Metaheurísticas y computación paralela para el problema de la planificación de frecuencias en redes reales de telecomunicaciones

Abstract

El problema de optimización con el que se ha trabajado en esta tesis es el de la asignación automática de frecuencias (FAP, del inglés Frequency Assigment Problem), y fue elegido, entre otras razones, tanto por su complejidad (se trata de un problema NP-Completo) como por su relevancia para la industria del sector.

El problema de optimización que surge con el FAP se debe al reducido rango de frecuencias disponible para cada red de telefonía. Debido a este hecho, no es posible asignar a cada comunicación que se establece en la red una frecuencia única, sino que los operadores deben repetir las frecuencias de que disponen múltiples veces para cubrir todas las comunicaciones que se producen entre los usuarios de la red. Sin embargo, este solapamiento de frecuencias causa interferencias que dificultan, e incluso pueden llegar a anular, dichas comunicaciones, por lo que se hace necesario realizar una planificación de frecuencias eficiente con la que se consiga maximizar el número de comunicaciones que se realizan en la red manteniendo a la vez unos mínimos aceptables en la calidad de los servicios ofrecidos.

Tras hacer una amplia revisión de los algoritmos heurísticos y metaheurísticos que parecían ajustarse mejor a los requisitos del problema descrito anteriormente, se terminó por desarrollar y ajustar un conjunto de siete metaheurísticas con el que se trató de resolver el problema de la asignación de frecuencias desde varios enfoques.

El estudio presentado en esta tesis concluyó con el diseño e implementación de una novedosa estrategia paralela que hacía uso de todas las metaheurísticas desarrolladas.

Entre las principales contribuciones aportadas por esta tesis se encuentran, por un lado, el desarrollo y evaluación de metaheurísticas que no habían sido aplicadas antes en la resolución del problema FAP, obteniéndose además resultados de muy buena calidad en todas ellas, y por otro, el diseño e implementación de una eficiente estrategia paralela (la hiperheurística basada en metaheurísticas) con la que se ha conseguido mejorar, hasta donde nosotros conocemos, cualquier resultado (tanto en tiempo como en calidad) publicado hasta la fecha en la resolución del problema de la asignación automática de frecuencia en redes reales de telecomunicaciones.