# On-Demand Delivery from Stores: Dynamic Dispatching and Routing with Random Demand

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jul 2021.

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

- [Neural Approximate Dynamic Programming for the Ultra-fast Order Dispatching Problem](https://mlsanity.com/paper/2311.12975/) (2023)
- [UrbanHuRo: A Two-Layer Human-Robot Collaboration Framework for the Joint Optimization of Heterogeneous Urban Services](https://mlsanity.com/paper/2603.03701/) (2026)

## Abstract (arXiv)

On-demand delivery has become increasingly popular around the world. Motivated by a large grocery chain store who offers fast on-demand delivery services, we model and solve a stochastic dynamic driver dispatching and routing problem for last-mile delivery systems where on-time performance is the main target. The system operator needs to dispatch a set of drivers and specify their delivery routes facing random demand that arrives over a fixed number of periods. The resulting stochastic dynamic program is challenging to solve due to the curse of dimensionality. We propose a novel structured approximation framework to approximate the value function via a parametrized dispatching and routing policy. We analyze the structural properties of the approximation framework and establish its performance guarantee under large-demand scenarios. We then develop efficient exact algorithms for the approximation problem based on Benders decomposition and column generation, which deliver verifiably optimal solutions within minutes. The evaluation results on a real-world data set show that our framework outperforms the current policy of the company by 36.53% on average in terms of delivery time. We also perform several policy experiments to understand the value of dynamic dispatching and routing with varying fleet sizes and dispatch frequencies.