Paper Info
Title
A Branch-and-Cut Procedure for the Vehicle Routing Problem with Time Windows
Abstract
This paper addresses the problem of finding the minimum number of vehicles required to visit a set of nodes subject to time window and capacity constraints. The fleet is homogeneous and is located at a common depot. Each node requires the same type of service. An exact method is introduced based on branch and cut. In the computations, ever increasing lower bounds on the optimal solution are obtained by solving a series of relaxed problems that incorporate newly found valid inequalities. Feasible solutions or upper bounds are obtained with the help of greedy randomized adaptive search procedure (GRASP). A wide variety of cuts is introduced to tighten the linear programming (LP) relaxation of the original mixed-integer program. To find violated cuts, it is necessary to solve a separation problem. A substantial portion of the paper is aimed at describing the heuristics developed for this purpose. A new approach for obtaining feasible solutions from the LP relaxation is also discussed. Numerical results for standard 50- and 100-node benchmark problems are reported.
Year
DOI
Venue
2002
10.1287/trsc.36.2.250.565
Transportation Science
Keywords
DocType
Volume
vehicle routing problem,linear programming,exact method,common depot,100-node benchmark problem,separation problem,time windows,branch-and-cut procedure,lower bound,lp relaxation,feasible solution,capacity constraint,greedy randomized adaptive search,linear program,greedy randomized adaptive search procedure,optimization,routing,mixed integer programming,type of service,upper bound,branch and cut,algorithms
Journal
36
Issue
ISSN
Citations 
2
0041-1655
45
PageRank 
References 
Authors
2.44
17
3
Name
Order
Citations
PageRank
Jonathan F. Bard11428144.29
George Kontoravdis211610.01
Gang Yu343134.83