# Neural Approximate Dynamic Programming for On-Demand Ride-Pooling

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Nov 2019.

## Built on by (most cited first, 30 of 33)

- [Reinforcement Learning for Ridesharing: An Extended Survey](https://mlsanity.com/paper/2105.01099/) (2021)
- [Real-world Ride-hailing Vehicle Repositioning using Deep Reinforcement Learning](https://mlsanity.com/paper/2103.04555/) (2021)
- [Data-Driven Methods for Balancing Fairness and Efficiency in Ride-Pooling](https://mlsanity.com/paper/2110.03524/) (2021)
- [An Online Approach to Solve the Dynamic Vehicle Routing Problem with Stochastic Trip Requests for Paratransit Services](https://mlsanity.com/paper/2203.15127/) (2022)
- [BMG-Q: Localized Bipartite Match Graph Attention Q-Learning for Ride-Pooling Order Dispatch](https://mlsanity.com/paper/2501.13448/) (2025)
- [Enabling MCTS Explainability for Sequential Planning Through Computation Tree Logic](https://mlsanity.com/paper/2407.10820/) (2024)
- [Using Simple Incentives to Improve Two-Sided Fairness in Ridesharing Systems](https://mlsanity.com/paper/2303.14332/) (2023)
- [Multi Agent Reinforcement Learning for Sequential Satellite Assignment Problems](https://mlsanity.com/paper/2412.15573/) (2024)
- [DECAF: Learning to be Fair in Multi-agent Resource Allocation](https://mlsanity.com/paper/2502.04281/) (2025)
- [Deep Reinforcement Learning for Demand Driven Services in Logistics and Transportation Systems: A Survey](https://mlsanity.com/paper/2108.04462/) (2021)
- [Future Aware Pricing and Matching for Sustainable On-demand Ride Pooling](https://mlsanity.com/paper/2302.10510/) (2023)
- [Mutual Information as Intrinsic Reward of Reinforcement Learning Agents for On-demand Ride Pooling](https://mlsanity.com/paper/2312.15195/) (2023)
- [Coordinating Ride-Pooling with Public Transit using Reward-Guided Conservative Q-Learning: An Offline Training and Online Fine-Tuning Reinforcement Learning Framework](https://mlsanity.com/paper/2501.14199/) (2025)
- [Conditional Expectation based Value Decomposition for Scalable On-Demand Ride Pooling](https://mlsanity.com/paper/2112.00579/) (2021)
- [Designing Decision Support Systems for Emergency Response: Challenges and Opportunities](https://mlsanity.com/paper/2202.11268/) (2022)
- [ADPTriage: Approximate Dynamic Programming for Bug Triage](https://mlsanity.com/paper/2211.00872/) (2022)
- [Neural Approximate Dynamic Programming for the Ultra-fast Order Dispatching Problem](https://mlsanity.com/paper/2311.12975/) (2023)
- [Dynamic AGV Task Allocation in Intelligent Warehouses](https://mlsanity.com/paper/2312.16026/) (2023)
- [Optimizing Ride-Pooling Operations with Extended Pickup and Drop-Off Flexibility](https://mlsanity.com/paper/2503.08472/) (2025)
- [Past-Discounting is Key for Learning Markovian Fairness with Long Horizons](https://mlsanity.com/paper/2504.01154/) (2025)
- [Fair Algorithms with Probing for Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2506.14988/) (2025)
- [Efficiency, Fairness, and Stability in Non-Commercial Peer-to-Peer Ridesharing](https://mlsanity.com/paper/2110.01152/) (2021)
- [Learning Individual Policies in Large Multi-agent Systems through Local Variance Minimization](https://mlsanity.com/paper/2212.13379/) (2022)
- [A Survey on Applications of Reinforcement Learning in Spatial Resource Allocation](https://mlsanity.com/paper/2403.03643/) (2024)
- [Long-term Fairness in Ride-Hailing Platform](https://mlsanity.com/paper/2407.17839/) (2024)
- [Ride-pool Assignment Algorithms: Modern Implementation and Swapping Heuristics](https://mlsanity.com/paper/2504.10649/) (2025)
- [Joint Matching and Pricing for Crowd-shipping with In-store Customers](https://mlsanity.com/paper/2507.01749/) (2025)
- [Online Learning with Probing for Sequential User-Centric Selection](https://mlsanity.com/paper/2507.20112/) (2025)
- [Adaptive Optimisation of Ride-Pooling Personalised Fares in a Stochastic Framework](https://mlsanity.com/paper/2508.20723/) (2025)
- [Non-myopic Matching and Rebalancing in Large-Scale On-Demand Ride-Pooling Systems Using Simulation-Informed Reinforcement Learning](https://mlsanity.com/paper/2510.25796/) (2025)

## Abstract (arXiv)

On-demand ride-pooling (e.g., UberPool) has recently become popular because of its ability to lower costs for passengers while simultaneously increasing revenue for drivers and aggregation companies. Unlike in Taxi on Demand (ToD) services -- where a vehicle is only assigned one passenger at a time -- in on-demand ride-pooling, each (possibly partially filled) vehicle can be assigned a group of passenger requests with multiple different origin and destination pairs. To ensure near real-time response, existing solutions to the real-time ride-pooling problem are myopic in that they optimise the objective (e.g., maximise the number of passengers served) for the current time step without considering its effect on future assignments. This is because even a myopic assignment in ride-pooling involves considering what combinations of passenger requests that can be assigned to vehicles, which adds a layer of combinatorial complexity to the ToD problem. A popular approach that addresses the limitations of myopic assignments in ToD problems is Approximate Dynamic Programming (ADP). Existing ADP methods for ToD can only handle Linear Program (LP) based assignments, however, while the assignment problem in ride-pooling requires an Integer Linear Program (ILP) with bad LP relaxations. To this end, our key technical contribution is in providing a general ADP method that can learn from ILP-based assignments. Additionally, we handle the extra combinatorial complexity from combinations of passenger requests by using a Neural Network based approximate value function and show a connection to Deep Reinforcement Learning that allows us to learn this value-function with increased stability and sample-efficiency. We show that our approach outperforms past approaches on a real-world dataset by up to 16%, a significant improvement in city-scale transportation problems.