A Hybrid Ant Colony Optimization Algorithm for the Extended Capacitated Arc Routing Problem

LN Xing, P Rohlfshagen, YW Chen, Xin Yao

Research output: Contribution to journalArticle

52 Citations (Scopus)


The capacitated arc routing problem (CARP) is representative of numerous practical applications, and in order to widen its scope, we consider an extended version of this problem that entails both total service time and fixed investment costs. We subsequently propose a hybrid ant colony optimization (ACO) algorithm (HACOA) to solve instances of the extended CARP. This approach is characterized by the exploitation of heuristic information, adaptive parameters, and local optimization techniques: Two kinds of heuristic information, arc cluster information and arc priority information, are obtained continuously from the solutions sampled to guide the subsequent optimization process. The adaptive parameters ease the burden of choosing initial values and facilitate improved and more robust results. Finally, local optimization, based on the two-opt heuristic, is employed to improve the overall performance of the proposed algorithm. The resulting HACOA is tested on four sets of benchmark problems containing a total of 87 instances with up to 140 nodes and 380 arcs. In order to evaluate the effectiveness of the proposed method, some existing capacitated arc routing heuristics are extended to cope with the extended version of this problem; the experimental results indicate that the proposed ACO method outperforms these heuristics.
Original languageEnglish
Pages (from-to)1110-1123
Number of pages14
JournalIEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)
Issue number4
Publication statusPublished - 1 Aug 2011


  • capacitated arc routing problem (CARP)
  • memetic algorithms (MAs)
  • Ant colony optimization (ACO)
  • combinatorial optimization


Dive into the research topics of 'A Hybrid Ant Colony Optimization Algorithm for the Extended Capacitated Arc Routing Problem'. Together they form a unique fingerprint.

Cite this