Branch-Price-and-Cut for the Soft-Clustered Capacitated Arc-Routing Problem
- Publication type:
- Journal article
- Metadata:
-
- Autoren
- Timo Hintsch
- Stefan Irnich
- Lone Kiilerich
- Autoren-URL
- https://www.webofscience.com/api/gateway?GWVersion=2&SrcApp=fis-test-1&SrcAuth=WosAPI&KeyUT=WOS:000651880500007&DestLinkType=FullRecord&DestApp=WOS_CPL
- DOI
- 10.1287/trsc.2020.1036
- Externe Identifier
- Clarivate Analytics Document Solution ID: SE2CH
- ISSN
- 0041-1655
- Ausgabe der Veröffentlichung
- 3
- Zeitschrift
- TRANSPORTATION SCIENCE
- Schlüsselwörter
- arc routing
- branch-price-and-cut
- branch-and-cut
- districting
- Paginierung
- 687 - 705
- Datum der Veröffentlichung
- 2021
- Status
- Published
- Titel
- Branch-Price-and-Cut for the Soft-Clustered Capacitated Arc-Routing Problem
- Sub types
- Article
- Ausgabe der Zeitschrift
- 55
Data source: Web of Science (Lite)
- Other metadata sources:
-
- Abstract
- <jats:p> The soft-clustered capacitated arc-routing problem (SoftCluCARP) is a variant of the classical capacitated arc-routing problem. The only additional constraint is that the set of required edges, that is, 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 vertex-disjoint, 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 nonrobust 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 problem-tailored components is effective: The largest SoftCluCARP instances solved to optimality have more than 150 required edges or more than 50 clusters. </jats:p>
- Autoren
- Timo Hintsch
- Stefan Irnich
- Lone Kiilerich
- DOI
- 10.1287/trsc.2020.1036
- eISSN
- 1526-5447
- ISSN
- 0041-1655
- Ausgabe der Veröffentlichung
- 3
- Zeitschrift
- Transportation Science
- Sprache
- en
- Paginierung
- 687 - 705
- Datum der Veröffentlichung
- 2021
- Status
- Published
- Herausgeber
- Institute for Operations Research and the Management Sciences (INFORMS)
- Herausgeber URL
- http://dx.doi.org/10.1287/trsc.2020.1036
- Datum der Datenerfassung
- 2023
- Titel
- Branch-Price-and-Cut for the Soft-Clustered Capacitated Arc-Routing Problem
- Ausgabe der Zeitschrift
- 55
Data source: Crossref
- Autoren
- Timo Hintsch
- Stefan Irnich
- Lone Kiilerich
- DOI
- 10.1287/trsc.2020.1036
- Zeitschrift
- Transp. Sci.
- Artikelnummer
- 3
- Paginierung
- 687 - 705
- Datum der Veröffentlichung
- 2021
- Titel
- Branch-Price-and-Cut for the Soft-Clustered Capacitated Arc-Routing Problem.
- Ausgabe der Zeitschrift
- 55
Data source: DBLP
- Beziehungen:
- Property of