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

Tolga Bektaş (), Güneş Erdoğan () and Stefan Røpke ()
Additional contact information
Tolga Bektaş: School of Management and Centre for Operational Research, Management Science and Information Systems (CORMSIS), University of Southampton, Highfield, Southampton SO17 1BJ, United Kingdom
Güneş Erdoğan: Industrial Engineering Department, Ozyegin University, Üsküdar, 34662 Istanbul, Turkey
Stefan Røpke: Department of Transport, Technical University of Denmark, 2800 Kgs. Lyngby, Denmark

Transportation Science, 2011, vol. 45, issue 3, 299-316

Abstract: The generalized vehicle routing problem (GVRP) consists of finding a set of routes for a number of capacitated vehicles on a graph where the vertices are partitioned into clusters with given demands, such that the total cost of travel is minimized and all demands are met. This paper describes and compares four new integer linear programming formulations for the GVRP, two based on multicommodity flow and the other two based on exponential-size sets of inequalities. Branch-and-cut algorithms are proposed for the latter two. Computational results on a large set of instances are presented.

Keywords: generalized vehicle routing; integer programming; branch-and-cut (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (20)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1100.0352 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:45:y:2011:i:3:p:299-316

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().