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

Mads Kehlet Jepsen; Simon Spoorendonk; Stefan Røpke

doi:10.1287/trsc.1110.0399

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

Mads Kehlet Jepsen
, Simon Spoorendonk
, Stefan Røpke

Research output: Contribution to journal › Journal article › Research › peer-review

1 Downloads (Orbit)

Abstract

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.

Original language	English
Journal	Transportation Science
Volume	47
Pages (from-to)	23-37
ISSN	0041-1655
DOIs	https://doi.org/10.1287/trsc.1110.0399
Publication status	Published - Feb 2013

Keywords

Vehicle routing
Two-echelon systems
Branch-and-cut

Access to Document

10.1287/trsc.1110.0399

OpenUrl availability

Check availability in DTU Findit

Cite this

@article{4bf4eb679f5d44cd9ac437bb44219b97,

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

abstract = "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.",

keywords = "Vehicle routing, Two-echelon systems, Branch-and-cut",

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

year = "2013",

month = feb,

doi = "10.1287/trsc.1110.0399",

language = "English",

volume = "47",

pages = "23--37",

journal = "Transportation Science",

issn = "0041-1655",

publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",

}

TY - JOUR

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

AU - Jepsen, Mads Kehlet

AU - Spoorendonk, Simon

AU - Røpke, Stefan

PY - 2013/2

Y1 - 2013/2

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

M3 - Journal article

SN - 0041-1655

VL - 47

SP - 23

EP - 37

JO - Transportation Science

JF - Transportation Science

ER -

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

Abstract

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this