A hybrid ant colony optimization algorithm for the extended capacitated arc routing problem

Li-Ning XING, Philipp ROHLFSHAGEN, Ying-Wu CHEN, Xin YAO

Research output: Journal PublicationsJournal Article (refereed)peer-review

60 Citations (Scopus)

Abstract

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. © 2011 IEEE.
Original languageEnglish
Article number5713263
Pages (from-to)1110-1123
Number of pages14
JournalIEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics
Volume41
Issue number4
Early online date16 Feb 2011
DOIs
Publication statusPublished - Aug 2011
Externally publishedYes

Bibliographical note

This work was supported in part by the National Natural Science Foundation of China under Grants 70971131 and 70801062 and in part by Engineering and Physical Sciences Research Council Grant EP/E058884/1 on “Evolutionary Algorithm for Dynamic Optimisation Problems: Design, Analysis and Applications.” This paper was recommended by Associate Editor J. Wang.

Keywords

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

Fingerprint

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