Scheduling direct deliveries with time windows to minimise truck fleet size and customer waiting times

摘要

This paper tackles the operational problem of scheduling direct deliveries from a single source (e.g. a distribution centre) to multiple customers (e.g. assembly plants). The problem consists of scheduling a set of given round trips such that each trip is processed exactly once within its time window and the employed truck fleet is as small as possible. Moreover, as a secondary objective, customer waiting times should be minimal. Such planning problems arise in many industries like, for instance, the automotive industry, where just-in-time parts are often shipped via direct delivery to OEMs. We propose two different mixed-integer programming models for this problem, discuss similarities to classic routing and scheduling problems from the literature, identify a subproblem that is solvable in polynomial time and propose suitable heuristics. In a computational study, the proposed procedures are shown to perform well both on newly generated instances as well as those from the literature. We also show that minimising waiting times is an adequate measure to make schedules more robust in the face of unforeseen disturbances.