MAENS+: A Divide-and-Conquer Based Memetic Algorithm for Capacitated Arc Routing Problem

The Capacitated Arc Routing Problem (CARP) has attracted much attention during the last few years due to its wide applications in real life. A Memetic Algorithm with Extended Neighborhood Search (MAENS) was developed for solving this kind of problem. A powerful local search operator, the so-called MS operator, was introduced and plays an important role in MAENS. But the main disadvantage is the high computational cost due to the large enumerative number of selecting route groups. In this paper, we propose an improved approach for MAENS with a divide-and-conquer strategy, named MAENS+, which divides a large graph into small sub graphs in order to decrease enumerative number so as to reduce the computational cost. An adaptive method is used for choosing parameters during dividing. Experimental results show that MAENS+ manages to obtain the same level of solution quality as MAENS with much less computational time.