The capacitated arc routing problem is a challenging combinatorial optimization problem with numerous real-world applications. In recent years, several multi-objective optimization algorithms have been applied to minimize both the total cost and makespan for capacitated arc routing problems, among which the decomposition-based memetic algorithm with extended neighborhood search has shown promising results. In this paper, we propose an improved decomposition-based memetic algorithm with extended neighborhood search, called D-MAENS2, which uses a novel method to construct a gene pool to measure and improve the diversity of solutions in decision variable space. Additionally, D-MAENS2 is capable of adapting online its hyper-parameters to various problem instances. Experimental studies show that our novel D-MAENS2 significantly outperforms D-MAENS on 81 benchmark instances and shows outstanding performance on instances of large size. © 2020 IEEE.
|Title of host publication
|2020 IEEE Symposium Series on Computational Intelligence, SSCI 2020
|Institute of Electrical and Electronics Engineers Inc.
|Number of pages
|Published - 1 Dec 2020
- Capacitated arc routing problem
- local search
- memetic algorithms
- multiobjective optimization