TAZ-TFM-2011-093


El problema del anillo-estrella

Iranzo Sanz, José Ángel
Calvete Fernández, Herminia Inmaculada (dir.)

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

Máster Universitario en Modelización Matemática, Estadística y Computación

Abstract: 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.


Free keyword(s): 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

Creative Commons License

El registro pertenece a las siguientes colecciones:
Academic Works > Trabajos Académicos por Centro > facultad-de-ciencias
Academic Works > End-of-master works




Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)