Joint Optimization of Relocation and Routing Strategies for E-Scooter Sharing System

In recent years, shared micro-mobility services have gained momentum, also as an extension of public transportation such as metro and buses. They have gradually become an indispensable part of the urban transportation system. However, the enhanced flexibility and the sharp increase in the number of vehicles have also brought new challenges. One of the most significant is the spontaneous imbalance problem especially in peak hours, which could lead to the accumulation of scooters in some areas while unsatisfying demand in others, resulting in a waste of resources and loss of profit. In this context, this paper takes a dock-less e-scooters sharing system as the research object, and proposes joint optimization of relocation and routing strategies. Specifically, we solve the e-scooter imbalance problem in two phases. In the first phase, multiple dispatch trucks perform dynamic repositioning of scooters while considering expected future demand, that is, trucks pick up a certain number of scooters from the zones with surplus scooters and drop them off to the zones with unsatisfied demand of scooters. At this phase, each truck is only taking scooters of a single pick up zone and a single drop off zone, i.e., matching. The relocation is dynamic: during a time slot, the relocation operations take place while at the same time the customers are also using scooters across zones. We formulate the dynamic repositioning problem as a Mixed Integer Linear Programming (MILP) model to optimize the dispatched trucks' relocation operation, that is, the number of scooters picked up/dropped off and the corresponding zones. The model aims at maximizing total profit (that is, the revenue of satisfied trips minus the relocation cost), taking into account parameters including the predicted demand, the number and capacity of dispatched trucks, the unit mileage cost per truck and the unit cost for relocating one scooter, the look-ahead horizon and the optimization horizon. In the second phase, given the output of the first model, a set of vertices representing city zones and the corresponding relocation (positive in case of drop off, negative in case of pick up), the dispatch trucks start from the depot with an empty load, passing all vertices and performing the relocation operations follow proper routes, and finally back to the depot. This problem is actually denoted as the Vehicle Routing Problem with Pickup and Delivery (VRPPD), and formulated as the second MILP model to optimize the routes of multiple dispatch trucks. The objective function is to minimize total routing cost, with the additional constraint of maximum routing time. Furthermore, the models are applied to solve toy case problems. And the outputs of the model are fed to a simulator, in which the customers' trips are generated according to the Origin-Destination matrix, uniformly distributed over the time slots, in random order. The simulation results are obtained and compared with theoretical optimal results(i.e. the results given by the model directly). We also discuss the impact of the different parameters on both two results. Finally, the developed joint optimization is applied to a practical case, in which a trace of recorded e-scooter trips is collected from the real world. The result of the developed joint optimization shows a significant improvement compared to the case without relocation or with a simpler relocation strategy.