| TAZ-TFM-2011-093 |
El problema del anillo-estrella
Iranzo Sanz, José Ángel
Calvete Fernández, Herminia Inmaculada (dir.)
Universidad de Zaragoza,
CIEN,
2011
Departamento de Métodos Estadísticos, Área de Estadística e Investigación Operativa
Máster Universitario en Modelización Matemática, Estadística y Computación
Resumen: El 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.
Palabra(s) clave (del autor): ring ; star ; genetic ; algorithm ; algoritmo ; genético ; evolutivo ; anillo ; rsp ; viajante
Tipo de Trabajo Académico: Trabajo Fin de Master
Notas: Resumen disponible en inglés
Enlace permanente:
El registro pertenece a las siguientes colecciones:
Trabajos académicos > Trabajos Académicos por Centro > Facultad de Ciencias
Trabajos académicos > Trabajos fin de máster