Please use this identifier to cite or link to this item: http://doi.org/10.25358/openscience-2115
Authors: Bode, Claudia
Irnich, Stefan
Title: Cut-first branch-and-price-second for the capacitated arc-routing problem
Online publication date: 15-Dec-2011
Year of first publication: 2011
Language: english
Abstract: 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.\r\nSuch 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.
DDC: 330 Wirtschaft
330 Economics
Institution: Johannes Gutenberg-Universität Mainz
Department: FB 03 Rechts- und Wirtschaftswissenschaften
Place: Mainz
ROR: https://ror.org/023b0x485
DOI: http://doi.org/10.25358/openscience-2115
URN: urn:nbn:de:hebis:77-29407
Version: Accepted version
Publication type: Zeitschriftenaufsatz
License: In Copyright
Information on rights of use: https://rightsstatements.org/vocab/InC/1.0/
Journal: Operations research
60
5
Pages or article number: 1167
1182
Publisher: INFORMS
Publisher place: Linthicum, Md.
Issue date: 2012
ISSN: 1526-5463
Publisher URL: https://doi.org/10.1287/opre.1120.1079
Publisher DOI: 10.1287/opre.1120.1079
Appears in collections:JGU-Publikationen

Files in This Item:
  File Description SizeFormat
Thumbnail
2940.pdf566.46 kBAdobe PDFView/Open