Back to Search Start Over

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

Authors :
Kohl, Niklas
Desrosiers, Jacques
Madsen, Oli B. G.
Solomon, Marius M.
Soumis, François
Source :
Transportation Science; Feb99, Vol. 33 Issue 1, p101, 16p, 5 Diagrams, 1 Graph
Publication Year :
1999

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. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
00411655
Volume :
33
Issue :
1
Database :
Complementary Index
Journal :
Transportation Science
Publication Type :
Academic Journal
Accession number :
4292812
Full Text :
https://doi.org/10.1287/trsc.33.1.101