Formulations and Branch-and-Cut Algorithms for the Generalized Vehicle Routing Problem

Publication: Research - peer-reviewJournal article – Annual report year: 2011

Standard

Formulations and Branch-and-Cut Algorithms for the Generalized Vehicle Routing Problem. / Bektas, Tolga; Erdogan, Günes; Røpke, Stefan.

In: Transportation Science, Vol. 45, No. 3, 2011, p. 299-316.

Publication: Research - peer-reviewJournal article – Annual report year: 2011

Harvard

APA

CBE

MLA

Vancouver

Author

Bektas, Tolga; Erdogan, Günes; Røpke, Stefan / Formulations and Branch-and-Cut Algorithms for the Generalized Vehicle Routing Problem.

In: Transportation Science, Vol. 45, No. 3, 2011, p. 299-316.

Publication: Research - peer-reviewJournal article – Annual report year: 2011

Bibtex

@article{b907b1e774824b6a82c9a98d8a6babe0,
title = "Formulations and Branch-and-Cut Algorithms for the Generalized Vehicle Routing Problem",
keywords = "Branch-and-Cut, Integer Programming, Generalized Vehicle Routing",
author = "Tolga Bektas and Günes Erdogan and Stefan Røpke",
year = "2011",
doi = "10.1287/trsc.1100.0352",
volume = "45",
pages = "299--316",
journal = "Transportation Science",
issn = "0041-1655",
publisher = "Institute for Operations Research and the Management Sciences (I N F O R M S)",
number = "3",

}

RIS

TY - JOUR

T1 - Formulations and Branch-and-Cut Algorithms for the Generalized Vehicle Routing Problem

AU - Bektas,Tolga

AU - Erdogan,Günes

AU - Røpke,Stefan

PY - 2011

Y1 - 2011

N2 - The Generalized Vehicle Routing Problem (GVRP) consists of nding a set of routes for a number of vehicles with limited capacities on a graph with the vertices partitioned into clusters with given demands such that the total cost of travel is minimized and all demands are met. This paper offers four new integer linear programming formulations for the GVRP, two based on multicommodity flow and the other two based on exponential sets of inequalities. Branch-and-cut algorithms are proposed for the latter two. Computational results on a large set of instances are presented.

AB - The Generalized Vehicle Routing Problem (GVRP) consists of nding a set of routes for a number of vehicles with limited capacities on a graph with the vertices partitioned into clusters with given demands such that the total cost of travel is minimized and all demands are met. This paper offers four new integer linear programming formulations for the GVRP, two based on multicommodity flow and the other two based on exponential sets of inequalities. Branch-and-cut algorithms are proposed for the latter two. Computational results on a large set of instances are presented.

KW - Branch-and-Cut

KW - Integer Programming

KW - Generalized Vehicle Routing

U2 - 10.1287/trsc.1100.0352

DO - 10.1287/trsc.1100.0352

M3 - Journal article

VL - 45

SP - 299

EP - 316

JO - Transportation Science

T2 - Transportation Science

JF - Transportation Science

SN - 0041-1655

IS - 3

ER -