000059074 001__ 59074 000059074 005__ 20170127103257.0 000059074 037__ $$aTAZ-TFG-2016-3218 000059074 041__ $$aspa 000059074 1001_ $$aVidal Lana, Ignacio 000059074 24200 $$aThe Capacitated m-Ring Star Problem 000059074 24500 $$aEl Problema del m-Anillo Estrella 000059074 260__ $$aZaragoza$$bUniversidad de Zaragoza$$c2016 000059074 506__ $$aby-nc-sa$$bCreative Commons$$c3.0$$uhttp://creativecommons.org/licenses/by-nc-sa/3.0/ 000059074 520__ $$aEl 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. 000059074 521__ $$aGraduado en Matemáticas 000059074 540__ $$aDerechos regulados por licencia Creative Commons 000059074 700__ $$aCalvete Fernández, Herminia Inmaculada$$edir. 000059074 7102_ $$aUniversidad de Zaragoza$$bMétodos Estadísticos$$cEstadística e Investigación Operativa 000059074 8560_ $$f631091@celes.unizar.es 000059074 8564_ $$s253552$$uhttps://zaguan.unizar.es/record/59074/files/TAZ-TFG-2016-3218.pdf$$yMemoria (spa) 000059074 909CO $$ooai:zaguan.unizar.es:59074$$pdriver$$ptrabajos-fin-grado 000059074 950__ $$a 000059074 951__ $$adeposita:2017-01-26 000059074 980__ $$aTAZ$$bTFG$$cCIEN