Resolución del problema de asignación de terminales en redes de telecomunicaciones usando métodos heurísticos

Resumen

En los últimos años, hemos asistido a un enorme crecimiento de las redes de comunicación. Esto se debe a que son ampliamente utilizadas en todos los ámbitos de la vida, y esta tendencia continúa aumentando. La investigación en el campo de redes informáticas de comunicación también ha tenido un crecimiento explosivo debido a una gran variedad de problemas de optimización combinatoria. Uno de estos problemas es el problema de la asignación de terminales (Terminal Assignment Problem - TAP). Asignación de terminales es una tarea importante en las redes de telecomunicaciones. Esta tarea puede aumentar la capacidad de las redes, y disminuir el costo de las conexiones entre terminales y concentradores. El objetivo de TAP implica la construcción de una red de costo mínimo entre un conjunto específico de terminales y de concentradores. Una buena solución para TAP debe mantener las distancias pequeñas entre los concentradores y los terminales asignados a ellos, sin exceder la capacidad de cualquier concentrador. Además, una solución buena también debe mantener una distribución equilibrada de terminales por concentradores. La dificultad de este problema es una motivación para utilizar diferentes algoritmos de aproximación. Meta-heurísticas son una clase de métodos aproximados diseñados para optimizar los complejos problemas de optimización combinatoria, donde las heurísticas clásicas no han podido ser eficientes (Dreo et al., 2006). En la literatura, hay diferentes meta-heurísticas que utilizan diferentes conceptos, derivados de: heurísticas clásicas, inteligencia artificial, evolución biológica, sistemas neuronales, inteligencia de enjambres y mecánica estadística. Entre los algoritmos más utilizados se encuentran métodos basados en el Enfriamiento Simulado, Búsqueda Tabú, Algoritmos Evolutivos, Algoritmos de Inteligencia de Enjambres y sus híbridos. En esta tesis, se exploran varias meta-heurísticas aplicadas al problema TAP. Los resultados demuestran la eficacia de estos algoritmos. En esta tesis es también descrita la aplicación de métodos diferentes aplicados al TAP a otros problemas directamente relacionados con TAP, con el fin de demostrar que los algoritmos se pueden generalizar a otros problemas de optimización combinatoria.