english Icono del idioma   español Icono del idioma  

Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.12008/33907 How cite
Title: Diseño topológico de redes. Caso de estudio: Capacitated m Two-Node Survivable Star Problem
Authors: Bayá Mantani, Gabriel
Obtained title: Magíster en Informática
University or service that grants the title: Universidad de la República (Uruguay). Facultad de Ingeniería
Tutor: Mauttone, Antonio
Robledo, Franco
Type: Tesis de maestría
Keywords: Diseño Topológico de Redes, Greedy Randomized Adaptive Search Procedure (GRASP), Variable Neighborhood Search (VNS), Metaheurísticas
Issue Date: 2014
Abstract: Hoy en día prácticamente todas las actividades inherentes al ser humano tienen un soporte de hardware y software que las gestiona o las controla. Los elementos de comunicaciones cumplen un papel vital en este entramado. El diseño de topologías de redes tolerantes a fallos ha pasado a tener una importancia fundamental en la infraestructura de estas redes y constituye un elemento crítico a la hora de mantener la comunicación ante la falla de un enlace o alguno de sus nodos. El problema tratado en esta tesis intenta resolver eficientemente el diseño de una red con conexiones redundantes utilizada a menudo por los operadores telefónicos y servicios de internet. Dicha red conecta un nodo principal con clientes y establece algunas normas que modelan su construcción, tales como cantidad de clientes, número de componentes y tipos de enlaces, con el fin de satisfacer restricciones técnicas y necesidades operativas. Se considera en este trabajo un problema de optimización combinatoria denominado CmTNSSP (Capacitated m Two-Node-Survivable Star Problem), una relajación del problema CmRSP (Capacitated m Ring Star Problem). La variante relajada consiste en que los anillos (rings) del problema CmRSP pueden ser componentes 2-nodo-conexas, las cuales no necesariamente deben ser ciclos. El objetivo de esta tesis consta de la especificación de un modelo de programación matemática del problema a tratar, la resolución exacta mediante un lenguaje algebraico y un solver, y la resolución aproximada del mismo a través de una metaheurística que alterna búsquedas locales que obtienen soluciones incrementalmente mejores y búsquedas locales de resolución exacta basadas en modelos de programación matemática, en particular Programación Lineal Entera. Los resultados computacionales obtenidos por los algoritmos desarrollados muestran la robustez y competitividad de los mismos, comparados con las instancias benchmark publicadas en la literatura. Así mismo los experimentos muestran la relevancia de considerar la variante concreta del problema estudiado en esta tesis.
Publisher: Udelar. FI.
ISSN: 1688-2792
Citation: Bayá Mantani, G. Diseño topológico de redes. Caso de estudio: Capacitated m Two-Node Survivable Star Problem [en línea] Tesis de maestría. Montevideo : Udelar. FI. INCO : PEDECIBA. Área Informática, 2014.
License: Licencia Creative Commons Atribución - No Comercial - Sin Derivadas (CC - By-NC-ND 4.0)
Appears in Collections:Tesis de posgrado - Instituto de Computación

Files in This Item:
File Description SizeFormat  
Bay14.pdfTesis de Maestría2,53 MBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons