2-path cuts for the vehicle routing problem with time windows

2-path cuts for the vehicle routing problem with time windows

0.00 Avg rating0 Votes
Article ID: iaor2001743
Country: United States
Volume: 33
Issue: 1
Start Page Number: 101
End Page Number: 116
Publication Date: Feb 1999
Journal: Transportation Science
Authors: , , , ,
Keywords: programming: branch and bound, networks
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.

Reviews

Required fields are marked *. Your email address will not be published.