000006554 001__ 6554 000006554 005__ 20170831220337.0 000006554 037__ $$aTAZ-TFM-2011-093 000006554 041__ $$aspa 000006554 1001_ $$aIranzo Sanz, José Ángel 000006554 24500 $$aEl problema del anillo-estrella 000006554 260__ $$aZaragoza$$bUniversidad de Zaragoza$$c2011 000006554 506__ $$aby-nc-sa$$bCreative Commons$$c3.0$$uhttp://creativecommons.org/licenses/by-nc-sa/3.0/ 000006554 500__ $$aResumen disponible en inglés 000006554 520__ $$aEl problema del anillo-estrella (Ring Star Problem, RSP) consiste en diseñar un ciclo simple (anillo) que pasa por un cierto nodo raiz y asignar cada nodo no visitado por el anillo al nodo mas cercano del anillo. El objetivo es minimizar el coste del ciclo más el coste de las asignaciones. Este problema tiene numerosas aplicaciones prácticas en el campo del diseño urbano de redes de telecomunicaciones. Este trabajo se divide en cuatro capítulos. El primero sirve como introducción y justificación del problema, y plantea la relación del RSP con su aplicación práctica en el diseño de redes de telecomunicaciones. En el segundo capítulo, se describe formalmente el problema, se detallan algunas de las formulaciones como un problema de programación lineal entera que se han propuesto en la literatura y se describen los algoritmos utilizados para resolver dichos problemas. Finalmente, se revisan algunas variantes del RSP. En el tercer capítulo, se propone una transformación del RSP en un problema del viajante generalizado (GTSP) que permite resolver el RSP aplicando las técnicas y algoritmos existentes para el GTSP. Por último, en el cuarto capítulo, se propone un algoritmo evolutivo para resolver de forma heurística el RSP y se muestran algunos de los resultados experimentales obtenidos a partir de una implementación del algoritmo en C++, cuyo código se presenta en el anexo. 000006554 521__ $$aMáster Universitario en Modelización Matemática, Estadística y Computación 000006554 540__ $$aDerechos regulados por licencia Creative Commons 000006554 6531_ $$aring 000006554 6531_ $$astar 000006554 6531_ $$agenetic 000006554 6531_ $$aalgorithm 000006554 6531_ $$aalgoritmo 000006554 6531_ $$agenético 000006554 6531_ $$aevolutivo 000006554 6531_ $$aanillo 000006554 6531_ $$arsp 000006554 6531_ $$aviajante 000006554 700__ $$aCalvete Fernández, Herminia Inmaculada$$edir. 000006554 7102_ $$aUniversidad de Zaragoza$$bMétodos Estadísticos$$cEstadística e Investigación Operativa 000006554 8560_ $$f534927@celes.unizar.es 000006554 8564_ $$s1550832$$uhttps://zaguan.unizar.es/record/6554/files/TAZ-TFM-2011-093.pdf$$yMemoria (spa) 000006554 8564_ $$s87198$$uhttps://zaguan.unizar.es/record/6554/files/TAZ-TFM-2011-093_ANE.pdf$$yAnexos (spa) 000006554 909CO $$ooai:zaguan.unizar.es:6554$$ptrabajos-fin-master$$pdriver 000006554 950__ $$a 000006554 980__ $$aTAZ$$bTFM$$cCIEN