# Off-line approximate dynamic programming for the vehicle routing problem with a highly variable customer basis and stochastic demands

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

## Key facts

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

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [A Review of Cooperative Multi-Agent Deep Reinforcement Learning](https://mlsanity.com/paper/1908.03963/) (2019)
- [Efficient Ridesharing Order Dispatching with Mean Field Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1901.11454/) (2019)
- [Deep Reinforcement Learning for Electric Vehicle Routing Problem with Time Windows](https://mlsanity.com/paper/2010.02068/) (2020)
- [MOVI: A Model-Free Approach to Dynamic Fleet Management](https://mlsanity.com/paper/1804.04758/) (2018)
- [Deep Q-Learning for Same-Day Delivery with Vehicles and Drones](https://mlsanity.com/paper/1910.11901/) (2019)
- [Learning to Optimize Industry-Scale Dynamic Pickup and Delivery Problems](https://mlsanity.com/paper/2105.12899/) (2021)
- [Can Sophisticated Dispatching Strategy Acquired by Reinforcement Learning? - A Case Study in Dynamic Courier Dispatching System](https://mlsanity.com/paper/1903.02716/) (2019)

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

- [A Deep Reinforcement Learning Algorithm for the Vehicle Routing Problem with Stochastic Demands and Outsourcing](https://mlsanity.com/paper/2607.16875/) (2026)

## Abstract (arXiv)

We study a stochastic variant of the vehicle routing problem arising in the context of domestic donor collection services. The problem we consider combines the following attributes. Customers requesting services are variable, in the sense that the customers are stochastic but are not restricted to a predefined set, as they may appear anywhere in a given service area. Furthermore, demand volumes are stochastic and observed upon visiting the customer. The objective is to maximize the expected served demands while meeting vehicle capacity and time restrictions. We call this problem the VRP with a highly Variable Customer basis and Stochastic Demands (VRP-VCSD). For this problem, we first propose a Markov Decision Process (MDP) formulation representing the classical centralized decision-making perspective where one decision-maker establishes the routes of all vehicles. While the resulting formulation turns out to be intractable, it provides us with the ground to develop a new MDP formulation, which we call partially decentralized. In this formulation, the action-space is decomposed by vehicle. However, the decentralization is incomplete as we enforce identical vehicle-specific policies while optimizing the collective reward. We propose several strategies to reduce the dimension of the state and action spaces associated with the partially decentralized formulation. These yield a considerably more tractable problem, which we solve via Reinforcement Learning. In particular, we develop a Q-learning algorithm called DecQN, featuring state-of-the-art acceleration techniques. We conduct a thorough computational analysis. Results show that DecQN considerably outperforms three benchmark policies. Moreover, we show that our approach can compete with specialized methods developed for the particular case of the VRP-VCSD, where customer locations and expected demands are known in advance.