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

Electronic data

  • mcf-csop-rev

    Rights statement: This is the author’s version of a work that was accepted for publication in European Journal of Operational Research. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in European Journal of Operational Research, 251, 1, 2015 DOI: 10.1016/j.ejor.2015.11.001

    Accepted author manuscript, 365 KB, PDF document

    Available under license: CC BY-NC-ND: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License

Links

Text available via DOI:

View graph of relations

Stronger multi-commodity flow formulations of the (capacitated) sequential ordering problem

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Published

Standard

Stronger multi-commodity flow formulations of the (capacitated) sequential ordering problem. / Letchford, Adam; Salazar Gonzalez, Juan Jose.
In: European Journal of Operational Research, Vol. 251, No. 1, 16.05.2016, p. 74-84.

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Harvard

APA

Vancouver

Letchford A, Salazar Gonzalez JJ. Stronger multi-commodity flow formulations of the (capacitated) sequential ordering problem. European Journal of Operational Research. 2016 May 16;251(1):74-84. Epub 2015 Nov 10. doi: 10.1016/j.ejor.2015.11.001

Author

Bibtex

@article{04206abcd4c84e868739e3184182fc21,
title = "Stronger multi-commodity flow formulations of the (capacitated) sequential ordering problem",
abstract = "The sequential ordering problem (SOP) is the generalisation of the asymmetric travelling salesman problem in which there are precedence relations between pairs of nodes. Hernandez & Salazar introduced a multi-commodity flow (MCF) formulation for a generalisation of the SOP in which the vehicle has a limited capacity. We strengthen this MCF formulation by fixing variables and adding valid equations. We then use polyhedral projection, together with some known results on flows, cuts and metrics, to derive new families of strong valid inequalities for both problems. Finally, we give computational results, which show that our findings yield good lower bounds in practice.",
keywords = "sequential ordering, travelling salesman problem, multi-commodity flows, metrics, polyhedral combinatorics",
author = "Adam Letchford and {Salazar Gonzalez}, {Juan Jose}",
note = "This is the author{\textquoteright}s version of a work that was accepted for publication in European Journal of Operational Research. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in European Journal of Operational Research, 251, 1, 2015 DOI: 10.1016/j.ejor.2015.11.001",
year = "2016",
month = may,
day = "16",
doi = "10.1016/j.ejor.2015.11.001",
language = "English",
volume = "251",
pages = "74--84",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier Science B.V.",
number = "1",

}

RIS

TY - JOUR

T1 - Stronger multi-commodity flow formulations of the (capacitated) sequential ordering problem

AU - Letchford, Adam

AU - Salazar Gonzalez, Juan Jose

N1 - This is the author’s version of a work that was accepted for publication in European Journal of Operational Research. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in European Journal of Operational Research, 251, 1, 2015 DOI: 10.1016/j.ejor.2015.11.001

PY - 2016/5/16

Y1 - 2016/5/16

N2 - The sequential ordering problem (SOP) is the generalisation of the asymmetric travelling salesman problem in which there are precedence relations between pairs of nodes. Hernandez & Salazar introduced a multi-commodity flow (MCF) formulation for a generalisation of the SOP in which the vehicle has a limited capacity. We strengthen this MCF formulation by fixing variables and adding valid equations. We then use polyhedral projection, together with some known results on flows, cuts and metrics, to derive new families of strong valid inequalities for both problems. Finally, we give computational results, which show that our findings yield good lower bounds in practice.

AB - The sequential ordering problem (SOP) is the generalisation of the asymmetric travelling salesman problem in which there are precedence relations between pairs of nodes. Hernandez & Salazar introduced a multi-commodity flow (MCF) formulation for a generalisation of the SOP in which the vehicle has a limited capacity. We strengthen this MCF formulation by fixing variables and adding valid equations. We then use polyhedral projection, together with some known results on flows, cuts and metrics, to derive new families of strong valid inequalities for both problems. Finally, we give computational results, which show that our findings yield good lower bounds in practice.

KW - sequential ordering

KW - travelling salesman problem

KW - multi-commodity flows

KW - metrics

KW - polyhedral combinatorics

U2 - 10.1016/j.ejor.2015.11.001

DO - 10.1016/j.ejor.2015.11.001

M3 - Journal article

VL - 251

SP - 74

EP - 84

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 1

ER -