El Problema del m-Anillo Estrella

Vidal Lana, Ignacio
Calvete Fernández, Herminia Inmaculada (dir.)

Universidad de Zaragoza, CIEN, 2016
Métodos Estadísticos department, Estadística e Investigación Operativa area

Graduado en Matemáticas

Abstract: El Problema del m-Anillo Estrella (en su versión en inglés, Capacitated m-Ring Star Problem, o CmRSP) consiste en diseñar un conjunto de ciclos o anillos, cada uno incluyendo un depósito central, un número limitado de clientes, y algunos posibles puntos llamados puntos de transición, que pueden ser usados para ahorrar costes de conexión. Es un problema de optimización dentro de la teoría de grafos, y tiene como objetivo encontrar el diseño óptimo de una red de telecomunicaciones, usando la topología del anillo por su capacidad de evitar la pérdida de conexión de un nodo de comunicaciones aunque haya una avería en alguna de las conexiones. En concreto, la red consistirá de m anillos (conjuntos de nodos conectados, formando un camino simple cerrado) incluyendo cada uno de ellos el nodo central o depósito, un conjunto de clientes o puntos de transición (puntos por los que puede pasar la conexión abaratando los costes de la red total) y las conexiones entre ellos. Al mismo tiempo, a estos nodos se podrán conectar otros clientes de forma directa, lo que explica el nombre de «m-anillo estrella». Esta memoria se divide en tres capítulos. El primero de ellos toma como referencia el artículo The Capacitated m-Ring-Star Problem, de R. Baldacci et al., donde fue planteado por primera vez el problema. En el capítulo se da una introducción al problema y se presenta su planteamiento. El segundo capítulo toma como referencia el artículo A heuristic procedure for the Capacitated m-Ring-Star Problem, de Z. Naji-Azimi et al., y en él se estudia un algoritmo heurístico propuesto por los autores, capaz de dar en tiempos mucho más razonables resultados muy cercanos, a veces superiores, a los mejores conocidos. En el tercer capítulo, se presenta el algoritmo basado en programación lineal entera (PLE) presentado por Z. Naji-Azimi et al. Este capítulo se divide en tres secciones. En la primera se introduce el algoritmo, en la segunda se describe de forma resumida, y en la tercera y última sección se describe de forma detallada cada uno de los procedimientos que forman el algoritmo. Por último, en el cuarto capítulo, se presenta la codificación, realizada por quien presenta esta memoria, del algoritmo heurístico del capítulo dos, en el lenguaje de programación C++. El programa es descrito en detalle, usando una sección propia para sus variables y otra para sus funciones o subrutinas, y termina con un cuadro de resultados de ejemplos conocidos del CmRSP.

Tipo de Trabajo Académico: Trabajo Fin de Grado