Optimizing truck driver schedules with dependent working shifts, drivers' legislation, and multiple time windows

More Info


In logistics, minimizing the resource expenses can be done by minimizing the total number of hours that each truck driver has to work. This sum of working hours is referred to as the total schedule duration for all truck drivers. Minimizing this total schedule duration is the main goal in the optimization problem that we consider. The considered minimization problem is called the Total Schedule Duration with Dependent resource, Multiple Time Windows and European drivers’ legislation problem, i.e., the TSDDMTW-EU problem. A literature study is given on this TSDDMTW-EU problem. Different solution approaches and Mixed Integer Linear Programs (MILP) are discussed regarding in the scope of our project. We compose a model for the TSDDMTW-EU problem by giving a MILP, based on a model by Kopfer and Meyer(2008). Two different modeling approaches are suggested which are assessed on their performance. Furthermore, we prove that the TSDDMTWEU problem is NP-hard, and to conclude, a heuristic is evaluated with respect to its performance in objective values. Our main research contributions can be given by the following three aspects. First, a MILP is given for the complete European drivers’ legislation. All extensions in the legislation regarding a single truck driver are included. Second, knowledge is gained on the influence of dependent truck drivers on a Total Schedule Duration problem. And finally, we prove that adding the complete European drivers’ legislation to a problem, results in a NP-hard problem.