Optimizing battery swapping for city-scale e-bike sharing systems: A three-stage spatial–temporal cluster-based approach

As a newly emerging mode of shared micro-mobility, the e-bike sharing system (EBSS) is increasingly establishing more stations to meet rising user demand. Due to the vast number of stations and the limited space available on urban streets, the operation of the EBSS largely relies on the platform’s battery swapping. This paper, for the first time, models the EBSS battery swapping problem as a variant of the multi-depot vehicle routing problem with soft time windows and proposes a three-stage algorithm for resolution. The first stage partitions the EBSS into exclusively operating service regions. A capacitated k-medoids clustering method is proposed, which incorporates special nodes, including battery warehouses and truck depots. The second stage further clusters the stations into smaller fan-shaped clusters to streamline the routing problem and enable parallel computation. In the third stage, the routes are obtained with the two-layer adaptive large neighborhood search (ALNS) with the iterative implementation of inner-layer and out-layer ALNS. Empirical evaluations conducted on a real-world city-wide EBSS in Hefei, China, comprising 4500 e-bike stations, demonstrate that the proposed three-stage method outperforms the prevailing practice utilizing a grid partitioning-based clustering method by around 25% through more informed clustering considering demand dynamics. Furthermore, compared to directly applying ALNS, our cluster-based method yields solutions with a difference of less than 3% in quality while consuming only 0.5% of the computation time.