Cooperating memes for vehicle routing problems

Abstract

To date, algorithms that are designed for solving different Vehicle Routing Problem (VRP) benchmarks usually incorporate domain driven biases of various forms. This makes an algorithm effective and efficient for some VRP benchmark sets but not necessarily on others. This paper presents a memetic algorithm for Capacitated Vehicle Routing Problems (CVRPs), which is specially designed for applying intense local search methods or merries. The main contribution of this work is a VRP domain-specific cooperating multi-strategy individual learning procedure. The MA finds high-quality solutions by using cooperating individual learning strategies or merries, each having different learning roles and search features. Experiments on several sets of VRP benchmarks of various problem characteristics showed that the algorithm is better or more competitive when compared with a number of state-of-the-art memetic algorithms and metaheuristics for CVRPs. © 2011 ICIC INTERNATIONAL.