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

Abstract: 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 different 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
Date: 2020-01-08
New Economics Papers: this item is included in nep-cmp and nep-ure
References: Add references at CitEc
Citations:

Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_2001.pdf First version, 2020 (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: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 ().