Original scientific paper
https://doi.org/10.2498/cit.1002465
A Generalized Island Model Based on Parallel and Cooperating Metaheuristics for Effective Large Capacitated Vehicle Routing Problem Solving
Meryem Ammi
orcid.org/0000-0001-6264-3720
; MISC laboratory, Computer Science Department, College of NTIC, Constantine 2 University, Constantine, Algeria
Salim Chikhi
; MISC laboratory, Computer Science Department, College of NTIC, Constantine2 University, Constantine, Algeria
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.
Keywords
cooperative meta-heuristics; parallel metaheuristics; vehicle routing problems; genetic algorithms; ant colony optimization
Hrčak ID:
139792
URI
Publication date:
12.6.2015.
Visits: 1.772 *