Subset-row inequalities applied to the vehicle routing problem with time windows
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Standard
Subset-row inequalities applied to the vehicle routing problem with time windows. / Jepsen, Mads Kehlet; Petersen, Bjørn; Spoorendonk, Simon; Pisinger, David.
I: Operations Research, Bind 56, Nr. 2, 2008, s. 497–511.Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Subset-row inequalities applied to the vehicle routing problem with time windows
AU - Jepsen, Mads Kehlet
AU - Petersen, Bjørn
AU - Spoorendonk, Simon
AU - Pisinger, David
PY - 2008
Y1 - 2008
N2 - 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. Subject classifications: transportation; vehicle routing; programming; integer.
AB - 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. Subject classifications: transportation; vehicle routing; programming; integer.
KW - Faculty of Science
KW - transportation
KW - Vehicle routing
KW - Programming
KW - Integer
U2 - 10.1287/opre.1070.0449
DO - 10.1287/opre.1070.0449
M3 - Journal article
VL - 56
SP - 497
EP - 511
JO - Operations Research
JF - Operations Research
SN - 0030-364X
IS - 2
ER -
ID: 6361532