An evolutionary approach to the multidepot capacitated Arc routing problem

Lining XING, Philipp ROHLFSHAGEN, Yingwu CHEN, Xin YAO

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

68 Citations (Scopus)


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. © 2006 IEEE.
Original languageEnglish
Article number5352249
Pages (from-to)356-374
Number of pages19
JournalIEEE Transactions on Evolutionary Computation
Issue number3
Early online date11 Dec 2009
Publication statusPublished - Jun 2010
Externally publishedYes

Bibliographical note

This work was supported by the China Scholarship Council Grant No. 2 007 103 861, the National Natural Science Foundation of China Grant Nos. 70 971 131, 70 703 036, 70 601 035, 70 801 062, and 70 901 074, and the Engineering and Physical Sciences Research Council Grant No. EP-E058884-1 for “Evolutionary Algorithms for Dynamic Optimization Problems: Design, Analysis, and Applications.”


  • Capacitated arc routing problem
  • Combinatorial optimization
  • Evolutionary algorithms
  • Time-limited service


Dive into the research topics of 'An evolutionary approach to the multidepot capacitated Arc routing problem'. Together they form a unique fingerprint.

Cite this