In-depth analysis of pricing problem relaxations for the capacitated arc-routing problem
- Publication type:
- Journal article
- Metadata:
-
- Autoren
- Claudia Bode
- Stefan Irnich
- Sammlungen
- metadata
- ISSN
- 0041-1655
- Ausgabe der Veröffentlichung
- 2
- Zeitschrift
- Transportation science
- Schlüsselwörter
- 330 Wirtschaft
- 330 Economics
- Sprache
- eng
- Paginierung
- Seiten: 369 - 383
- Datum der Veröffentlichung
- 2015
- Herausgeber
- INFORMS
- Herausgeber URL
- http://dx.doi.org/10.1287/trsc.2013.0507
- Datum der Datenerfassung
- 2020
- Datum, an dem der Datensatz öffentlich gemacht wurde
- 2020
- Zugang
- Public
- Titel
- In-depth analysis of pricing problem relaxations for the capacitated arc-routing problem
- Ausgabe der Zeitschrift
- 49
Data source: METADATA.UB
- Other metadata sources:
-
- Autoren
- Claudia Bode
- Stefan Irnich
- Autoren-URL
- https://www.webofscience.com/api/gateway?GWVersion=2&SrcApp=fis-test-1&SrcAuth=WosAPI&KeyUT=WOS:000354704200014&DestLinkType=FullRecord&DestApp=WOS_CPL
- DOI
- 10.1287/trsc.2013.0507
- Externe Identifier
- Clarivate Analytics Document Solution ID: CI4FV
- ISSN
- 0041-1655
- Ausgabe der Veröffentlichung
- 2
- Zeitschrift
- TRANSPORTATION SCIENCE
- Schlüsselwörter
- capacitated arc-routing problem
- CARP
- column generation
- branch-and-price
- pricing problem
- relaxations
- Paginierung
- 369 - 383
- Datum der Veröffentlichung
- 2015
- Status
- Published
- Titel
- In-Depth Analysis of Pricing Problem Relaxations for the Capacitated Arc-Routing Problem
- Sub types
- Article
- Ausgabe der Zeitschrift
- 49
Data source: Web of Science (Lite)
- Abstract
- <jats:p> Recently, Bode and Irnich [Bode C, Irnich S (2012) Cut-first branch-and-price-second for the capacitated arc-routing problem. Oper. Res. 60(5):1167–1182] presented a cut-first branch-and-price-second algorithm for solving the capacitated arc-routing problem (CARP). The fundamental difference to other approaches for exactly solving the CARP is that the entire algorithm works directly on the typically sparse underlying graph representing the street network. This enables the use of highly efficient dynamic programming-based pricing algorithms to solve the column-generation subproblem also known as the pricing problem. The contribution of this paper is the in-depth analysis of the CARP pricing problem and its possible relaxations, including the construction of new labeling algorithms for their solution and comprehensive computational tests on standard benchmark problems. We show that a systematic variation of different relaxations provides a powerful approach to solve knowingly hard instances of the CARP to proven optimality. </jats:p>
- Autoren
- Claudia Bode
- Stefan Irnich
- DOI
- 10.1287/trsc.2013.0507
- eISSN
- 1526-5447
- ISSN
- 0041-1655
- Ausgabe der Veröffentlichung
- 2
- Zeitschrift
- Transportation Science
- Sprache
- en
- Paginierung
- 369 - 383
- Datum der Veröffentlichung
- 2015
- Status
- Published
- Herausgeber
- Institute for Operations Research and the Management Sciences (INFORMS)
- Herausgeber URL
- http://dx.doi.org/10.1287/trsc.2013.0507
- Datum der Datenerfassung
- 2023
- Titel
- In-Depth Analysis of Pricing Problem Relaxations for the Capacitated Arc-Routing Problem
- Ausgabe der Zeitschrift
- 49
Data source: Crossref
- Autoren
- Claudia Bode
- Stefan Irnich
- DOI
- 10.1287/trsc.2013.0507
- Zeitschrift
- Transp. Sci.
- Artikelnummer
- 2
- Paginierung
- 369 - 383
- Datum der Veröffentlichung
- 2015
- Titel
- In-Depth Analysis of Pricing Problem Relaxations for the Capacitated Arc-Routing Problem.
- Ausgabe der Zeitschrift
- 49
Data source: DBLP
- Beziehungen:
- Property of