Magíster en Gestión de Operaciones / todos desarrollados en estudios previos. Para este tipo de problemas, la formEn este trabajo se desarrolla un nuevo enfoque para resolver el problema de diseño de redes no capacitadas con fuente única en base a la combinación de méulación multicommodity que desagrega las demandas ha sido utilizada extensamente y se ha probado que se obtienen mejores resultados que con la formulación de flujo en redes clásica al comparar sus relajaciones lineales. En este trabajo se muestra que dicha formulación puede mejorar aún más al duplicar y dirigir arcos no-dirigidos. Con este concepto, se desarrolla un método de ascenso dual específico para el problema de diseño con fuente única que entrega cotas inferiores de buena calidad. Dentro de este método se propone un esquema de clasificación de commodities que permite una representación reducida del problema y que entrega mejores cotas inferiores en las instancias testeadas.
Adicionalmente, este método también entrega una subred de tamaño reducido que se utiliza para encontrar soluciones primales factibles. Se muestra, que en este sentido, el método de ascenso dual es una excelente herramienta de selección de arcos en términos del potencial que tiene la subred de encontrar soluciones primales de buena calidad. Para obtener la solución primal, se utiliza la formulación multicommodity original o un esquema de generación de filas dependiendo del tamaño de la instancia. Se testean los distintos enfoques en instancias de distintos tamaños de redes en forma de grilla generadas aleatoriamente variando sus parámetros y su relación de costos fijos a costos de flujo, testeando instancias que en su equivalente de formulación multicommodity llegan a más de 16 millones de variables. / Este trabajo ha sido parcialmente financiado por Comisión Nacional de Investigación Científica y Tecnológica (CONICYT)
| Identifer | oai:union.ndltd.org:UCHILE/oai:repositorio.uchile.cl:2250/143505 |
| Date | January 2016 |
| Creators | Rivas Sáenz, Sebastián Andrés |
| Contributors | Epstein Numhauser, Rafael, Olivares Acuña, Marcelo, Correa Haeussler, José, Rey, Pablo |
| Publisher | Universidad de Chile |
| Source Sets | Universidad de Chile |
| Language | English |
| Detected Language | Spanish |
| Type | Tesis |
| Rights | Attribution-NonCommercial-NoDerivs 3.0 Chile, http://creativecommons.org/licenses/by-nc-nd/3.0/cl/ |
Page generated in 0.0022 seconds