Home > Research > Publications & Outputs > A new branch-and-cut algorithm for the capacita...

Research

Links

Text available via DOI:

Keywords

View graph of relations

A new branch-and-cut algorithm for the capacitated vehicle routing problem

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

A new branch-and-cut algorithm for the capacitated vehicle routing problem. / Letchford, A N; Eglese, R W; Lysgaard, J.
In: Mathematical Programming, Vol. 100, No. 2, 2004, p. 423-445.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Letchford, AN, Eglese, RW & Lysgaard, J 2004, 'A new branch-and-cut algorithm for the capacitated vehicle routing problem', Mathematical Programming, vol. 100, no. 2, pp. 423-445. https://doi.org/10.1007/s10107-003-0481-8

APA

Letchford, A. N., Eglese, R. W., & Lysgaard, J. (2004). A new branch-and-cut algorithm for the capacitated vehicle routing problem. Mathematical Programming, 100(2), 423-445. https://doi.org/10.1007/s10107-003-0481-8

Vancouver

Letchford AN, Eglese RW, Lysgaard J. A new branch-and-cut algorithm for the capacitated vehicle routing problem. Mathematical Programming. 2004;100(2):423-445. doi: 10.1007/s10107-003-0481-8

Author

Letchford, A N ; Eglese, R W ; Lysgaard, J. / A new branch-and-cut algorithm for the capacitated vehicle routing problem. In: Mathematical Programming. 2004 ; Vol. 100, No. 2. pp. 423-445.

Bibtex

@article{449351c7bf364c948b4c54d679666f53,
title = "A new branch-and-cut algorithm for the capacitated vehicle routing problem",
abstract = "We present a new branch-and-cut algorithm for the capacitated vehicle routing problem (CVRP). The algorithm uses a variety of cutting planes, including capacity, framed capacity, generalized capacity, strengthened comb, multistar, partial multistar, extended hypotour inequalities, and classical Gomory mixed-integer cuts. For each of these classes of inequalities we describe our separation algorithms in detail. Also we describe the other important ingredients of our branch-and-cut algorithm, such as the branching rules, the node selection strategy, and the cut pool management. Computational results, for a large number of instances, show that the new algorithm is competitive. In particular, we solve three instances (B-n50-k8, B-n66-k9 and B-n78-k10) of Augerat to optimality for the first time.",
keywords = "vehicle routing, branch-and-cut, combinatorial optimisation",
author = "Letchford, {A N} and Eglese, {R W} and J Lysgaard",
year = "2004",
doi = "10.1007/s10107-003-0481-8",
language = "English",
volume = "100",
pages = "423--445",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer-Verlag GmbH and Co. KG",
number = "2",

}

RIS

TY - JOUR

T1 - A new branch-and-cut algorithm for the capacitated vehicle routing problem

AU - Letchford, A N

AU - Eglese, R W

AU - Lysgaard, J

PY - 2004

Y1 - 2004

N2 - We present a new branch-and-cut algorithm for the capacitated vehicle routing problem (CVRP). The algorithm uses a variety of cutting planes, including capacity, framed capacity, generalized capacity, strengthened comb, multistar, partial multistar, extended hypotour inequalities, and classical Gomory mixed-integer cuts. For each of these classes of inequalities we describe our separation algorithms in detail. Also we describe the other important ingredients of our branch-and-cut algorithm, such as the branching rules, the node selection strategy, and the cut pool management. Computational results, for a large number of instances, show that the new algorithm is competitive. In particular, we solve three instances (B-n50-k8, B-n66-k9 and B-n78-k10) of Augerat to optimality for the first time.

AB - We present a new branch-and-cut algorithm for the capacitated vehicle routing problem (CVRP). The algorithm uses a variety of cutting planes, including capacity, framed capacity, generalized capacity, strengthened comb, multistar, partial multistar, extended hypotour inequalities, and classical Gomory mixed-integer cuts. For each of these classes of inequalities we describe our separation algorithms in detail. Also we describe the other important ingredients of our branch-and-cut algorithm, such as the branching rules, the node selection strategy, and the cut pool management. Computational results, for a large number of instances, show that the new algorithm is competitive. In particular, we solve three instances (B-n50-k8, B-n66-k9 and B-n78-k10) of Augerat to optimality for the first time.

KW - vehicle routing

KW - branch-and-cut

KW - combinatorial optimisation

U2 - 10.1007/s10107-003-0481-8

DO - 10.1007/s10107-003-0481-8

M3 - Journal article

VL - 100

SP - 423

EP - 445

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 2

ER -