# DROP: Deep relocating option policy for optimal ride-hailing vehicle repositioning

arXiv: https://arxiv.org/abs/2109.04149 · HTML: https://mlsanity.com/paper/2109.04149/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 49 references that are in the map.
- First posted on arXiv 9 Sep 2021.

## Builds on (most cited first, 14 of 14)

- [A Laplacian Framework for Option Discovery in Reinforcement Learning](https://mlsanity.com/paper/1703.00956/) (2017)
- [The Laplacian in RL: Learning Representations with Efficient Approximations](https://mlsanity.com/paper/1810.04586/) (2018)
- [Efficient Ridesharing Order Dispatching with Mean Field Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1901.11454/) (2019)
- [DeepPool: Distributed Model-free Algorithm for Ride-sharing using Deep Reinforcement Learning](https://mlsanity.com/paper/1903.03882/) (2019)
- [A Deep Value-network Based Approach for Multi-Driver Order Dispatching](https://mlsanity.com/paper/2106.04493/) (2021)
- [Reinforcement Learning for Ridesharing: An Extended Survey](https://mlsanity.com/paper/2105.01099/) (2021)
- [Deep Reinforcement Learning for Multi-Driver Vehicle Dispatching and Repositioning Problem](https://mlsanity.com/paper/1911.11260/) (2019)
- [Multi-Agent Reinforcement Learning for Order-dispatching via Order-Vehicle Distribution Matching](https://mlsanity.com/paper/1910.02591/) (2019)
- [Control of Robotic Mobility-On-Demand Systems: a Queueing-Theoretical Perspective](https://mlsanity.com/paper/1404.4391/) (2014)
- [CoRide: Joint Order Dispatching and Fleet Management for Multi-Scale Ride-Hailing Platforms](https://mlsanity.com/paper/1905.11353/) (2019)
- [Real-world Ride-hailing Vehicle Repositioning using Deep Reinforcement Learning](https://mlsanity.com/paper/2103.04555/) (2021)
- [A Distributed Model-Free Ride-Sharing Approach for Joint Matching, Pricing, and Dispatching using Deep Reinforcement Learning](https://mlsanity.com/paper/2010.01755/) (2020)
- [Reward Design for Driver Repositioning Using Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2002.06723/) (2020)
- [Rebalancing the Rebalancers: Optimally Routing Vehicles and Drivers in Mobility-on-Demand Systems](https://mlsanity.com/paper/1303.3522/) (2013)

## Built on by (most cited first, 1 of 1)

- [SPO-VCS: An End-to-End Smart Predict-then-Optimize Framework with Alternating Differentiation Method for Relocation Problems in Large-Scale Vehicle Crowd Sensing](https://mlsanity.com/paper/2411.18432/) (2024)

## Abstract (arXiv)

In a ride-hailing system, an optimal relocation of vacant vehicles can significantly reduce fleet idling time and balance the supply-demand distribution, enhancing system efficiency and promoting driver satisfaction and retention. Model-free deep reinforcement learning (DRL) has been shown to dynamically learn the relocating policy by actively interacting with the intrinsic dynamics in large-scale ride-hailing systems. However, the issues of sparse reward signals and unbalanced demand and supply distribution place critical barriers in developing effective DRL models. Conventional exploration strategy (e.g., the ε-greedy) may barely work under such an environment because of dithering in low-demand regions distant from high-revenue regions. This study proposes the deep relocating option policy (DROP) that supervises vehicle agents to escape from oversupply areas and effectively relocate to potentially underserved areas. We propose to learn the Laplacian embedding of a time-expanded relocation graph, as an approximation representation of the system relocation policy. The embedding generates task-agnostic signals, which in combination with task-dependent signals, constitute the pseudo-reward function for generating DROPs. We present a hierarchical learning framework that trains a high-level relocation policy and a set of low-level DROPs. The effectiveness of our approach is demonstrated using a custom-built high-fidelity simulator with real-world trip record data. We report that DROP significantly improves baseline models with 15.7% more hourly revenue and can effectively resolve the dithering issue in low-demand areas.