Column Generation for Solving the Electric Autonomous Dial-a-Ride Problem

The Electric Autonomous Dial-A-Ride Problem (E-ADARP) consists in scheduling a fleet of electric autonomous vehicles to provide ride-sharing services for customers that specify their origins and destinations. The E-ADARP differs from the classical DARP in two aspects: (i) a weighted-sum objective that minimizes both total travel time and total excess user ride time; (ii) the employment of electric autonomous vehicles and a partial recharging policy. This paper presents a highly-efficient labeling algorithm, which is integrated into Column Generation (CG) to solve the E-ADARP. To handle (i), we introduce a fragment-based representation of paths. A novel approach is invoked to abstract fragments to arcs while ensuring excess-user-ride-time optimality. We then construct a new graph that preserves all feasible routes of the original graph by enumerating all feasible fragments, abstracting them to arcs, and connecting them with each other, depots, and recharging stations in a feasible way. On the new graph, partial recharging (ii) is tackled exactly by tailored Resource Extension Functions (REFs). We apply strong dominance rules and constant-time feasibility checks to compute the shortest paths efficiently. These methods pave the way for a powerful labeling algorithm that ensures excess-user-ride-time optimality in label extension. In the computational experiments, 66 instances out of 84 are solved optimally at the root node without branching, and we identify 17 new optimal solutions. We improve 29 previously-reported lower bounds by 1.35\% on average and provide 17 new lower bounds for large-scale instances with up to 8 vehicles and 96 requests. In total 41 new best solutions are generated on previously solved and unsolved instances.