2-Path Cuts for the Vehicle Routing Problem with Time Windows
- 1 February 1999
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Transportation Science
- Vol. 33 (1), 101-116
- https://doi.org/10.1287/trsc.33.1.101
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.Keywords
This publication has 16 references indexed in Scilit:
- A Unified Framework for Deterministic Time Constrained Vehicle Routing and Crew Scheduling ProblemsPublished by Springer Science and Business Media LLC ,1998
- Vehicle Routing with Time Windows: Two Optimization AlgorithmsOperations Research, 1997
- A new branching strategy for time constrained routing problems with application to backhaulingAnnals of Operations Research, 1995
- An Optimal Algorithm for the Traveling Salesman Problem with Time WindowsOperations Research, 1995
- Note on the Complexity of the Shortest Path Models for Column Generation in VRPTWOperations Research, 1994
- Optimal Solution of Vehicle Routing Problems Using Minimum K-TreesOperations Research, 1994
- Polyhedral study of the capacitated vehicle routing problemMathematical Programming, 1993
- A New Optimization Algorithm for the Vehicle Routing Problem with Time WindowsOperations Research, 1992
- Lagrangian Relaxation Methods for Solving the Minimum Fleet Size Multiple Traveling Salesman Problem with Time WindowsManagement Science, 1988
- Lagrangean relaxation for integer programmingPublished by Springer Science and Business Media LLC ,1974