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

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). Moreo...

Full description

Saved in:
Bibliographic Details
Published in:Annals of operations research 2023-03, Vol.322 (1), p.467-496
Main Authors: Emde, Simon, Zehtabian, Shohre, Disser, Yann
Format: Article
Language:English
Subjects:
Algorithms
Benders decomposition
Business and Management
Combinatorics
Complexity
Delivery of goods
Delivery scheduling
Distribution
Integer programming
Loading bays
Methods
Milk
Mixed integer
Operations research
Operations Research/Decision Theory
Optimization
Original Research
Scheduling (Management)
Theory of Computation
Windows (intervals)
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0254-5330
1572-9338
DOI:10.1007/s10479-022-04891-1