A memetic algorithm with iterated local search for the capacitated arc routing problem

Abstract

The capacitated arc routing problem (CARP) is a difficult vehicle routing problem, where given an undirected graph, the objective is to minimize the total cost of all vehicle tours that serve all required edges under vehicle capacity constraints. In this paper, a memetic algorithm with iterated local search (MAILS) is proposed to solve this problem. The proposed MAILS incorporates a new crossover operator, i.e., the longest common substring crossover (LCSX), an iterated local search (ILS) and a perturbation mechanism into the framework of the memetic algorithm (MA). The proposed MAILS is evaluated on the CARP benchmark instances and computational results show that the MAILS is very competitive.

Keywords:

• Capacitated arc routing problem
• Memetic algorithm
• Iterated local search
• Longest common substring crossover

Acknowledgements

This work was supported by the National Natural Science Foundation of China under research Grant No. 70872077 and the National Natural Science Foundation of China - Research Grants Council of Hong Kong (NSFC-RGC) joint research projects (No. 70831160527). We thank the editor and the anonymous referees for their valuable comments.