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

Automated summary

This article addresses the problem of scheduling direct deliveries between a depot and multiple customers using a heterogeneous truck fleet, with consideration of time windows and weights constraints, milk runs, and maximization of the weighted flow time. The authors adapt a mixed-integer programming model and prove the NP-completeness of feasibility decision-making at different levels. They also compare the performance of constraint programming solver, logic-based Benders decomposition, and commercial optimization software, and explore the robustness of the objective function and the impact of milk runs.