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

Research output: Contribution to journalArticle

Standard

A Hybrid Ant Colony Optimization Algorithm for the Extended Capacitated Arc Routing Problem. / Xing, LN; Rohlfshagen, P; Chen, YW; Yao, Xin.

In: IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), Vol. 41, No. 4, 01.08.2011, p. 1110-1123.

Research output: Contribution to journalArticle

Harvard

APA

Vancouver

Author

Bibtex

@article{6ae34d70a29448e78b134cfbd0bf45a8,
title = "A Hybrid Ant Colony Optimization Algorithm for the Extended Capacitated Arc Routing Problem",
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.",
keywords = "capacitated arc routing problem (CARP), memetic algorithms (MAs), Ant colony optimization (ACO), combinatorial optimization",
author = "LN Xing and P Rohlfshagen and YW Chen and Xin Yao",
year = "2011",
month = aug,
day = "1",
doi = "10.1109/TSMCB.2011.2107899",
language = "English",
volume = "41",
pages = "1110--1123",
journal = "IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)",
issn = "1083-4419",
publisher = "Institute of Electrical and Electronics Engineers (IEEE)",
number = "4",

}

RIS

TY - JOUR

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

AU - Xing, LN

AU - Rohlfshagen, P

AU - Chen, YW

AU - Yao, Xin

PY - 2011/8/1

Y1 - 2011/8/1

N2 - 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.

AB - 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.

KW - capacitated arc routing problem (CARP)

KW - memetic algorithms (MAs)

KW - Ant colony optimization (ACO)

KW - combinatorial optimization

U2 - 10.1109/TSMCB.2011.2107899

DO - 10.1109/TSMCB.2011.2107899

M3 - Article

VL - 41

SP - 1110

EP - 1123

JO - IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)

JF - IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)

SN - 1083-4419

IS - 4

ER -