A bi-level approach for optimal vehicle relocating in Mobility-On-Demand systems with approximate dynamic programming and coverage control

For Mobility-on-Demand systems, the imbalance between vehicle supply and demand is a long-standing challenge, leading to losses of orders and long waiting times. Relocating idle vehicles to high-demand regions can enhance system efficiency, thus improving the quality of service. Enforcing vehicle relocation via either link-node or grid-based representation makes it hard to capture the interrelated dynamics with private vehicles while being computationally intensive. The macroscopic fundamental diagram (MFD) provides a powerful tool to model the interrelated dynamics while individual vehicle details may be absent in the regional-level representation. Therefore, we propose a bi-level rebalancing scheme to maximize the served orders in the system. The urban area is first partitioned into several subregions. For the upper level, the interrelated dynamics of private vehicles and on-demand vehicles are modeled based on the MFD. Then a stochastic programming problem is formulated and solved using Approximate Dynamic Programming (ADP) to determine the number of desired vehicles in each subregion and cross-border. For the lower level, a Voronoi-based distributed coverage control algorithm is implemented by each vehicle to obtain position guidance efficiently. The bi-level framework is evaluated on a simulator of the real road network of Shenzhen, China. Simulation results demonstrate that, compared to other policies, the proposed approach can serve more requests with less waiting time. • A bi-level vehicle relocation framework is proposed for on-demand vehicles. • Modeling the interrelated dynamics of on-demand and private vehicles via Macroscopic Fundamental diagram. • A stochastic programming problem is solved using Approximate Dynamic Programming (ADP) for the upper level. • A Voronoi-based distributed coverage control algorithm is implemented for the lower level.