Memetic algorithm based on extension step and statistical filtering for large-scale capacitated arc routing problems

摘要

The capacitated arc routing problem (CARP) is a classical NP-Hard combinatorial optimization problem. In this paper, we present a memetic algorithm based on Extension step and Statistical filtering for Large-Scale CARP (ESMAENS) which has improvements in both the global search strategy and the local search strategy. Firstly, ESMAENS adopts the Route Distance Grouping decomposition scheme (RDG) to decompose the large-scale CARP into some independent sub-problems. Then, the initial population would evolve into a new group by using the Evolutionary Algorithm. Furthermore, ESMAENS introduces the extension step search strategy to search the potential solutions around the current solution. As a result, with the increase of the iteration number, it avoids getting to the premature convergence. Meanwhile, the diversity of the population can be increased. Finally, in the local search strategy, the statistical filter is used to filter out some solutions and make the algorithm get the lower bound at a faster convergence rate with a high stability. Compared with RDG-MAENS, experimental results on Beullen ’ C , D , E , F , egl and EGL - G test set show that ESMAENS has a better convergence rate, and the stability of solutions obtained is improved. Furthermore, ESMAENS achieves a global search for the solutions. Especially for the large-scale EGL - G test set, ESMAENS can converge to a lower bound at a faster convergence rate, and it is suitable for solving large-scale CARP.