A Memetic Algorithm Based on Decomposition and Extended Search for Multi-Objective Capacitated Arc Routing Problem

摘要

The capacitated arc routing problem is a classical NP-hard problem to solve in the field of combinatorial optimization. In recent years, due to its extensive use in our daily life, its importance has gradually emerged. Multi-objective capacitated arc routing problem (MO-CARP) is more close to real life, so it arouses widespread concern. The Multi-objective evolution algorithm based on decomposition provides a suitable frame for solving MO-CARP. In this paper, a memetic algorithm based on decomposition and extended search (ED-MAENS) is proposed to deal with MO-CARP. Firstly, decompose the MO-CARP into many single-objective sub-problems using weight vectors. Then assign represent solution for each single-objective problem. To make sure that each single-objective problems can get a reasonable represent solution, the rank conception is proposed. After that, MAENS algorithm is adopted to solve each single-objective problem using the information of its neighborhood. Finally, we proposed an extended search operator to enlarge the searching space to improve the solution quality. The new proposed algorithm is evaluated on medium and large scale instance set and experimental results demonstrate the proposed method can obtain the better non-dominated solution than compared algorithms especially on large-scale instance.