Improved lower bounds and exact algorithm for the capacitated arc routing problem

Enrico Bartolini, Jean François Cordeau, Gilbert Laporte

Research output: Contribution to journalArticlepeer-review

24 Citations (Scopus)

Abstract

In the capacitated arc routing problem (CARP), a subset of the edges of an undirected graph has to be serviced at least cost by a fleet of identical vehicles in such a way that the total demand of the edges serviced by each vehicle does not exceed its capacity. This paper describes a new lower bounding method for the CARP based on a set partitioning-like formulation of the problem with additional cuts. This method uses cut-and-column generation to solve different relaxations of the problem, and a new dynamic programming method for generating routes. An exact algorithm based on the new lower bounds was also implemented to assess their effectiveness. Computational results over a large set of classical benchmark instances show that the proposed method improves most of the best known lower bounds for the open instances, and can solve several of these for the first time.

Original languageEnglish
Pages (from-to)409-452
Number of pages44
JournalMathematical Programming
Volume137
Issue number1-2
DOIs
Publication statusPublished - 2013

Keywords

  • Arc routing
  • Column generation
  • Dynamic programming
  • Set partitioning
  • Valid inequalities

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Improved lower bounds and exact algorithm for the capacitated arc routing problem'. Together they form a unique fingerprint.

Cite this