Decomposition-based memetic algorithm for multiobjective capacitated arc routing problem

Yi MEI, Ke TANG, Xin YAO

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

171 Citations (Scopus)

Abstract

The capacitated arc routing problem (CARP) is a challenging combinatorial optimization problem with many real-world applications, e.g., salting route optimization and fleet management. There have been many attempts at solving CARP using heuristic and meta-heuristic approaches, including evolutionary algorithms. However, almost all such attempts formulate CARP as a single-objective problem although it usually has more than one objective, especially considering its real-world applications. This paper studies multiobjective CARP (MO-CARP). A new memetic algorithm (MA) called decomposition-based MA with extended neighborhood search (D-MAENS) is proposed. The new algorithm combines the advanced features from both the MAENS approach for single-objective CARP and multiobjective evolutionary optimization. Our experimental studies have shown that such combination outperforms significantly an off-the-shelf multiobjective evolutionary algorithm, namely nondominated sorting genetic algorithm II, and the state-of-the-art multiobjective algorithm for MO-CARP (LMOGA). Our work has also shown that a specifically designed multiobjective algorithm by combining its single-objective version and multiobjective features may lead to competitive multiobjective algorithms for multiobjective combinatorial optimization problems. © 2006 IEEE.
Original languageEnglish
Article number5685271
Pages (from-to)151-165
Number of pages15
JournalIEEE Transactions on Evolutionary Computation
Volume15
Issue number2
Early online date10 Jan 2011
DOIs
Publication statusPublished - Apr 2011
Externally publishedYes

Bibliographical note

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

Keywords

  • Capacitated arc routing problem (CARP)
  • local search
  • memetic algorithms (MA)
  • meta-heuristics
  • multiobjective optimization

Fingerprint

Dive into the research topics of 'Decomposition-based memetic algorithm for multiobjective capacitated arc routing problem'. Together they form a unique fingerprint.

Cite this