Optimal rebalancing and on-board charging of shared electric scooters

This paper presents a sequence of models for optimal overnight charging and rebalancing of shared electric scooters (e-scooters) by allowing e-scooters to be charged while being transported on rebalancing vehicles. This problem is first modeled as a mixed-integer program for the multi-commodity inventory routing problem, where commodities represent e-scooters with different states of charge. To avoid prohibitive computation burden, continuous approximation techniques are proposed to estimate costs associated with the pickup and drop-off operations in small local neighborhoods, and the formulation turns into a discrete-continuous hybrid model for the integrated operations at both local and line-haul levels. A series of numerical experiments are conducted to demonstrate that, as compared to direct application of the discrete formulation, the proposed hybrid approach can produce good quality solutions for large-scale instances in a much shorter computation time.