Point-to-point and milk run delivery scheduling: models, complexity results, and algorithms based on Benders decomposition

Simon Emde (), Shohre Zehtabian () and Yann Disser ()
Additional contact information
Simon Emde: Aarhus University
Shohre Zehtabian: Aarhus University
Yann Disser: Technische Universität Darmstadt

Annals of Operations Research, 2023, vol. 322, issue 1, No 18, 467-496

Abstract: Abstract We consider the problem of scheduling a set of direct deliveries between a depot and multiple customers using a given heterogeneous truck fleet. The trips have time windows and weights, and they should be completed as soon after release as possible (minimization of maximum weighted flow time). Moreover, some trips can optionally be combined in predefined milk runs (i.e., round trip tours), which need not be linear combinations of the constituent direct trips, accounting, e.g., for consolidation effects because the loading dock needs to be approached only once. This problem has applications, e.g., in just-in-time, humanitarian, and military logistics. We adapt a mixed-integer programming model from the literature to this problem and show that deciding feasibility is NP-complete in the strong sense on three levels: assigning trips to trucks, selecting milk runs, and scheduling trips on each individual truck. We also show that, despite this complexity, a state-of-the-art constraint programming solver and a problem-specific approach based on logic-based Benders decomposition can solve even large instances with up to 175 trips in many cases, while the mixed-integer programming model is essentially unsolvable using commercial optimization software. We also investigate the robustness of the maximum flow time objective in the face of unforeseen delays as well as the influence of milk runs.

Keywords: Scheduling; Logistics; Benders decomposition; Direct deliveries; Maximum weighted flow time (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-022-04891-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:annopr:v:322:y:2023:i:1:d:10.1007_s10479-022-04891-1

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-022-04891-1

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().