A Generalized Island Model Based on Parallel and Cooperating Metaheuristics for Effective Large Capacitated Vehicle Routing Problem Solving

Abstract

Capacitated Vehicle Routing Problem (CVRP) is among transportation problems that are of the foremost concerns in logistics. Ensuring an effective product distribution over a large distribution network while reducing the required costs represents the scope of the present work. A synergic and interactive environment of parallel meta-heuristics is developed using a generalized island model to deal with large instances of CVRP. In the proposed model, cooperative meta-heuristics, namely genetic algorithms (GA) and ant colony optimization algorithms (ACO), are organized into archipelagoes. They communicate synchronously, globally and locally by exchanging solutions. In order to handle properly the migration of solutions, either between archipelagoes or between islands within the same archipelago, appropriate selection and replacement policies are adopted. Furthermore, the proposed approach uses other new features including a new binary solution representation and different optimization process (i.e GA, ACO) on each island. To prove the efficiency of the present work, tests over the well-known set of benchmarks, comparative studies and experimental analysis have been conducted.