Accelerating Local Search in a Memetic Algorithm for the Capacitated Vehicle Routing Problem

摘要

Memetic algorithms usually employ long running times, since local search is performed every time a new solution is generated. Acceleration of a memetic algorithm requires focusing on local search, the most time-consuming component. This paper describes the application of two acceleration techniques to local search in a memetic algorithm: caching of values of objective function for neighbours and forbidding moves which could increase distance between solutions. Computational experiments indicate that in the capacitated vehicle routing problem the usage of these techniques is not really profitable, because of cache management overhead and implementation issues.