2-Path Cuts for the Vehicle Routing Problem with Time Windows

Niklas Kohl, Jacques Desrosiers, Oli B. G. Madsen, Marius M. Solomon and François Soumis
Additional contact information
Niklas Kohl: University of Copenhagen, Denmark
Jacques Desrosiers: École des Hautes Études Commerciales, Montréal, Quebec, Canada and GERAD
Oli B. G. Madsen: Technical University of Denmark, Copenhagen, Denmark
Marius M. Solomon: Northeastern University, Boston, Massachusetts and GERAD
François Soumis: École Polytechnique de Montréal, Montréal, Quebec, Canada and GERAD

Transportation Science, 1999, vol. 33, issue 1, 101-116

Abstract: This paper introduces a strong valid inequality, the 2-path cut, to produce better lower bounds for the vehicle routing problem with time windows. It also develops an effective separation algorithm to find such inequalities. We next incorporate them as needed in the master problem of a Dantzig–Wolfe decomposition approach. In this enhanced optimization algorithm, the coupling constraints require that each customer be serviced. The subproblem is a shortest path problem with time window and capacity constraints. We apply branch and bound to obtain integer solutions. We first branch on the number of vehicles if this is fractional, and then on the flow variables. The algorithm has been implemented and tested on problems of up to 100 customers from the Solomon datasets. It has succeeded in solving to optimality several previously unsolved problems and a new 150-customer problem. In addition, the algorithm proved faster than algorithms previously considered in the literature. These computational results indicate the effectiveness of the valid inequalities we have developed.

Date: 1999
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (99)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.33.1.101 (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:33:y:1999:i:1:p:101-116

Access Statistics for this article

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