A Column Generation Approach for 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 typical 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. We present a highly-efficient column generation (CG) approach to solve the E-ADARP, where a customized labeling algorithm is designed to solve CG subproblems. To handle (i), we propose a segment-based representation for a partial path that generalizes sequences of Resource Extension Functions (REFs) to single REFs. When extending the partial path, a novel schedule optimization method is invoked to generate all the optimal schedules. Partial recharging (ii) is tackled by tailored REFs, and we define strong dominance rules to allow fast computation of the shortest paths with constant time feasibility checking. In the computational experiments, 50 instances out of 84 are solved optimally at the root node without branching and we identify 15 new optimal solutions. The Lagrangian lower bounds have an average gap of 0.31% to the best-found solutions, and we enhance 24 previously-reported lower bounds and provide 17 new lower bounds for large-scale instances. Thirty-six new best solutions are generated on previously solved and unsolved instances, and the proposed CG approach is able to handle instances with up to 8 vehicles and 96 requests. The superiority of our CG algorithm over the existing exact method is therefore highlighted by these computational results