Efficient Collaborative Multi-Agent Deep Reinforcement Learning for Large-Scale Fleet Management

Kaixiang Lin, Renyu Zhao, Zhe Xu, Jiayu Zhou

Abstract

Large-scale online ride-sharing platforms have substantially transformed our lives by reallocating transportation resources to alleviate traffic congestion and promote transportation efficiency. An efficient fleet management strategy not only can significantly improve the utilization of transportation resources but also increase the revenue and customer satisfaction. It is a challenging task to design an effective fleet management strategy that can adapt to an environment involving complex dynamics between demand and supply. Existing studies usually work on a simplified problem setting that can hardly capture the complicated stochastic demand-supply variations in high-dimensional space. In this paper we propose to tackle the large-scale fleet management problem using reinforcement learning, and propose a contextual multi-agent reinforcement learning framework including three concrete algorithms to achieve coordination among a large number of agents adaptive to different contexts. We show significant improvements of the proposed framework over state-of-the-art approaches through extensive empirical studies.

Introduction

In modern ride-sharing ecosystems, a persistent challenge is the spatial-temporal mismatch between passenger demand and vehicle supply. While passengers in one urban sector may experience long wait times, idle vehicles might be concentrated in another. Efficient fleet management requires "repositioning" empty vehicles to anticipated high-demand areas. However, scaling Reinforcement Learning (RL) to thousands of agents in a dynamic urban environment introduces significant hurdles: the curse of dimensionality in action spaces, environmental non-stationarity, and complex geographic constraints.

The Grid World environment illustrating agent repositioning and order fulfillment across hexagonal cells.

Methodology: Contextual MARL

To address these challenges, we introduce the Contextual Multi-Agent Reinforcement Learning (cMARL) framework. The core innovation lies in using "contexts" to prune the action space and stabilize learning.

Framework Components

  1. Contextual DQN (cDQN): Employs a centralized action-value table shared across agents. It utilizes a Geographic Context to mask physically impossible moves and a Collaborative Context to prevent agents from moving to regions with lower expected utility than their current location.
  2. Contextual Actor-Critic (cA2C): A policy gradient approach that integrates "Policy Context Embedding." As shown in the architecture, the network masks output logits based on geographic and collaborative constraints, ensuring valid and efficient action selection.
  3. LP-cA2C: This hybrid approach combines the valuation strengths of RL with the allocation efficiency of Linear Programming (LP). By feeding state-values from cA2C into an LP optimizer, the system finds the global optimal flow of vehicles, minimizing redundant "shuffling" moves.
  4. Averaged Reward Design: To foster cooperation, agents receive rewards based on the averaged revenue of all agents in a specific grid at a specific time. This "credit assignment" trick encourages agents to cooperate rather than compete for individual high-value orders.
The cMARL architecture featuring centralized value output and decentralized actor execution with context-based logit masking.

Experimental Setup and Results

The framework was evaluated using massive real-world datasets from Didi Chuxing in Chengdu (504 grids) and Wuhan (1,000+ grids). A custom simulator, calibrated to match real-world Gross Merchandise Volume (GMV) with high fidelity ($r^2 = 0.9331$), served as the training environment.

Key Findings

  • Performance: LP-cA2C consistently outperformed baselines in both GMV and Order Response Rate (ORR).
  • Efficiency: The collaborative context and LP layer significantly reduced the number of unnecessary repositions, leading to a higher Return on Investment (ROI) compared to independent or rule-based agents.
  • Scalability: The framework successfully coordinated over 5,000 agents, demonstrating robustness against the non-stationarity typically found in large-scale multi-agent systems.

Conclusion

By integrating geographic and collaborative contexts into a multi-agent reinforcement learning framework, we provide a scalable solution for large-scale fleet management. The combination of RL for value estimation and Linear Programming for optimal dispatching offers a powerful paradigm for urban resource allocation. Future work will explore stochastic travel times and heterogeneous agent types to further bridge the gap between simulation and real-world deployment.

Summary updated

Abstract

Large-scale online ride-sharing platforms have substantially transformed our lives by reallocating transportation resources to alleviate traffic congestion and promote transportation efficiency. An efficient fleet management strategy not only can significantly improve the utilization of transportation resources but also increase the revenue and customer satisfaction. It is a challenging task to design an effective fleet management strategy that can adapt to an environment involving complex dynamics between demand and supply. Existing studies usually work on a simplified problem setting that can hardly capture the complicated stochastic demand-supply variations in high-dimensional space. In this paper we propose to tackle the large-scale fleet management problem using reinforcement learning, and propose a contextual multi-agent reinforcement learning framework including three concrete algorithms to achieve coordination among a large number of agents adaptive to different contexts. We show significant improvements of the proposed framework over state-of-the-art approaches through extensive empirical studies.
BibTeX
@misc{lin2018efficient,
  author = {Kaixiang Lin and Renyu Zhao and Zhe Xu and Jiayu Zhou},
  title = {{Efficient Collaborative Multi-Agent Deep Reinforcement Learning for Large-Scale Fleet Management}},
  year = {2018},
  eprint = {1802.06444},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1802.06444},
}
Figure