A Dynamic Programming Heuristic for the Vehicle Routing Problem with Time Windows and European Community Social Legislation

In practice, apart from the problem of vehicle routing, schedulers also face the problem of finding feasible driver schedules complying with complex restrictions on drivers' driving and working hours. To address this complex interdependent problem of vehicle routing and break scheduling, we propose a restricted dynamic programming heuristic for the vehicle routing problem with time windows and the full European social legislation on drivers' driving and working hours. The problem we consider includes all rules in this legislation, whereas in the literature only a basic set of rules has been addressed. In addition to this basic set of rules, the legislation contains a set of modifications that allow for more flexibility. To include the legislation in the restricted dynamic programming heuristic, we propose a break scheduling heuristic. Computational results show that our method finds solutions to benchmark instances---which only consider the basic set of rules---with 18% fewer vehicles and 5% less travel distance than state-of-the-art approaches. Moreover, our results are obtained with significantly less computational effort. Furthermore, the results show that including a set of rules on drivers' working hours---which has been generally ignored in the literature---has a significant impact on the resulting vehicle schedules: 3.9% more vehicle routes and 1.0% more travel distances are needed. Finally, using the modified rules of the legislation leads to an additional reduction of 4% in the number of vehicles and of 1.5% in travel distances. Therefore, the modified rules should be exploited in practice.