Large Neigborhood Search for the Electric Dial-A-Ride Problem Integrated with Timetabled Transit

Integrating demand-responsive mobility services with transit systems is recognized as a practical and effective strategy to mitigate their impact on traffic congestion and the environment. This paper develops an efficient hybrid metaheuristic to solve the corresponding integrated dial-a-ride problem utilizing electric vehicles to minimize both operational costs and customer travel time. The system aims to improve customer convenience by limiting a maximum intermodal transfer time to synchronize demand-responsive buses’ arrival and transit departures. The proposed metaheuristic addresses the challenges of optimizing the integrated demand-responsive vehicle routing and charging operations with fixed-route transit systems with capacitated charging stations and partial recharge. The algorithm is tested on instances with up to 50 customers, outperforming an 8-hour state-of-the-art solver by 23% in solution quality, with an average runtime of 136 seconds.