Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time Windows

Mads Jepsen (), Bjørn Petersen (), Simon Spoorendonk () and David Pisinger ()
Additional contact information
Mads Jepsen: Department of Computer Science (DIKU), University of Copenhagen, DK-2100 Copenhagen Ø, Denmark
Bjørn Petersen: Department of Computer Science (DIKU), University of Copenhagen, DK-2100 Copenhagen Ø, Denmark
Simon Spoorendonk: Department of Computer Science (DIKU), University of Copenhagen, DK-2100 Copenhagen Ø, Denmark
David Pisinger: Department of Computer Science (DIKU), University of Copenhagen, DK-2100 Copenhagen Ø, Denmark

Operations Research, 2008, vol. 56, issue 2, 497-511

Abstract: This paper presents a branch-and-cut-and-price algorithm for the vehicle-routing problem with time windows. The standard Dantzig-Wolfe decomposition of the arc flow formulation leads to a set-partitioning problem as the master problem and an elementary shortest-path problem with resource constraints as the pricing problem. We introduce the subset-row inequalities, which are Chvatal-Gomory rank-1 cuts based on a subset of the constraints in the master problem. Applying a subset-row inequality in the master problem increases the complexity of the label-setting algorithm used to solve the pricing problem because an additional resource is added for each inequality. We propose a modified dominance criterion that makes it possible to dominate more labels by exploiting the step-like structure of the objective function of the pricing problem. Computational experiments have been performed on the Solomon benchmarks where we were able to close several instances. The results show that applying subset-row inequalities in the master problem significantly improves the lower bound and, in many cases, makes it possible to prove optimality in the root node.

Keywords: transportation; vehicle routing; programming; integer (search for similar items in EconPapers)
Date: 2008
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (147)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1070.0449 (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:56:y:2008:i:2:p:497-511

Access Statistics for this article

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