Asignación de frecuencias en telefonía celular aplicando el problema de coloracion robusta

Abstract

The Robust Coloring Problem (RCP) is a NP-Hard Problem for which fast andefficient heuristic algorithms has been developed. In this work we present as a PCRthe problem of assignment of frequencies for a cellphone grid. Some instances for thismodel are proposed and solved using a GRASP algorithm. Evidence shows that theintermittent interruptions in service can be eliminated and the overall capacity can beincreased in approximately 25%.Keywords: Graph coloring, Robust coloring problem, Heuristics, GRASP.

El Problema de Coloraci ?n Robusta (PCR), es un problema combinatorio del tipo oNP-duro del cual ya se conocen varios algoritmos heur ??sticos r ?pidos y eficientes que lo aresuelven. En el presente trabajo se plantea el problema de asignaci ?n de frecuencias opara telefon ? celular como un PCR: se proponen algunas instancias con este modelo ?apara una red de celulares y se resuelven estas instancias con un algoritmo GRASP.Los resultados indican que se pueden disminuir las interrupciones intermitentes en elservicio y adem ?s aumentar la capacidad de la red en aproximadamente un 25%. aPalabras clave: Coloraci ?n de gr ?ficas, Coloraci ?n Robusta, GRASP, Heur ? o a o ?sticas.