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

摘要

The capacitated arc routing problem (CARP) is a difficult vehicle routing problem where, given an undirected graph, the objective is to minimise 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.