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

Sheng Liu () and Zhixing Luo ()
Additional contact information
Sheng Liu: Rotman School of Management, University of Toronto, Toronto, Ontario M5S 3E6, Canada
Zhixing Luo: Department of Industrial Engineering and Operations Management, School of Management and Engineering, Nanjing University, Nanjing City, 210093 Jiangsu, China

Manufacturing & Service Operations Management, 2023, vol. 25, issue 2, 595-612

Abstract: Problem definition : 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 because of the curse of dimensionality. Methodology/results : 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. Managerial implications : 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.

Keywords: on-time delivery; stochastic dynamic programming; optimization; Benders decomposition (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/msom.2022.1171 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormsom:v:25:y:2023:i:2:p:595-612

Access Statistics for this article

More articles in Manufacturing & Service Operations Management from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().