On the Effectiveness of Set Covering Formulations for the Vehicle Routing Problem with Time Windows

Julien Bramel and David Simchi-Levi
Additional contact information
Julien Bramel: Columbia University, New York
David Simchi-Levi: Northwestern University, Evanston, Illinois

Operations Research, 1997, vol. 45, issue 2, 295-301

Abstract: The Vehicle Routing Problem with Time Windows (VRPTW) is one of the most important problems in distribution and transportation. A classical and recently popular technique that has proven effective for solving these problems is based on formulating them as a set covering problem . The method starts by solving its linear programming relaxation , via column generation, and then uses a branch and bound strategy to find an integer solution to the set covering problem: a solution to the VRPTW. An empirically observed property is that the optimal solution value of the set covering problem is very close to its linear programming relaxation which makes the branch and bound step extremely efficient. In this paper we explain this behavior by demonstrating that for any distribution of service times, time windows, customer loads, and locations, the relative gap between fractional and integer solutions of the set covering problem becomes arbitrarily small as the number of customers increases.

Keywords: transportation; vehicle routing; vehicle routing with time windows; programming; integer; applications; linear relaxations (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations: View citations in EconPapers (15)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.45.2.295 (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:oropre:v:45:y:1997:i:2:p:295-301

Access Statistics for this article

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