Algoritmos heurísticos y metaheurísticos para el problema de localización de regeneradores.

Abstract

El objetivo de este proyecto es resolver un problema que tiene una aplicación real en el mundo de las telecomunicaciones. Es un problema de optimización en el que se pretende, mediante el uso de algoritmos, encontrar soluciones que permitan ahorrar recursos a las empresas que trabajan en el sector. Dado un grupo de ciudades, con unas distancias entre ellas se quiere comunicar a todas con todas, de manera que cada ciudad encuentre un camino para comunicarse con cualquier otra. Este problema se modela informáticamente con una estructura de grafo, donde las ciudades son los nodos y los caminos junto con las distancias entre estas son las aristas del grafo. Dada la atenuación de las señales eléctricas u ópticas de transmisión de información se deben utilizar aparatos que refuercen la calidad de estas, y permitan alcanzar nuevos y más lejanos destinos. Estos aparatos son los regeneradores o repetidores de la señal y deben colocarse en los nodos del grafo. Es en esta colocación es en la que se centrarán los algoritmos, con el objetivo de colocar el mínimo número posible de regeneradores, ya que son relativamente caros, para poder comunicar completamente todos los nodos entre sí. Se han utilizado algoritmos de construcción de soluciones basados en algoritmos heurísticos los cuales construyen soluciones relativamente buenas y en ocasiones óptimas, pero en muchas ocasiones estas soluciones no son las mejores para el problema y pueden ser optimizadas. Para ello se han utilizado también algoritmos heurísticos de optimización, como la búsqueda local o el re-encaminamiento de trayectorias. Estos algoritmos reciben soluciones factibles construidas previamente e intentan mejorarlas, es decir, partiendo de ellas intentan encontrar una solución mejor. Los algoritmos anteriormente comentados son la base para construir algoritmos metaheurísticos, como es el caso de los algoritmos GRASP (Greedy Randomized Adaptative Search Procedures) y GRASP-PR (Greedy Randomized Adaptative Search Procedures with Path Relinking). Los algoritmos metaheurísticos son más completos y complejos que los heurísticos. Utilizan a los heurísticos y consiguen explorar un rango mayor de posibles soluciones para una instancia de un problema dado.