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.
|Number of pages
|IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics
|Early online date
|16 Feb 2011
|Published - Aug 2011
Bibliographical noteThis 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.
- Ant colony optimization (ACO)
- capacitated arc routing problem (CARP)
- combinatorial optimization
- memetic algorithms (MAs)