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

作者：Xing, Li Ning^*; Rohlfshagen, Philipp; Chen, Ying Wu; Yao, Xin

来源：IEEE Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics , 2011, 41(4): 1110-1123.

DOI：10.1109/TSMCB.2011.2107899

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

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-8
• 单位中国人民解放军国防科学技术大学