# Approximate Dynamic Programming for Planning a Ride-Sharing System using Autonomous Fleets of Electric Vehicles

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Oct 2018.

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

- [Reinforcement Learning for Ridesharing: An Extended Survey](https://mlsanity.com/paper/2105.01099/) (2021)
- [A Deep Reinforcement Learning Approach for the Meal Delivery Problem](https://mlsanity.com/paper/2104.12000/) (2021)
- [Where the Action is: Let's make Reinforcement Learning for Stochastic Dynamic Vehicle Routing Problems work!](https://mlsanity.com/paper/2103.00507/) (2021)
- [A Reinforcement Learning Approach to the Stochastic Cutting Stock Problem](https://mlsanity.com/paper/2109.09592/) (2021)
- [Neural Approximate Dynamic Programming for the Ultra-fast Order Dispatching Problem](https://mlsanity.com/paper/2311.12975/) (2023)
- [Atomic Proximal Policy Optimization for Electric Robo-Taxi Dispatch and Charger Allocation](https://mlsanity.com/paper/2502.13392/) (2025)
- [To Start Up a Start-Up-Embedding Strategic Demand Development in Operational On-Demand Fulfillment via Reinforcement Learning with Information Shaping](https://mlsanity.com/paper/2504.05633/) (2025)
- [Joint Matching and Pricing for Crowd-shipping with In-store Customers](https://mlsanity.com/paper/2507.01749/) (2025)

## Abstract (arXiv)

Within a decade, almost every major auto company, along with fleet operators such as Uber, have announced plans to put autonomous vehicles on the road. At the same time, electric vehicles are quickly emerging as a next-generation technology that is cost effective, in addition to offering the benefits of reducing the carbon footprint. The combination of a centrally managed fleet of driverless vehicles, along with the operating characteristics of electric vehicles, is creating a transformative new technology that offers significant cost savings with high service levels. This problem involves a dispatch problem for assigning riders to cars, a surge pricing problem for deciding on the price per trip and a planning problem for deciding on the fleet size. We use approximate dynamic programming to develop high-quality operational dispatch strategies to determine which car is best for a particular trip, when a car should be recharged, and when it should be re-positioned to a different zone which offers a higher density of trips. We prove that the value functions are monotone in the battery and time dimensions and use hierarchical aggregation to get better estimates of the value functions with a small number of observations. Then, surge pricing is discussed using an adaptive learning approach to decide on the price for each trip. Finally, we discuss the fleet size problem which depends on the previous two problems.