Home > Research > Publications & Outputs > Stronger multi-commodity flow formulations of t...

Electronic data

  • 2015-mcf-cvrp-source

    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

Links

Text available via DOI:

View graph of relations

Stronger multi-commodity flow formulations of the capacitated vehicle routing problem

Research output: Contribution to journalJournal article

Published

Standard

Stronger multi-commodity flow formulations of the capacitated vehicle routing problem. / Letchford, Adam; Salazar Gonzalez, Juan Jose.

In: European Journal of Operational Research, Vol. 244, No. 3, 01.08.2015, p. 730-738.

Research output: Contribution to journalJournal article

Harvard

APA

Vancouver

Author

Letchford, Adam ; Salazar Gonzalez, Juan Jose. / Stronger multi-commodity flow formulations of the capacitated vehicle routing problem. In: European Journal of Operational Research. 2015 ; Vol. 244, No. 3. pp. 730-738.

Bibtex

@article{eb27e648bd4d466faaa426f0e5444661,
title = "Stronger multi-commodity flow formulations of the capacitated vehicle routing problem",
abstract = "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.",
keywords = "vehicle routing, multi-commodity flows, integer programming, combinatorial optimisation",
author = "Adam Letchford and {Salazar Gonzalez}, {Juan Jose}",
note = "The final, definitive version of this article has been published in the Journal, European Journal of Operational Research 244 (2), 2015, {\textcopyright} ELSEVIER. ",
year = "2015",
month = aug
day = "1",
doi = "10.1016/j.ejor.2015.02.028",
language = "English",
volume = "244",
pages = "730--738",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier Science B.V.",
number = "3",

}

RIS

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 -