Towards Supply-Demand Equilibrium With Ridesharing: An Elastic Order Dispatching Algorithm in MoD System

Mobility on demand (MoD) systems utilize ridesharing, i.e., multiple orders with high associating utility share a single vehicle, to reduce carbon footprint and alleviate traffic pressure. Existing methods mainly promote ridesharing by flocking multiple orders to the minimum required vehicles. However, supply-demand variations may aggregate undersupply in the long run and affect the order completion rate. Meanwhile, it is difficult to accurately estimate associating utility among ridesharing orders with lane-level features, such as traffic flow. To fill this gap, we propose ERShare, an elastic order dispatching algorithm to maximize the order completion rate in the MoD system. First, the ridesharing order dispatching problem is formulated as an offline optimization problem, and then it is proved that the order completion rate is maximized when the MoD system achieves long-term supply-demand equilibrium. Next, a dummy order/vehicle generation method is proposed to generate dummies as a spinner to achieve supply-demand equilibrium elastically. Also, a lane-level ridesharing rule is designed to accurately estimate the associating utility based on an order association graph. Subsequently, a dummy-based order dispatching algorithm is proposed to find the optimal dispatching decisions. Finally, the simulations on real-world data validate the superiority of ERShare over state-of-the-art solutions regarding order completion rate.