A Ride Time-Oriented Scheduling Algorithm for Dial-a-Ride Problems

This paper offers a new algorithm to efficiently optimize scheduling decisions for dial-a-ride problems (DARPs), including problem variants considering electric and autonomous vehicles (e-ADARPs). The scheduling heuristic, based on linear programming theory, aims at finding minimal user ride time schedules in polynomial time. The algorithm can either return optimal feasible routes or it can return incorrect infeasibility declarations, on which feasibility can be recovered through a specifically-designed heuristic. The algorithm is furthermore supplemented by a battery management algorithm that can be used to determine charging decisions for electric and autonomous vehicle fleets. Timing solutions from the proposed scheduling algorithm are obtained on millions of routes extracted from DARP and e-ADARP benchmark instances. They are compared to those obtained from a linear program, as well as to popular scheduling procedures from the DARP literature. Results show that the proposed procedure outperforms state-of-the-art scheduling algorithms, both in terms of compute-efficiency and solution quality