Exact Algorithms for the Clustered Vehicle Routing Problem

Maria Battarra (), Güneş Erdoğan () and Daniele Vigo ()
Additional contact information
Maria Battarra: School of Mathematics, University of Southampton, Highfield, Southampton SO17 1BJ, United Kingdom
Güneş Erdoğan: School of Management, University of Southampton, Highfield, Southampton SO17 1BJ, United Kingdom
Daniele Vigo: Department of Electrical, Electronics, and Information Engineering, University of Bologna, 04136 Bologna, Italy

Operations Research, 2014, vol. 62, issue 1, 58-71

Abstract: This study presents new exact algorithms for the clustered vehicle routing problem (CluVRP). The CluVRP is a generalization of the capacitated vehicle routing problem (CVRP), in which the customers are grouped into clusters . As in the CVRP, all the customers must be visited exactly once, but a vehicle visiting one customer in a cluster must visit all the remaining customers therein before leaving it. Based on an exponential time preprocessing scheme, an integer programming formulation for the CluVRP is presented. The formulation is enhanced by a polynomial time graph reduction scheme. Two exact algorithms for the CluVRP, a branch and cut as well as a branch and cut and price, are presented. The computational performances of the algorithms are tested on benchmark instances adapted from the vehicle routing problem literature as well as real-world instances from a solid waste collection application.

Keywords: clusters; vehicle routing; branch and cut (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (39)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2013.1227 (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:oropre:v:62:y:2014:i:1:p:58-71

Access Statistics for this article

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