Mobility-on-Demand with Electric Vehicles: Scalable Route and Recharging Planning through Column Generation.

The rise of battery-powered vehicles for mobility-on-demand leads to many technical and methodological hurdles. Among these, the efficient planning of a shared electric fleet to fulfill passenger transportation requests still represents a major challenge. This is due to the specific constraints of electric vehicles, bound by their autonomy and necessity of recharge planning, and the typical large scale of these systems, which challenges existing optimization algorithms. The purpose of this paper is to introduce a scalable column generation approach for the problem of managing electric mobility-on-demand fleets. Our algorithm relies on three ingredients: (i) an algebraic framework leading to an efficient algorithm for the pricing subproblem despite its non-linearity, (ii) sparsification approaches permitting to decrease the size of the subjacent graphs dramatically, and (iii) a diving heuristic, which locates near-optimal solutions in a fraction of the time needed for a complete branch-and-price. Through extensive computational experiments, we demonstrate that our approach significantly outperforms previous algorithms for this setting, leading to accurate solutions for problems counting several hundreds of requests.