Provably Good Region Partitioning for On-Time Last-Mile Delivery

John Gunnar Carlsson (), Sheng Liu (), Nooshin Salari () and Han Yu ()
Additional contact information
John Gunnar Carlsson: Epstein Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, California 90089
Sheng Liu: Rotman School of Management, University of Toronto, Toronto, Ontario M5S 3E6, Canada
Nooshin Salari: Donadeo Innovation Center for Engineering, University of Alberta, Edmonton, Alberta T6G 1H9, Canada; DeGroote School of Business, McMaster University, Hamilton, Ontario L8S 4M4, Canada
Han Yu: Epstein Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, California 90089

Operations Research, 2024, vol. 72, issue 1, 91-109

Abstract: On-time last-mile delivery is expanding rapidly as people expect faster delivery of goods ranging from grocery to medicines. Managing on-time delivery systems is challenging because of the underlying uncertainties and combinatorial nature of the routing decision. In practice, the efficiency of such systems also hinges on the driver’s familiarity with the local neighborhood. This paper studies the optimal region partitioning policy to minimize the expected delivery time of customer orders in a stochastic and dynamic setting. We allow both the order locations and on-site service times to be random and generally distributed. This policy assigns every driver to a subregion, hence making sure drivers will only be dispatched to their own territories. We characterize the structure of the optimal partitioning policy and show its expected on-time performance converges to that of the flexible dispatching policy in heavy traffic. The optimal characterization features two insightful conditions that are critical to the on-time performance of last-mile delivery systems. We then develop partitioning algorithms with performance guarantees, leveraging ham sandwich cuts and three-partitions from discrete geometry. This algorithmic development can be of independent interest for other logistics problems. We demonstrate the efficiency of the proposed region partitioning policy via numerical experiments using synthetic and real-world data sets.

Keywords: Transportation; last-mile delivery; region partitioning; vehicle routing; queueing (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.0588 (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:oropre:v:72:y:2024:i:1:p:91-109

Access Statistics for this article

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