  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.

Optimization and Control;Data Structures and Algorithms