Optimization Online


Comparative Analysis of Capacitated Arc Routing Formulations for Branch-Cut-and-Price Algorithms

Diego Pecin(diego.pecin***at***isye.gatech.edu)
Eduardo Uchoa(uchoa***at***producao.uff.br)

Abstract: The current best exact algorithms for the Capacitated Arc Routing Problem are based on the combination of cut and column generation. This work presents a deep theoretical investigation of the formulations behind those algorithms, classifying them and pointing similarities and differences, advantages and disadvantages. In particular, we discuss which families of cuts and branching strategies are suitable for each alternative and their pricing complexities. That analysis is used for justifying key decisions on constructing a new branch-cut-and-price algorithm, that combines several features picked from the capacitated arc routing literature with some features adapted from the most successful recent algorithms for node routing. The computational experiments show that the resulting algorithm is indeed effective and can solve almost all open instances from the classical benchmark sets.

Keywords: Arc Routing; Column Generation; Cutting Planes; Algorithmic Engineering

Category 1: Combinatorial Optimization

Category 2: Integer Programming

Category 3: Applications -- OR and Management Sciences (Transportation )

Citation: @techreport{PecinUchoa2017, Author = {Diego Pecin and Eduardo Uchoa}, Title = {Comparative Analysis of Capacitated Arc Routing Formulations for Branch-Cut-and-Price Algorithms}, Institution = {Cadernos do LOGIS-UFF}, Address = {Niter{\'o}i, Brazil}, Number = {L-2017-6}, pages = {37}, month = {September}, Year = {2017} }

Download: [PDF]

Entry Submitted: 09/05/2017
Entry Accepted: 09/13/2017
Entry Last Modified: 09/05/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society