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

A. L. Kok (), C. M. Meyer (), H. Kopfer () and J. M. J. Schutten ()
Additional contact information
A. L. Kok: Algorithmic R&D, ORTEC, 2800 AL Gouda, The Netherlands
C. M. Meyer: Faculty of Business Studies and Economics, University of Bremen, 28359 Bremen, Germany
H. Kopfer: Faculty of Business Studies and Economics, University of Bremen, 28359 Bremen, Germany
J. M. J. Schutten: Operational Methods for Production and Logistics, University of Twente, 7500 AE Enschede, The Netherlands

Transportation Science, 2010, vol. 44, issue 4, 442-454

Abstract: 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.

Keywords: vehicle routing and scheduling; restricted dynamic programming; break scheduling; European Community (EC) regulations on driving time; drivers' working hours (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (37)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1100.0331 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:44:y:2010:i:4:p:442-454

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().