Towards a Better Understanding of Genetic operators for Ordering Optimization -Application to the Capacitated Vehicle Routing Problem

International audience ; Genetic Algorithms (GA) have long been used for ordering optimization problems with some considerable efforts to improve their exploration and exploitation abilities. A great number of GA implementations have been proposed varying from GAs applying simple or advanced variation operators to hybrid GAs combined with different heuristics. In this work, we propose a short review of genetic operators for ordering optimization with a classification according to the information used in the reproduction step. Crossover operators could be position ("blind") operators or heuristic operators. Mutation operators could be applied randomly or using local optimization. After studying the contribution of each class on solving two benchmark instances of the Capacitated Vehicle Routing Problem (CVRP), we explain how to combine the variation operators to allow simultaneously a better exploration of the search space with higher exploitation. We then propose the random and the balanced hybridization of the operators' classes. The hybridization strategies are applied to solve 24 CVRP benchmark instances. Results are analyzed and compared to demonstrate the role of each class of operators in the evolution process.