Title of article
A new Simulated Annealing algorithm for the robust coloring problem
Author/Authors
Lara-Velazquez, Pedro Universidad Autonoma Metropolitana - Azcapotzaico - Departamento de Sistemas, Mexico , de-Ios-Cobos-Silva, Sergio G. Universidad Autonoma Metropolitana - Iztapalapa - Departamento de Ingenieria Electrica, Mexico , Gutierrez-Andrade, Miguel Angel Universidad Autonoma Metropolitana - Irtapalapa - Departamento de Ingenieria Electrica, Mexico
From page
27
To page
32
Abstract
The Robust Coloring Problem (RCP) is a generalization of the well-known Graph Coloring Problem where we seek for a solution that remains valid when extra edges are added. The RCP is used in scheduling of events with possible last-minute changes and study frequency assignments of the electromagnetic spectrum. This problem has been proved as NP-hard and in instances larger than 30 vertices, meta-heuristics are required. In this paper a Simulated Annealing Algorithm is proposed, and his performance is compared against other techniques such as GRASP, Tabu Search and Scatter Search. In the classic instances of the problem our proposal method which gives the best solutions at this moment.
Keywords
Robust coloring problem , Graph coloring , Heuristics , Simulated Annealing
Journal title
Journal of Industrial Engineering International
Journal title
Journal of Industrial Engineering International
Record number
2584765
Link To Document