Source-linked AI summary
Efficient Ridesharing Order Dispatching with Mean Field Multi-Agent Reinforcement Learning
Minne Li, Zhiwei, Qin, Yan Jiao, Yaodong Yang, Zhichen Gong, Jun Wang, Chenxi Wang, Guobin Wu, Jieping Ye
TL;DR
The paper addresses real-time order dispatching under changing demand, supply, action sets, and driver populations, where existing rule-based and single-agent approaches are limited. It proposes MARL with centralized training, decentralized execution, and mean field approximation, and reports improved dispatching outcomes over strong baselines in large-scale simulations.
Problem
Order dispatching must maximize GMV while balancing immediate and long-term rewards, but existing methods rely on hand-crafted weights, limited communications, or single-agent formulations that oversimplify driver-order interactions.
Method
The paper uses MARL with centralized training and decentralized execution, assigning local rewards and demand-supply constraints while using mean field approximation for changing populations and local interactions.
Results
COD and IOD achieved higher GMV and ORR than three rule-based methods, higher GMV than HOD, and lower rush-hour supply-demand gaps in two large-scale simulation environments.
Takeaways & Limitations
The results support a fully decentralized, scalable order-dispatching system that can capture stochastic demand-supply dynamics and may reduce rush-hour traffic congestion.
Takeaways & Limitations
Naively concatenating all other agents’ actions is infeasible because the number of agents changes and large-scale interactions are intractable.
Abstract
from arXiv · showhide
A fundamental question in any peer-to-peer ridesharing system is how to, both effectively and efficiently, dispatch user's ride requests to the right driver in real time. Traditional rule-based solutions usually work on a simplified problem setting, which requires a sophisticated hand-crafted weight design for either centralized authority control or decentralized multi-agent scheduling systems. Although recent approaches have used reinforcement learning to provide centralized combinatorial optimization algorithms with informative weight values, their single-agent setting can hardly model the complex interactions between drivers and orders. In this paper, we address the order dispatching problem using multi-agent reinforcement learning (MARL), which follows the distributed nature of the peer-to-peer ridesharing problem and possesses the ability to capture the stochastic demand-supply dynamics in large-scale ridesharing scenarios. Being more reliable than centralized approaches, our proposed MARL solutions could also support fully distributed execution through recent advances in the Internet of Vehicles (IoV) and the Vehicle-to-Network (V2N). Furthermore, we adopt the mean field approximation to simplify the local interactions by taking an average action among neighborhoods. The mean field approximation is capable of globally capturing dynamic demand-supply variations by propagating many local interactions between agents and the environment. Our extensive experiments have shown the significant improvements of MARL order dispatching algorithms over several strong baselines on the gross merchandise volume (GMV), and order response rate measures. Besides, the simulated experiments with real data have also justified that our solution can alleviate the supply-demand gap during the rush hours, thus possessing the capability of reducing traffic congestion.
1 INTRODUCTION
Real-time ridesharing must dispatch orders among drivers while balancing immediate income against longer-term demand-supply effects. The paper proposes MARL with mean field approximation to handle changing action sets and populations in a distributed, scalable system.
- Motivation: Order dispatching assigns real-time ride requests to active drivers and directly affects transportation capacity, service income, and customer satisfaction.The paper targets maximizing daily gross merchandise volume while scaling to many drivers and remaining robust to hardware or connectivity failures.
- Motivation: Choosing an order requires balancing immediate price against longer-term outcomes when destinations differ in future demand.A higher-priced trip to a sparsely populated suburb may harm long-run GMV compared with an order ending near a high-demand CBD.
- Prior limitations: Hand-crafted centralized and distributed dispatching methods depend on sophisticated weighting schemes, while centralized control introduces a single-point-of-failure risk.Existing distributed solutions may also require direct communication rounds during execution, limiting them to small local areas.
- Prior limitations: Single-agent reinforcement learning oversimplifies driver-order interactions and stochastic demand-supply dynamics in large-scale ridesharing.Centralized execution retains the reliability concerns associated with centralized architectures.
- Proposed approach: The proposed MARL approach uses centralized training with decentralized execution, allowing actors to act independently from local information after training.The critic incorporates information from other agents during training, while fully distributed execution can be supported through IoV and V2N.
- Proposed approach: MARL faces changing action-set contents and population sizes because orders arrive or are taken, drivers move, and drivers switch between online and offline.Mean field approximation addresses variable population size by simplifying local interactions through neighborhood-level information.
2 METHOD
The paper formulates ridesharing order dispatching as a cooperative partially observable Markov game and develops MARL methods for variable action sets and changing agent populations. IOD uses independent actor-critic learning, while COD adds mean field approximation to capture neighborhood interactions and support decentralized execution; the paper also establishes convergence under stated assumptions.
- Game Settings: Order dispatching is modeled as a fully cooperative POMDP with changing numbers of homogeneous driver agents, private observations, joint actions, transitions, rewards, and discounting.Drivers may switch between online and offline, so the population size varies over time.
- Game Settings: The reward combines a driver’s own order income with destination potential and a pickup-distance regularizer to balance immediate revenue, future opportunities, and customer experience.Destination potential reflects demand and supply at the destination, while each driver’s own income is used to address credit assignment.
- Game Settings: Each driver’s action is an available order, so changing locations and times produce variable action sets that make Q-tables impractical.The action pool changes throughout training and execution and may have potentially infinite size.
- Independent Order Dispatching: IOD applies independent actor-critic policy-gradient learning, using a policy network that scores observation-order pairs to handle variable candidate sets.Order embeddings concatenate normalized origin and destination representations, supporting similar outputs for similar orders and improving generalization.
- Cooperative Order Dispatching with Mean Field Approximation: COD extends IOD with mean field approximation, replacing many-agent interactions with neighborhood average actions while retaining centralized training and decentralized execution.The average response is used for model updates, so agents can execute independently after training.
- Convergence of Mean Field Reinforcement Learning with Function Approximations: The convergence analysis uses an ODE argument and proves convergence with probability 1 for the function-approximated update under Lipschitz-continuity and stochastic-approximation assumptions.The proof follows trajectories toward a globally asymptotically stable equilibrium under the stated conditions.
3 EXPERIMENT
The experiments use grid-based and coordinate-based simulators to train and evaluate the MARL algorithm, differing mainly in how driver pickups are modeled.
- Two simulators support MARL training and evaluation: one uses a grid-based map, and the other uses a coordinate-based map.The grid-based simulator represents locations with grid IDs, whereas the coordinate-based simulator uses geographic coordinate vectors.
- The grid-based simulator assumes identical pickup distances and arrival times within each grid and no cancellations before pickup.This simplified representation hides exact within-grid coordinates.
- The coordinate-based simulator represents driver and order locations with two-value geographic-coordinate vectors and includes cancellation before pickup.Orders may be canceled when drivers take too long to reach their origins, making pickup distance consequential.
3.1 Grid-based Experiment
The grid-based experiment evaluates dispatching methods in a calibrated simulator using GMV, order response rate, and average destination potential. MARL methods, especially COD, improve income and response outcomes while alleviating demand-supply gaps by considering order value and destination potential.
- Environment Setting: The simulator represents the city as a hexagonal grid and provides active-driver and available-order observations at each time step.Orders include origin and destination grid IDs, while drivers use their current grid ID as a location feature.
- Environment Setting: The simulator bootstraps available orders from DiDi Chuxing order data and vehicle trajectories collected over three weeks.Orders are sampled with replacement from real orders occurring during the corresponding time interval.
- Model Setting: The evaluation compares random, response-based, revenue-based, IOD, and COD dispatching using GMV, order response rate, and average destination potential.The learning methods are trained for 20 episodes, evaluated using five random seeds, and compared against RAN-normalized performance.
- Result Analysis: COD achieves the best GMV by jointly considering order price and destination potential, whereas rule-based methods struggle to balance income per order with the number of orders taken.Low-potential destinations are less likely to be selected, reducing the chance that drivers become trapped in areas with few future orders.
- Result Analysis: IOD and COD achieve higher order response rates while dispatching drivers toward destinations with greater demand, and COD largely fills the city-center demand-supply gap during peak hours.Average destination potential remains negative for all methods, indicating that supply does not fully satisfy demand on average.
- Result Analysis: IOD and COD outperform RAN during most hours, with especially high hourly income during morning and evening peaks, while COD consistently outperforms IOD.REV exceeds MARL methods from late night to early morning but performs worse during much of the remaining day because its destination choices can lead to low-demand areas.
3.2 Coordinate-based Experiment
The coordinate-based experiment evaluates MARL dispatching methods against a centralized Hungarian-algorithm baseline using GMV and average arriving time. COD achieves stronger GMV performance, while MARL methods incur relatively longer arriving times but support decentralized execution.
- Coordinate-based simulator: The coordinate-based simulator represents real-world locations with active-driver and available-order coordinates, and models order cancellations during pickup.The dispatching algorithm follows the procedure described in Section 3.1.1.
- Compared methods: IOD, COD, and Q-IOD are evaluated against HOD, a centralized Hungarian-algorithm method that weights driver-order pairs by pickup distance.Q-IOD removes the policy network, while HOD focuses on minimizing average arriving time.
- Evaluation protocol: GMV1 excludes cancellations, whereas GMV2 includes them; all reported metrics are normalized against HOD after training on 400K iterations.The test set consists of three weekdays, and evaluation includes total daily income and average arriving time.
- Results: COD largely outperforms Q-IOD and IOD in both GMV1 and GMV2, and also outperforms HOD in both GMV settings.The reported comparison attributes COD’s advantage to directly modeling other agents’ policies and agent-environment interaction.
- Results: MARL methods have relatively longer AAT than the combinatorial optimization method, although the increase is described as tolerable because GMV values are much larger.Unlike HOD, MARL methods use pickup distance only as a regularization term.
- Deployment property: MARL methods require no centralized control during execution, making the dispatching system more robust to potential hardware or connectivity failures.
4 RELATED WORK
Prior order-dispatching research includes centralized and decentralized rule-based methods, negotiation-based multi-agent scheduling, and single-agent reinforcement learning. The paper positions MARL as a way to model driver-order interactions while retaining distributed execution.
- Rule-based approaches: Rule-based approaches select drivers using criteria such as pickup distance or time, but do not account for other orders’ effects.These methods commonly assign the nearest option on a first-come, first-served basis.
- Decentralized scheduling: Decentralized scheduling can group neighboring drivers and orders for simultaneous assignment, but may require several rounds of direct agent communication.Such negotiation is described as limited to a local area.
- Reinforcement learning: A prior RL formulation optimizes dispatching globally and farsightedly but uses a single-agent setting that cannot model complex driver-order interactions.
- Reinforcement learning: The paper’s multi-agent setting follows peer-to-peer ridesharing’s distributed nature, captures stochastic demand-supply dynamics, and allows independent execution under learned policies.
5 CONCLUSION
The paper concludes that MARL methods improve dispatching outcomes across large-scale simulations while supporting fully decentralized execution. The experiments and theory also indicate benefits for rush-hour supply-demand balance and mean-field MARL justification.
- Conclusion: COD and IOD achieve higher GMV and order response rate than three rule-based methods: RAN, RES, and REV.
- Conclusion: COD and IOD achieve higher GMV than HOD while retaining desirable properties of fully distributed execution.
- Conclusion: The proposed algorithms produce a lower supply-demand gap during rush hours, indicating the ability to reduce traffic congestion.
- Conclusion: The paper provides a convergence proof for applying mean field theory to MARL with function approximations.
- Conclusion: Vehicle-to-Network can distribute the centrally trained policy to each vehicle for fully decentralized execution.
- Conclusion: Future work targets controlling average arriving time while maximizing GMV and supporting heterogeneous agents with individual-specific features.