A Branch-and-Cut Algorithm for the Soft-Clustered Vehicle-Routing Problem
Katrin Heßler () and
Stefan Irnich ()
Additional contact information
Katrin Heßler: Johannes Gutenberg-University Mainz, Germany
Stefan Irnich: Johannes Gutenberg University Mainz
No 2001, Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz
The soft-clustered vehicle-routing problem is a variant of the classical capacitated vehicle-routing problem (CVRP) in which customers are partitioned into clusters and all customers of the same cluster must be served by the same vehicle. We introduce a novel symmetric formulation of the problem in which the clustering part is modeled with an asymmetric sub-model. We solve the new model with a branch-and-cut algorithm exploiting some known valid inequalities for the CVRP that can be adapted. In addition, we derive problem-specific cutting planes and new heuristic and exact separation procedures. For square grid instances in the Euclidean plane, we provide lower-bounding techniques and a reduction scheme that is also applicable to the respective traveling salesman problem. In comprehensive computational test on standard benchmark instances, we compare the diﬀerent formulations and separation strategies in order to determine a best performing algorithmic setup. The computational results with this branch-and-cut algorithm show that several previously open instances can now be solved to proven optimality.
Keywords: vehicle routing; clustered customers; branch-and-cut (search for similar items in EconPapers)
Pages: 37 pages
New Economics Papers: this item is included in nep-cmp and nep-ure
References: View references in EconPapers View complete reference list from CitEc
Citations: Track citations by RSS feed
Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_2001.pdf First version, 2020 (application/pdf)
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
Persistent link: https://EconPapers.repec.org/RePEc:jgu:wpaper:2001
Access Statistics for this paper
More papers in Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz Contact information at EDIRC.
Bibliographic data for series maintained by Research Unit IPP ().