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

作者：Liu, Tiantang; Jiang, Zhibin^*; Geng, Na

来源：International Journal of Production Research, 2013, 51(10): 3075-3084.

DOI：10.1080/00207543.2012.753165

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

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.

• 出版日期2013-5-1
• 单位上海交通大学