A new Simulated Annealing algorithm for the robust coloring problem

Authors

1 Titular Professor, Departamento de Ingeniería Eléctrica, Universidad Autónoma Metropolitana – Iztapalapa, Av. San Rafael Atlixco No. 186, Col. Vicentina, Del. Iztapalapa, México, D.F., C.P. 09340

2 Associate Professor, Departamento de Sistemas, Universidad Autónoma Metropolitana – Azcapotzalco. Av. San Pablo No. 180, Col. Reynosa Tamaulipas, Del. Azcapotzalco, México, D.F., C.P. 02200

3 Titular Profesor, Departamento de Ingeniería Eléctrica, Universidad Autónoma Metropolitana – Iztapalapa, Av. San Rafael Atlixco No. 186, Col. Vicentina, Del. Iztapalapa, México, D.F., C.P. 09340

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 tech-niques 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