In-Depth Analysis of Pricing Problem Relaxations for the Capacitated Arc-Routing Problem

Claudia Bode () and Stefan Irnich ()
Additional contact information
Claudia Bode: Johannes Gutenberg University Mainz
Stefan Irnich: Johannes Gutenberg University Mainz

No 1212, Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz

Abstract: Recently, Bode and Irnich (‘Cut-First Branch-and-Price-Second for the Capacitated Arc-Routing Problem’, Operations Research, 2012, doi: 10.1287/opre.1120.1079) presented a cut-first branch-and-price-second algorithm for solving the capacitated arc-routing problem (CARP). The fundamental difference to other approaches from the literature 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 for solving 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, theoretical complexity results, and comprehensive computational tests on standard benchmark problems. We will show that a systematic variation of different relaxations provides a powerful approach to solve knowingly hard instances of the CARP to proven optimality.

Keywords: CARP; column generation; branch-and-price; pricing problem; relaxations (search for similar items in EconPapers)
Pages: 57 page
Date: 2012-11-17
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_1212.pdf First version, 2012 (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:jgu:wpaper:1212

Access Statistics for this paper

More papers in Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz Contact information at EDIRC.
Bibliographic data for series maintained by Research Unit IPP ().