A Branch-and-Cut Procedure for the Vehicle Routing Problem with Time Windows

Jonathan F. Bard (), George Kontoravdis () and Gang Yu ()
Additional contact information
Jonathan F. Bard: Graduate Program in Operations Research, Department of Mechanical Engineering, The University of Texas, Austin, Texas 78712-1063
George Kontoravdis: Graduate Program in Operations Research, Department of Mechanical Engineering, The University of Texas, Austin, Texas 78712-1063
Gang Yu: Management Science and Information Systems, College of Business Administration, The University of Texas, Austin, Texas 78712

Transportation Science, 2002, vol. 36, issue 2, 250-269

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.

Date: 2002
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (23)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.36.2.250.565 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:36:y:2002:i:2:p:250-269

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().