  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
Branch-and-Price (B&P) algorithms 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 construct the first labeling algorithm that can deal with
minimizing (excess) user ride time. In the computational experiments, the B&P
algorithm achieves optimality in 71 out of 84 instances. Remarkably, among
these instances, 50 were solved optimally at the root node without branching.
We identify 26 new best solutions, improve 30 previously reported lower bounds,
and provide 17 new lower bounds for large-scale instances with up to 8 vehicles
and 96 requests. In total 42 new best solutions are generated on previously
solved and unsolved instances.
