European Driver Rules in Vehicle Routing with Time Windows

Eric Prescott-Gagnon (), Guy Desaulniers (), Michael Drexl () and Louis-Martin Rousseau ()
Additional contact information
Eric Prescott-Gagnon: École Polytechnique de Montréal, Montréal, Québec H3C 3A7, Canada, and GERAD, Montréal, Québec H3T 2A7, Canada
Guy Desaulniers: École Polytechnique de Montréal, Montréal, Québec H3C 3A7, Canada, and GERAD, Montréal, Québec H3T 2A7, Canada
Michael Drexl: Fraunhofer-Centre for Applied Research on Supply Chain Services SCS, 90411 Nuremberg, Germany
Louis-Martin Rousseau: École Polytechnique de Montréal and CIRRELT, Montréal, Québec H3C 3AT, Canada

Transportation Science, 2010, vol. 44, issue 4, 455-473

Abstract: As of April 2007, the European Union has new regulations concerning driver working hours. These rules force the placement of breaks and rests into vehicle routes when consecutive driving or working time exceeds certain limits. This paper proposes a large neighborhood search method for the vehicle routing problem with time windows and driver regulations. In this method, neighborhoods are explored using a column generation heuristic that relies on a tabu search algorithm for generating new columns (routes). Checking route feasibility after inserting a customer into a route in the tabu search algorithm is not an easy task. To do so, we model all feasibility rules as resource constraints, develop a label-setting algorithm to perform this check, and show how it can be used efficiently to validate multiple customer insertions into a given existing route. We test the overall solution method on modified Solomon instances and report computational results that clearly show the efficiency of our method compared to two other existing heuristics.

Keywords: vehicle routing; time windows; driver rules; large neighborhood search; heuristic column generation; resource constraints (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (40)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1100.0328 (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:455-473

Access Statistics for this article

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