A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem

Publication: Research - peer-review › Journal article – Annual report year: 2011

Standard

A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem. / Jepsen, Mads Kehlet ; Spoorendonk, Simon ; Røpke, Stefan.

In: Transportation Science, Vol. 47, No. 1, 2013, p. 23-37.

Publication: Research - peer-review › Journal article – Annual report year: 2011

In: Transportation Science, Vol. 47, No. 1, 2013, p. 23-37.

Publication: Research - peer-review › Journal article – Annual report year: 2011

Bibtex

@article{4bf4eb679f5d44cd9ac437bb44219b97,

title = "A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem",

publisher = "Institute for Operations Research and the Management Sciences (I N F O R M S)",

author = "Jepsen, {Mads Kehlet} and Simon Spoorendonk and Stefan Røpke",

year = "2013",

volume = "47",

number = "1",

pages = "23--37",

journal = "Transportation Science",

issn = "0041-1655",

}

RIS

TY - JOUR

T1 - A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem

A1 - Jepsen,Mads Kehlet

A1 - Spoorendonk,Simon

A1 - Røpke,Stefan

AU - Jepsen,Mads Kehlet

AU - Spoorendonk,Simon

AU - Røpke,Stefan

PB - Institute for Operations Research and the Management Sciences (I N F O R M S)

PY - 2013

Y1 - 2013

N2 - This paper presents an exact method for solving the symmetric two-echelon capacitated vehicle routing problem, a transportation problem concerned with the distribution of goods from a depot to a set of customers through a set of satellite locations. The presented method is based on an edge flow model that is a relaxation and provides a valid lower bound. A specialized branching scheme is employed to obtain feasible solutions. Out of a test set of 93 instances the algorithm is able to solve 47 to optimality surpassing previous exact algorithms.

AB - This paper presents an exact method for solving the symmetric two-echelon capacitated vehicle routing problem, a transportation problem concerned with the distribution of goods from a depot to a set of customers through a set of satellite locations. The presented method is based on an edge flow model that is a relaxation and provides a valid lower bound. A specialized branching scheme is employed to obtain feasible solutions. Out of a test set of 93 instances the algorithm is able to solve 47 to optimality surpassing previous exact algorithms.

KW - Vehicle routing

KW - Two-echelon systems

KW - Branch-and-cut

U2 - 10.1287/trsc.1110.0399

DO - 10.1287/trsc.1110.0399

JO - Transportation Science

JF - Transportation Science

SN - 0041-1655

IS - 1

VL - 47

SP - 23

EP - 37

ER -