A new branch-and-cut algorithm for capacitated vehicle routing problems

Management Science

Keywords

vehicle routing, branch-and-cut, separation

Research output: Working paper

Published

Standard

A new branch-and-cut algorithm for capacitated vehicle routing problems. / Eglese, R W ; Letchford, A N; Lysgaard, J.
Lancaster University: The Department of Management Science, 2003. (Management Science Working Paper Series).

Research output: Working paper

Harvard

Eglese, RW , Letchford, AN & Lysgaard, J 2003 'A new branch-and-cut algorithm for capacitated vehicle routing problems' Management Science Working Paper Series, The Department of Management Science, Lancaster University.

APA

Eglese, R. W., Letchford, A. N., & Lysgaard, J. (2003). A new branch-and-cut algorithm for capacitated vehicle routing problems. (Management Science Working Paper Series). The Department of Management Science.

Vancouver

Eglese RW , Letchford AN, Lysgaard J. A new branch-and-cut algorithm for capacitated vehicle routing problems. Lancaster University: The Department of Management Science. 2003. (Management Science Working Paper Series).

Author

Eglese, R W ; Letchford, A N ; Lysgaard, J. / A new branch-and-cut algorithm for capacitated vehicle routing problems. Lancaster University : The Department of Management Science, 2003. (Management Science Working Paper Series).

Bibtex

@techreport{d9f24d51d06c46bebfce2468b6939538,

title = "A new branch-and-cut algorithm for capacitated vehicle routing problems",

abstract = "We present a new branch-and-cut algorithm for the well-known capacitated vehicle routing problem (CVRP). The algorithm uses a variety of cutting planes, including capacity, framed 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 of Augerat to optimality for the first time.",

keywords = "vehicle routing, branch-and-cut, separation",

author = "Eglese, {R W} and Letchford, {A N} and J Lysgaard",

note = "This was eventually published as: J. Lysgaard, A.N. Letchford & R.W. Eglese (2004) A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math. Program., 100(2), 423-445.",

year = "2003",

language = "English",

series = "Management Science Working Paper Series",

publisher = "The Department of Management Science",

type = "WorkingPaper",

institution = "The Department of Management Science",

}

RIS

TY - UNPB

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

AU - Eglese, R W

AU - Letchford, A N

AU - Lysgaard, J

N1 - This was eventually published as: J. Lysgaard, A.N. Letchford & R.W. Eglese (2004) A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math. Program., 100(2), 423-445.

PY - 2003

Y1 - 2003

N2 - We present a new branch-and-cut algorithm for the well-known capacitated vehicle routing problem (CVRP). The algorithm uses a variety of cutting planes, including capacity, framed 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 of Augerat to optimality for the first time.

AB - We present a new branch-and-cut algorithm for the well-known capacitated vehicle routing problem (CVRP). The algorithm uses a variety of cutting planes, including capacity, framed 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 of Augerat to optimality for the first time.

KW - vehicle routing

KW - branch-and-cut

KW - separation

M3 - Working paper

T3 - Management Science Working Paper Series

BT - A new branch-and-cut algorithm for capacitated vehicle routing problems

PB - The Department of Management Science

CY - Lancaster University

ER -

Research

Keywords