Rights statement: The final, definitive version of this article has been published in the Journal, European Journal of Operational Research 244 (2), 2015, © ELSEVIER.
Submitted manuscript, 324 KB, PDF document
Final published version
Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - Stronger multi-commodity flow formulations of the capacitated vehicle routing problem
AU - Letchford, Adam
AU - Salazar Gonzalez, Juan Jose
N1 - The final, definitive version of this article has been published in the Journal, European Journal of Operational Research 244 (2), 2015, © ELSEVIER.
PY - 2015/8/1
Y1 - 2015/8/1
N2 - The Capacitated Vehicle Routing Problem is a much-studied (and strongly NP-hard) combinatorial optimization problem, for which many integer programming formulations have been proposed. We present two new multi-commodity flow (MCF) formulations, and show that they dominate all of the existing ones, in the sense that their continuous relaxations yield stronger lower bounds. Moreover, we show that the relaxations can be strengthened, in pseudo-polynomial time, in such a way that all of the so-called knapsack large multistar (KLM) inequalities are satisfied. The only other relaxation known to satisfy the KLM inequalities, based on set partitioning, is strongly NP-hard to solve. Computational results demonstrate that the new MCF relaxations are significantly stronger than the previously known ones.
AB - The Capacitated Vehicle Routing Problem is a much-studied (and strongly NP-hard) combinatorial optimization problem, for which many integer programming formulations have been proposed. We present two new multi-commodity flow (MCF) formulations, and show that they dominate all of the existing ones, in the sense that their continuous relaxations yield stronger lower bounds. Moreover, we show that the relaxations can be strengthened, in pseudo-polynomial time, in such a way that all of the so-called knapsack large multistar (KLM) inequalities are satisfied. The only other relaxation known to satisfy the KLM inequalities, based on set partitioning, is strongly NP-hard to solve. Computational results demonstrate that the new MCF relaxations are significantly stronger than the previously known ones.
KW - vehicle routing
KW - multi-commodity flows
KW - integer programming
KW - combinatorial optimisation
U2 - 10.1016/j.ejor.2015.02.028
DO - 10.1016/j.ejor.2015.02.028
M3 - Journal article
VL - 244
SP - 730
EP - 738
JO - European Journal of Operational Research
JF - European Journal of Operational Research
SN - 0377-2217
IS - 3
ER -