Authors
Niklas Kohl, Jacques Desrosiers, Oli BG Madsen, Marius M Solomon, Francois Soumis
Publication date
1999/2
Journal
Transportation science
Volume
33
Issue
1
Pages
101-116
Publisher
INFORMS
Description
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 …
Total citations
19981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202425571615172635262222252821183518192526313319232112
Scholar articles
N Kohl, J Desrosiers, OBG Madsen, MM Solomon… - Transportation science, 1999