Resumen:
El Problema del m-anillo-estrella con capacidades, CmRSP (Capacitated m-Ring-Star Problem) consiste en encontrar una estructura llamada m-anillo-estrella de costo mínimo que conecte a un conjunto de clientes en red. La estructura está compuesta por conexiones anillo (con costos asociados) que forman m anillos (ciclos) disjuntos de nodos junto con un nodo distinguido (depósito) común a todos los anillos, y conexiones estrella (con costos asociados) que permiten conectar clientes a anillos. Adicionalmente, existen nodos de tránsito, llamados nodos de Steiner que pueden ser utilizados opcionalmente en los anillos en casos que permitan reducir costos al conectar clientes a estos nodos con conexiones estrella. Cada anillo, además, tiene una capacidad de clientes, esto quiere decir que no se puede superar un cierto límite de cantidad de clientes en cada anillo, considerando tanto los clientes que forman parte del anillo como aquellos que están conectados a algún nodo del anillo por medio de una conexión estrella. CmRSP pertenece a la clase de problemas NP-Hard. Las redes con estructura de m-anillo-estrella se utilizan en redes de comunicación de alcance urbano de fibra óptica. Los cables que llevan las fibras se instalan bajo tierra, y la estructura de anillo permite que la falla en una conexión del anillo, que podría producirse accidentalmente en alguna excavación o rotura de calle por algún tipo de reparación, no afecte la conectividad de la red, asi como tambien, la falla de algún nodo no afecte al resto de los nodos de la red. Esto se debe a que cada cliente recibe un par de cables de fibra óptica, de manera que es capaz de transmitir en los dos sentidos posibles dentro de su anillo. Por otro lado, las conexiones estrella permiten reducir costos de instalación, considerando que estas conexiones se establecen entre nodos que están físicamente no muy alejados, de manera que sea menor la posibilidad de que ocurra alguna falla en la conexión. El objetivo de esta tesis es abordar el Problema del m-anillo-estrella con capacidades. Se propone un nuevo modelo de programación entera y se desarrolla un algoritmo branch-and- cut para su resolución exacta. Para ello, se proponen familias de desigualdades válidas para el nuevo modelo y se diseñan algoritmos de separación de las mismas para utilizar como planos de corte en las relajaciones, se presenta una heurística inicial para obtener una cota primal, se analizan distintas estrategias de branching y de recorrido del árbol. Finalmente se implementa el algoritmo branch-and-cut y se analizan los resultados obtenidos.
Abstract:
The Capacitated m-ring-star problem, CmRSP, is the problem of designing a structure named m-ring-star with minimum cost, to connect a set of customers in a network. The m-ring-star is a set of m rings that pass through a distinguished node (depot) shared by all rings, and optionally star connections (with costs) from customers not in rings to rings. Every connection have some cost. Also, the rings can include transit nodes, named Steiner nodes, to reduce costs if possible. The number of customers in a ring (included in the ring or connected to the ring using a star connection) is bounded by an upper limit (capacity). CmRSP belongs to NP-Hard problems's class. Applications of m-ring-star networks includes design of optical urban networks. Fiber cables could be damaged during street reparations in a urban environment. Each customer receives a pair of bers to send/receive information in clockwise and counter-clockwise way. So, if some ring connection fails, the network don't lose connectivity. Star connections may be established between non very distant nodes. The aim of this thesis is to present a new integer programming formulation for the Capa- citated m-ring-star Problem and develop a branch-and-cut algorithm to solve it. To achieve this goal, proposes families of valid inequalities for the new model and separation algorithms for them to use as cutting planes in linear relaxations, presents an initial heuristic to get a primal bound, branching and traversal tree strategies. Then implements the branch-and-cut algorithm and analyzes the obtained results.
Citación:
---------- APA ----------
Berinsky, Hernán. (2010). Un modelo y algoritmo branch- and -cut para el problema del m-anillo-estrella con capacidades. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000383_Berinsky
---------- CHICAGO ----------
Berinsky, Hernán. "Un modelo y algoritmo branch- and -cut para el problema del m-anillo-estrella con capacidades". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2010.https://hdl.handle.net/20.500.12110/seminario_nCOM000383_Berinsky
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000383_Berinsky.pdf
Distrubución geográfica
