A new Simulated Annealing algorithm for the robust coloring problem
محورهای موضوعی : Mathematical OptimizationM.A Gutiérrez-Andrade 1 , P Lara-Velázquez 2 , S.G de-los-Cobos-Silva 3
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
کلید واژه: Simulated Annealing, Robust coloring problem, Graph coloring, Heuristics,
چکیده مقاله :
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.
