A bi-level approach for optimal vehicle relocating in Mobility-On-Demand systems with approximate dynamic programming and coverage control
针对出行即服务系统中车辆供需失衡问题，提出一种双层重定位方案：上层用宏观基本图建模并借助近似动态规划求解随机规划问题，下层用Voronoi覆盖控制算法引导车辆，在深圳路网模拟中提升了订单服务率并减少了等待时间。
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.