Branch-Price-and-Cut for the Soft-Clustered Capacitated Arc-Routing Problem

Stefan Irnich (), Timo Hintsch () and Lone Kiilerich ()
Additional contact information
Stefan Irnich: Johannes Gutenberg University Mainz
Timo Hintsch: Johannes Gutenberg University Mainz
Lone Kiilerich: Aarhus University, Denmark

No 1911, Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz

Abstract: The soft-clustered capacitated arc-routing problem (SoftCluCARP) is a restricted variant of the classical capacitated arc-routing problem. The only additional constraint is that the set of required edges, i.e., the streets to be serviced, is partitioned into clusters and feasible routes must respect the soft-cluster constraint, that is, all required edges of the same cluster must be served by the same vehicle. In this article, we design an effective branch-price-and-cut algorithm for the exact solution of the SoftCluCARP. Its new components are a metaheuristic and branch-and-cut-based solvers for the solution of the column-generation subproblem, which is a profitable rural clustered postman tour problem. Although postman problems with these characteristics have been studied before, there is one fundamental difference here: clusters are not necessarily vertexdisjoint, which prohibits many preprocessing and modeling approaches for clustered postman problems from the literature. We present an undirected and a windy formulation for the pricing subproblem and develop and computationally compare two corresponding branch-and-cut algorithms. Cutting is also performed at the master-program level using subset-row inequalities for subsets of size up to five. For the first time, these non-robust cuts are incorporated into MIP-based routing subproblem solvers using two different modeling approaches. In several computational studies, we calibrate the individual algorithmic components. The final computational experiments prove that the branch-price-and-cut algorithm equipped with these problemtailored components is effective: The largest SoftCluCARP instances solved to optimality have more than 150 required edges or more than 50 clusters.

Keywords: Arc routing; branch-price-and-cut; branch-and-cut; districting (search for similar items in EconPapers)
New Economics Papers: this item is included in nep-cmp and nep-ure
Date: 2019-10-10
References: Add references at CitEc
Citations: Track citations by RSS feed

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

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 ().