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.
Bibliographical noteThis 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.”
- Capacitated arc routing problem (CARP)
- local search
- memetic algorithms (MA)
- multiobjective optimization