A new Simulated Annealing algorithm for the robust coloring problem

Subject Areas : Mathematical Optimization

M.A Gutiérrez-Andrade ¹ , P Lara-Velázquez ² , S.G de-los-Cobos-Silva ³

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

Received: 2015-05-18 Accepted : 2015-05-18 Published : 2007-07-01

Keywords: Simulated Annealing, Robust coloring problem, Graph coloring, Heuristics,

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.