Multi-stage Dynamic Scheduling Optimization for Autonomous Mobility-on-Demand Systems

Autonomous Mobility-on-Demand (AMoD) system is booming in urban transportation, however, the uncertain and complex fleet dynamic scheduling remains one of the main challenges for operators. Therefore, this study proposes a multistage dynamic scheduling approach for shared autonomous electric vehicles (SAEVs). Specifically, considering the matching characteristics of the different tasks, the vehicle order-taking and charging tasks are modelled as bipartite graph maximum weight matching problems with the objectives of maximizing order revenue and minimizing charging mileage. The vehicle repositioning task is modelled as integer programming with the objective of minimizing the vehicle dispatch mileage, and stochastic chance-constrained programming is applied to cope with uncertain user demands. A solution strategy combining the KM algorithm with Gurobi solver and greedy strategy is designed to obtain the real-time scheduling instructions. Finally, numerical experiments based on real travel data validate the advantages of the proposed approach in reducing fleet scheduling costs and improving system operational revenues.