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

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.