Memetic algorithm with adaptive local search for Capacitated Arc Routing Problem

Tingting YAO, Xin YAO, Shuangshuang HAN, Yingchun WANG, Dongpu CAO, Feiyue WANG

Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Researchpeer-review

3 Citations (Scopus)


The Capacitated Arc Routing Problem (CARP) is a challenging combinatorial optimization problem with wide real world applications. Since CARP is NP-hard, many heuristic and meta-heuristic approaches have been applied to solve CARP. In this paper, a novel extension memetic approach, named MAENS-Pls is proposed to improve the state-of-the-art algorithm - Memetic Algorithm with Extended Neighbourhood Search (MAENS) for CARP, in which using an adaptive probability to optimize the frequency and depth of local search. Based on the parameter optimization on all the 8 instances, experimental studies show that the proposed algorithm can significantly improve the average performance of MAENS, and there is an increase in the robust stability and convergence reliability. Furthermore, 4 new best known solutions are found by the proposed algorithm. © 2017 IEEE.
Original languageEnglish
Title of host publicationIEEE Conference on Intelligent Transportation Systems, Proceedings, ITSC
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Print)9781538615256
Publication statusPublished - Oct 2017
Externally publishedYes

Bibliographical note

This work was supported in part by the National Natural Science Foundation of China 61501461, 61471269, 71232006, 61533019, 91520301 and 61773381; and the Early Career Development Award of SKLMCCS (Y3S9021F34).


  • Adaptive Probability
  • Capacitated Arc Routing Problem (CARP)
  • Extended Neighbourhood Search
  • Frequency and Depth of Local Search
  • Memetic Algorithm


Dive into the research topics of 'Memetic algorithm with adaptive local search for Capacitated Arc Routing Problem'. Together they form a unique fingerprint.

Cite this