A new Simulated Annealing algorithm for the robust coloring problem

الموضوعات :

M.A Gutiérrez-Andrade ¹ (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)
P Lara-Velázquez ² (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)
S.G de-los-Cobos-Silva ³ (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)

تاريخ الإرسال : 29 الإثنين , رجب, 1436 تاريخ التأكيد : 29 الإثنين , رجب, 1436 تاريخ الإصدار : 16 الأحد , جمادى الثانية, 1428

الکلمات المفتاحية: 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.