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.