Asignación de frecuencias en telefonía celular aplicando el problema de coloracion robusta
Authors
Lara Velázquez, Pedro
Gallardo López, Lizbeth
Gutiérrez Andrade, Miguel Ángel
de los Cobos Silva, Sergio Gerardo
Journal Title
Journal ISSN
Volume Title
Publisher
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.
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.