In the electric autonomous dial-a-ride problem (E-ADARP) a fleet of electric autonomous vehicles provides ride-sharing services for customers between specified origin and destination locations, minimizing a weighted sum of cost and excess user ride time. In this work, we propose a column generation approach relying on a fragment-based representation of paths. Each fragment corresponds to a feasible sequence of pickup and drop-off nodes. At the start and the end of each fragment the vehicle is empty. Our representation allows us to ensure excess user ride time optimality along the path during the execution of the labeling algorithm. Partial recharging is handled by tailored resource extension functions. The obtained lower bounds are strengthened by two-path cuts and subset row inequalities. When applied to single objective benchmark instances, a majority of the instances can already be solved in the root node to integer optimality and 17 new optimal solutions are identified. We also embed the proposed column generation scheme into different bi-objective optimization frameworks so as to analyze the trade-off between the two concurrently considered objectives.
This is joint work with Yue Su, Nicolas Dupin, and Jakob Puchinger.