Battery swapping, vehicle rebalancing, and staff routing for electric scooter sharing systems

Electric scooter (e-scooter) sharing systems provide on-demand electric scooter rental services. E-scooters are equipped with swappable batteries managed by staff who visit each scooter and replace depleted batteries with charged ones. The e-scooters in this system are free-floating; they can be located anywhere without having to be returned to designated stations. Due to this characteristic of the scattered location of e-scooters, operation decisions with associated staff routing are more challenging than station-based services. Thus, it is critical to implement the efficient management of e-scooter redistribution and charging decisions with proper staff routing to successfully prepare for user demand within a limited operation time while minimizing the total operating cost. To this end, we introduce a battery swapping and vehicle rebalancing problem with staff routing for e-scooter sharing systems, formulated as a mixed integer programming (MIP) model. To derive solutions efficiently for a large-scale instance in practice, we propose a clustered iterative construction approach where the problem is decomposed into two phases. The first phase clusters regions using an approximation of intra-region and inter-region operation costs with the minimum spanning tree approach. The second phase efficiently derives multiple candidate regional sequences by our partial permutation procedure and following the sequences, iteratively solves a significantly reduced size of the problem to construct operation assignments. Our numerical experiments on the generated instances and real-world instances demonstrate that the proposed two-phase algorithm shows significantly superior performance in practically large scale instances than the benchmarks without clustering or the iterative procedures of our algorithm.