In-Depth Analysis of Pricing Problem Relaxations 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

Transportation Science, 2015, vol. 49, issue 2, 369-383

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

Keywords: capacitated arc-routing problem; CARP; column generation; branch-and-price; pricing problem; relaxations (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2013.0507 (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:ortrsc:v:49:y:2015:i:2:p:369-383

Access Statistics for this article

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