Memetic algorithm with extended neighborhood search for capacitated arc routing problems

Ke TANG, Yi MEI, Xin YAO

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

175 Citations (Scopus)

Abstract

The capacitated arc routing problem (CARP) has attracted much attention during the last few years due to its wide applications in real life. Since CARP is NP-hard and exact methods are only applicable to small instances, heuristic and metaheuristic methods are widely adopted when solving CARP. In this paper, we propose a memetic algorithm, namely memetic algorithm with extended neighborhood search (MAENS), for CARP. MAENS is distinct from existing approaches in the utilization of a novel local search operator, namely Merge-Split (MS). The MS operator is capable of searching using large step sizes, and thus has the potential to search the solution space more efficiently and is less likely to be trapped in local optima. Experimental results show that MAENS is superior to a number of state-of-the-art algorithms, and the advanced performance of MAENS is mainly due to the MS operator. The application of the MS operator is not limited to MAENS. It can be easily generalized to other approaches. © 2009 IEEE.
Original languageEnglish
Pages (from-to)1151-1166
Number of pages16
JournalIEEE Transactions on Evolutionary Computation
Volume13
Issue number5
Early online date12 Aug 2009
DOIs
Publication statusPublished - Oct 2009
Externally publishedYes

Bibliographical note

This work was supported in part by the Engineering and Physical Sciences Research Council under Grant EP/E058884/1 on “Evolutionary Algorithms for Dynamic Optimization Problems: Design, Analysis and Applications,” by the National Natural Science Foundation of China under Grants 60533020 and U0835002, and by the Fund for Foreign Scholars in University Research and Teaching Programs, Grant B07033.

Keywords

  • Capacitated arc routing problem (CARP)
  • Evolutionary optimization
  • Local search
  • Memetic algorithm
  • Metaheuristic search

Fingerprint

Dive into the research topics of 'Memetic algorithm with extended neighborhood search for capacitated arc routing problems'. Together they form a unique fingerprint.

Cite this