Tabu Search, Partial Elementarity, and Generalized k -Path Inequalities for the Vehicle Routing Problem with Time Windows

Guy Desaulniers (), François Lessard () and Ahmed Hadjar ()
Additional contact information
Guy Desaulniers: Department of Mathematics and Industrial Engineering, École Polytechnique de Montréal and GERAD, Montréal, Québec, Canada H3C 3A7
François Lessard: Department of Mathematics and Industrial Engineering, École Polytechnique de Montréal and GERAD, Montréal, Québec, Canada H3C 3A7
Ahmed Hadjar: Department of Mathematics and Industrial Engineering, École Polytechnique de Montréal and GERAD, Montréal, Québec, Canada H3C 3A7

Transportation Science, 2008, vol. 42, issue 3, 387-404

Abstract: The vehicle routing problem with time windows consists of delivering goods at minimum cost to a set of customers using an unlimited number of capacitated vehicles assigned to a single depot. Each customer must be visited within a prescribed time window. The most recent successful solution methods for this problem are branch-and-price-and-cut algorithms where the column generation subproblem is an elementary shortest-path problem with resource constraints (ESPPRC). In this paper, we propose new ideas having the potential to improve such a methodology. First, we develop a tabu search heuristic for the ESPPRC that allows, in most iterations, the generation of negative reduced cost columns in a short computation time. Second, to further accelerate the subproblem solution process, we propose to relax the elementarity requirements for a subset of the nodes. This relaxation, however, yields weaker lower bounds. Third, we introduce a generalization of the k -path inequalities and highlight that these generalized inequalities can, in theory, be stronger than the traditional ones. Finally, combining these ideas with the most recent advances published in the literature, we present a wide variety of computational results on the Solomon's 100-customer benchmark instances. In particular, we report solving five previously unsolved instances.

Keywords: vehicle routing; time windows; column generation; partial elementarity; tabu search; generalized k-path inequalities (search for similar items in EconPapers)
Date: 2008
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (51)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1070.0223 (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:42:y:2008:i:3:p:387-404

Access Statistics for this article

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