Cut-first branch-and-price-second for the capacitated arc-routing problem
- Publikationstyp:
- Zeitschriftenaufsatz
- Metadaten:
-
- Autoren
- Claudia Bode
- Stefan Irnich
- Sammlungen
- metadata
- ISSN
- 1526-5463
- Ausgabe der Veröffentlichung
- 5
- Zeitschrift
- Operations research
- Schlüsselwörter
- 330 Wirtschaft
- 330 Economics
- Sprache
- eng
- Paginierung
- Seiten: 1167 - 1182
- Datum der Veröffentlichung
- 2012
- Herausgeber
- Informs
- Herausgeber URL
- http://dx.doi.org/10.1287/opre.1120.1079
- Datum der Datenerfassung
- 2020
- Datum, an dem der Datensatz öffentlich gemacht wurde
- 2020
- Zugang
- Public
- Titel
- Cut-first branch-and-price-second for the capacitated arc-routing problem
- Ausgabe der Zeitschrift
- 60
Datenquelle: METADATA.UB
- Andere Metadatenquellen:
-
- Autoren
- Claudia Bode
- Stefan Irnich
- Autoren-URL
- https://www.webofscience.com/api/gateway?GWVersion=2&SrcApp=fis-test-1&SrcAuth=WosAPI&KeyUT=WOS:000310926500012&DestLinkType=FullRecord&DestApp=WOS_CPL
- DOI
- 10.1287/opre.1120.1079
- Externe Identifier
- Clarivate Analytics Document Solution ID: 035ER
- ISSN
- 0030-364X
- Ausgabe der Veröffentlichung
- 5
- Zeitschrift
- OPERATIONS RESEARCH
- Paginierung
- 1167 - 1182
- Datum der Veröffentlichung
- 2012
- Status
- Published
- Titel
- Cut-First Branch-and-Price-Second for the Capacitated Arc-Routing Problem
- Sub types
- Article
- Ausgabe der Zeitschrift
- 60
Datenquelle: Web of Science (Lite)
- Abstract
- <jats:p>This paper presents the first full-fledged branch-and-price (bap) algorithm for the capacitated arc-routing problem (CARP). Prior exact solution techniques either rely on cutting planes or the transformation of the CARP into a node-routing problem. The drawbacks are either models with inherent symmetry, dense underlying networks, or a formulation where edge flows in a potential solution do not allow the reconstruction of unique CARP tours. The proposed algorithm circumvents all these drawbacks by taking the beneficial ingredients from existing CARP methods and combining them in a new way. The first step is the solution of the one-index formulation of the CARP in order to produce strong cuts and an excellent lower bound. It is known that this bound is typically stronger than relaxations of a pure set-partitioning CARP model. Such a set-partitioning master program results from a Dantzig-Wolfe decomposition. In the second phase, the master program is initialized with the strong cuts, CARP tours are iteratively generated by a pricing procedure, and branching is required to produce integer solutions. This is a cut-first bap-second algorithm and its main function is, in fact, the splitting of edge flows into unique CARP tours.</jats:p>
- Autoren
- Claudia Bode
- Stefan Irnich
- DOI
- 10.1287/opre.1120.1079
- eISSN
- 1526-5463
- ISSN
- 0030-364X
- Ausgabe der Veröffentlichung
- 5
- Zeitschrift
- Operations Research
- Sprache
- en
- Paginierung
- 1167 - 1182
- Datum der Veröffentlichung
- 2012
- Status
- Published
- Herausgeber
- Institute for Operations Research and the Management Sciences (INFORMS)
- Herausgeber URL
- http://dx.doi.org/10.1287/opre.1120.1079
- Datum der Datenerfassung
- 2024
- Titel
- Cut-First Branch-and-Price-Second for the Capacitated Arc-Routing Problem
- Ausgabe der Zeitschrift
- 60
Datenquelle: Crossref
- Autoren
- Claudia Bode
- Stefan Irnich
- DOI
- 10.1287/opre.1120.1079
- Zeitschrift
- Oper. Res.
- Artikelnummer
- 5
- Paginierung
- 1167 - 1182
- Datum der Veröffentlichung
- 2012
- Titel
- Cut-First Branch-and-Price-Second for the Capacitated Arc-Routing Problem.
- Ausgabe der Zeitschrift
- 60
Datenquelle: DBLP
- Author's licence
- InCopyright
- Autoren
- Claudia Bode
- Stefan Irnich
- Hosting institution
- Universitätsbibliothek Mainz
- Sammlungen
- JGU-Publikationen
- Resource version
- Accepted version
- URN
- urn:nbn:de:hebis:77-29407
- DOI
- 10.1287/opre.1120.1079
- File(s) embargoed
- false
- Open access
- true
- ISSN
- 1526-5463
- Ausgabe der Veröffentlichung
- 5
- Zeitschrift
- Operations research
- Schlüsselwörter
- 330 Wirtschaft
- 330 Economics
- Sprache
- eng
- Open access status
- Open Access
- Paginierung
- 1167 - 1182
- Datum der Veröffentlichung
- 2011
- Public URL
- https://openscience.ub.uni-mainz.de/handle/20.500.12030/2117
- Herausgeber
- INFORMS
- Herausgeber URL
- https://doi.org/10.1287/opre.1120.1079
- Datum der Datenerfassung
- 2011
- Datum, an dem der Datensatz öffentlich gemacht wurde
- 2011
- Zugang
- Public
- Titel
- Cut-first branch-and-price-second for the capacitated arc-routing problem
- Ausgabe der Zeitschrift
- 60
Files
2940.pdf
Datenquelle: OPENSCIENCE.UB
- Beziehungen:
- Eigentum von