A Memetic Algorithm with Random Key Crossover and Modified Neighborhood Search for the Solution of Capacitated Arc Routing Problems

Capacitated Arc Routing Problem (CARP) is a well known combinatorial optimization problem and existing algorithms require numerous function evaluations to solve them. In order to develop the capability to solve dynamic CARP problems, there is a need to further improve the efficiency of these algorithms. The aim of this work is to develop an algorithm that is capable of solving CARP instances efficiently within a limited computational budget of 50,000 function (solution) evaluations. The proposed algorithm is essentially a memetic algorithm embedded with random key crossovers and a modified neighborhood search to improve its rate of convergence. The performance of the algorithm is compared with a recently proposed memetic algorithm (MAENS) across three sets of benchmarks (gdb, val, egl). The results obtained using the proposed algorithm are better for all the above instances clearly highlighting its potential use for dynamic CARP problems.