Tackling Sparsity in Designated Driver Dispatch with Multi-Agent Reinforcement Learning

Designated driving service is a fast-growing market that provides drivers to transport customers in their own cars. The key technical challenge in this business lies in the design of driver repositioning due to the far distances between drivers and orders, which is caused by complex moving constraints of drivers and the "hub-and-spoke" structure of orders. To address these challenges, this paper proposes Reinforcement Learning for Designated Driver Dispatch (RLD3), a Multi-Agent Reinforcement Learning (MARL) algorithm based on the Partially Observed Markov Decision Process (POMDP) formulation. Our algorithm considers group-sharing structures and frequent potential rewards with heterogeneous costs to achieve a trade-off between heterogeneity and sparsity. Additionally, our algorithm addresses long-term agent cross-effects through windowlasting policy ensembles. We also implement a simulator to train and evaluate our algorithm using real-world data. Extensive experiments demonstrate that our algorithm achieves superior performance compared to existing Deep Reinforcement Learning (DRL) and taxi-reposition methods.