Por favor, use este identificador para citar o enlazar este ítem:
https://hdl.handle.net/20.500.12008/9205
Cómo citar
Registro completo de metadatos
Campo DC | Valor | Lengua/Idioma |
---|---|---|
dc.contributor.advisor | Robledo Amoza, Franco | - |
dc.contributor.author | Recoba, Rodrigo | - |
dc.date.accessioned | 2017-07-21T17:49:32Z | - |
dc.date.available | 2017-07-21T17:49:32Z | - |
dc.date.issued | 2016 | - |
dc.identifier.citation | RECOBA, Rodrigo. Diseño topológico de redes : un caso : 2-node-connected star problem [en línea] Tesis de maestría 2016 | es |
dc.identifier.issn | 0797-6410 | - |
dc.identifier.uri | http://hdl.handle.net/20.500.12008/9205 | - |
dc.description.abstract | En este trabajo se propone un nuevo problema de optimización combinatoria que denominamos Two-Node-Connected Star Problem (2NCSP), el cual, dado un grafo simple con costos de ruteo y costos de asignación, tiene como objetivo encontrar un subgrafo de costo mínimo conformado por una componente 2-nodo conexa mientras que el resto de los nodos están asignadas a la misma mediante un enlace directo. El 2NCSP es una generalización del conocido Ring Star Problem [1] el cual difiere en que la componente 2-nodo conexa tiene que tener necesariamente topología de anillo. El objetivo de este trabajo es definir formalmente el problema Two-Node-Connected Star Problem y su resolución mediante una metaheurística GRASP de buen desempeño. Se diseñaron e implementaron búsquedas locales basadas en modelos de programación lineal entera y búsquedas locales que generan movimientos tradicionales para este tipo de problemas. Los resultados obtenidos muestran una buena performance del algoritmo en relación a instancias de prueba diseñadas y publicadas por otros autores. Dichas instancias de prueba consideran grafos de entre 50 y 200 nodos de la TSPLIB, donde los costos de asignación y conexión se obtienen con un factor de ponderación de la distancia euclidiana entre los nodos. Dicho factor permite determinar que la componente 2-nodo conexa de la solución deba contener la mayoría de los nodos, o solo unos pocos. | es |
dc.format.extent | 94 p. | es |
dc.language.iso | es | es |
dc.publisher | UR.FI-INCO | es |
dc.rights | Las obras depositadas en el Repositorio se rigen por la Ordenanza de los Derechos de la Propiedad Intelectual de la Universidad de la República.(Res. Nº 91 de C.D.C. de 8/III/1994 – D.O. 7/IV/1994) y por la Ordenanza del Repositorio Abierto de la Universidad de la República (Res. Nº 16 de C.D.C. de 07/10/2014) | es |
dc.subject | Diseño topológico de redes | es |
dc.subject | Greedy Randomized Adaptive Search Procedure | es |
dc.subject | GRASP | es |
dc.subject | Metaheurísticas | es |
dc.subject | Ring Star Problem | es |
dc.subject | RSP | es |
dc.title | Diseño topológico de redes : un caso : 2-node-connected star problem | es |
dc.type | Tesis de maestría | es |
dc.contributor.filiacion | Recoba Rodrigo, Universidad de la República (Uruguay). Facultad de Ingeniería. | - |
thesis.degree.grantor | Universidad de la República (Uruguay). Facultad de Ingeniería. | es |
thesis.degree.name | Magíster en Informática | es |
dc.rights.licence | Licencia Creative Commons Atribución – No Comercial – Sin Derivadas (CC BY-NC-ND 4.0) | - |
Aparece en las colecciones: | Tesis de posgrado - Instituto de Computación |
Ficheros en este ítem:
Fichero | Descripción | Tamaño | Formato | ||
---|---|---|---|---|---|
tesis-recoba.pdf | 1,25 MB | Adobe PDF | Visualizar/Abrir |
Este ítem está sujeto a una licencia Creative Commons Licencia Creative Commons