A new Simulated Annealing algorithm for the robust coloring problem

Journal of Industrial Engineering International

مقاله 4، دوره 3، شماره 5، مهر 2007، صفحه 27-32   

نویسندگان

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

¹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

²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

³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

چکیده

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.

کلیدواژه‌ها

Robust coloring problem؛ Graph coloring؛ Heuristics؛ Simulated Annealing