On integrating an Iterated Variable Neighborhood Search within a bi-objective Genetic Algorithm: Sum Coloring of Graphs Case Application

The minimum sum coloring of graphs is a variant of the classical graph coloring problem which is known to be NP-hard. The problem consists on minimizing the sum colorings of different graph vertices. In this paper, we propose a new bi-objective model for the underlying problem. We also propose for the resolution a hybrid schema which combines a bi-objective genetic algorithm with an Iterated Variable Neighborhood Search. The proposed approach relies on the use of different dedicated evolutionary operators mainly crossover and mutation. We also note two important features of the Variable Neighborhood Search: the use of destroy/repair method for shaking step and a multi-neighborhood search. Combined methods led us to preliminary promising results.