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.
Original language | English |
---|---|
Pages (from-to) | 58-71 |
Number of pages | 15 |
Journal | Operations Research |
Volume | 62 |
Issue number | 1 |
Early online date | 13 Jan 2014 |
DOIs | |
Publication status | Published - 13 Jan 2014 |
Keywords
- clusters
- vehicle routing
- branch and cut
Fingerprint
Dive into the research topics of 'Exact Algorithms for the Clustered Vehicle Routing Problem'. Together they form a unique fingerprint.Profiles
-
Maria Battarra
- Management - Professor
- Information, Decisions & Operations - Director of Studies MSc in Management suite
- Made Smarter Innovation: Centre for People-Led Digitalisation
- IAAPS: Propulsion and Mobility
- Centre for Climate Adaptation & Environment Research (CAER)
- Centre for Digital, Manufacturing & Design (dMaDe)
Person: Research & Teaching, Affiliate staff
-
Gunes Erdogan
- Management - Professor
- Information, Decisions & Operations - Director of Studies MSc in Business Analytics
- Centre for Healthcare Innovation and Improvement
- Institute for Mathematical Innovation (IMI)
- Smart Warehousing and Logistics Systems
Person: Research & Teaching, Researcher