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

Tolga Bektas; Günes Erdogan; Stefan Røpke

doi:10.1287/trsc.1100.0352

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

Tolga Bektas, Günes Erdogan, Stefan Røpke

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

1425 Downloads (Orbit)

Abstract

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.

Original language	English
Journal	Transportation Science
Volume	45
Issue number	3
Pages (from-to)	299-316
ISSN	0041-1655
DOIs	https://doi.org/10.1287/trsc.1100.0352
Publication status	Published - 2011

Keywords

Branch-and-Cut
Integer Programming
Generalized Vehicle Routing

Access to Document

10.1287/trsc.1100.0352

Formulations and Branch-and-Cut Algorithms for the Generalized Vehicle Routing ProblemSubmitted manuscript, 311 KB

OpenUrl availability

Full text

Cite this

@article{b907b1e774824b6a82c9a98d8a6babe0,

title = "Formulations and Branch-and-Cut Algorithms for the Generalized Vehicle Routing Problem",

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

keywords = "Branch-and-Cut, Integer Programming, Generalized Vehicle Routing",

author = "Tolga Bektas and G{\"u}nes Erdogan and Stefan R{\o}pke",

year = "2011",

doi = "10.1287/trsc.1100.0352",

language = "English",

volume = "45",

pages = "299--316",

journal = "Transportation Science",

issn = "0041-1655",

publisher = "INFORMS Institute for Operations Research and the Management Sciences",

number = "3",

}

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

SN - 0041-1655

VL - 45

SP - 299

EP - 316

JO - Transportation Science

JF - Transportation Science

IS - 3

ER -