An Evolutionary Approach to the Multidepot Capacitated Arc Routing Problem

Research output: Contribution to journalArticle

Standard

An Evolutionary Approach to the Multidepot Capacitated Arc Routing Problem. / Xing, L; Rohlfshagen, Philipp; Chen, Y; Yao, Xin.

In: IEEE Transactions on Evolutionary Computation, Vol. 14, No. 3, 01.06.2010, p. 356-374.

Research output: Contribution to journalArticle

Harvard

APA

Vancouver

Author

Bibtex

@article{ba47be949a6546dc933620f024615143,
title = "An Evolutionary Approach to the Multidepot Capacitated Arc Routing Problem",
abstract = "The capacitated arc routing problem (CARP) is a challenging vehicle routing problem with numerous real world applications. In this paper, an extended version of CARP, the multidepot capacitated arc routing problem (MCARP), is presented to tackle practical requirements. Existing CARP heuristics are extended to cope with MCARP and are integrated into a novel evolutionary framework: the initial population is constructed either by random generation, the extended random path-scanning heuristic, or the extended random Ulusoy's heuristic. Subsequently, multiple distinct operators are employed to perform selection, crossover, and mutation. Finally, the partial replacement procedure is implemented to maintain population diversity. The proposed evolutionary approach (EA) is primarily characterized by the exploitation of attributes found in near-optimal MCARP solutions that are obtained throughout the execution of the algorithm. Two techniques are employed toward this end: the performance information of an operator is applied to select from a range of operators for selection, crossover, and mutation. Furthermore, the arc assignment priority information is employed to determine promising positions along the genome for operations of crossover and mutation. The EA is evaluated on 107 instances with up to 140 nodes and 380 arcs. The experimental results suggest that the integrated evolutionary framework significantly outperforms these individual extended heuristics.",
keywords = "data mining, proteomics, negative correlation learning, bioinformatics",
author = "L Xing and Philipp Rohlfshagen and Y Chen and Xin Yao",
year = "2010",
month = jun,
day = "1",
doi = "10.1109/TEVC.2009.2033578",
language = "English",
volume = "14",
pages = "356--374",
journal = "IEEE Transactions on Evolutionary Computation",
issn = "1089-778X",
publisher = "Institute of Electrical and Electronics Engineers (IEEE)",
number = "3",

}

RIS

TY - JOUR

T1 - An Evolutionary Approach to the Multidepot Capacitated Arc Routing Problem

AU - Xing, L

AU - Rohlfshagen, Philipp

AU - Chen, Y

AU - Yao, Xin

PY - 2010/6/1

Y1 - 2010/6/1

N2 - The capacitated arc routing problem (CARP) is a challenging vehicle routing problem with numerous real world applications. In this paper, an extended version of CARP, the multidepot capacitated arc routing problem (MCARP), is presented to tackle practical requirements. Existing CARP heuristics are extended to cope with MCARP and are integrated into a novel evolutionary framework: the initial population is constructed either by random generation, the extended random path-scanning heuristic, or the extended random Ulusoy's heuristic. Subsequently, multiple distinct operators are employed to perform selection, crossover, and mutation. Finally, the partial replacement procedure is implemented to maintain population diversity. The proposed evolutionary approach (EA) is primarily characterized by the exploitation of attributes found in near-optimal MCARP solutions that are obtained throughout the execution of the algorithm. Two techniques are employed toward this end: the performance information of an operator is applied to select from a range of operators for selection, crossover, and mutation. Furthermore, the arc assignment priority information is employed to determine promising positions along the genome for operations of crossover and mutation. The EA is evaluated on 107 instances with up to 140 nodes and 380 arcs. The experimental results suggest that the integrated evolutionary framework significantly outperforms these individual extended heuristics.

AB - The capacitated arc routing problem (CARP) is a challenging vehicle routing problem with numerous real world applications. In this paper, an extended version of CARP, the multidepot capacitated arc routing problem (MCARP), is presented to tackle practical requirements. Existing CARP heuristics are extended to cope with MCARP and are integrated into a novel evolutionary framework: the initial population is constructed either by random generation, the extended random path-scanning heuristic, or the extended random Ulusoy's heuristic. Subsequently, multiple distinct operators are employed to perform selection, crossover, and mutation. Finally, the partial replacement procedure is implemented to maintain population diversity. The proposed evolutionary approach (EA) is primarily characterized by the exploitation of attributes found in near-optimal MCARP solutions that are obtained throughout the execution of the algorithm. Two techniques are employed toward this end: the performance information of an operator is applied to select from a range of operators for selection, crossover, and mutation. Furthermore, the arc assignment priority information is employed to determine promising positions along the genome for operations of crossover and mutation. The EA is evaluated on 107 instances with up to 140 nodes and 380 arcs. The experimental results suggest that the integrated evolutionary framework significantly outperforms these individual extended heuristics.

KW - data mining

KW - proteomics

KW - negative correlation learning

KW - bioinformatics

U2 - 10.1109/TEVC.2009.2033578

DO - 10.1109/TEVC.2009.2033578

M3 - Article

VL - 14

SP - 356

EP - 374

JO - IEEE Transactions on Evolutionary Computation

JF - IEEE Transactions on Evolutionary Computation

SN - 1089-778X

IS - 3

ER -