Cut-First Branch-and-Price-Second for the Capacitated Arc-Routing Problem

Claudia Bode () and Stefan Irnich ()
Additional contact information
Claudia Bode: Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz, D-55128 Mainz, Germany
Stefan Irnich: Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz, D-55128 Mainz, Germany

Operations Research, 2012, vol. 60, issue 5, 1167-1182

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

Keywords: transportation; vehicle routing; integer programming; cutting-plane and branch-and-price algorithm (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (30)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1120.1079 (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:inm:oropre:v:60:y:2012:i:5:p:1167-1182

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().