An optimal procedure for solving the hierarchical network design problem

Simple item page
dc.contributor.authorObreque, Carlos
dc.contributor.authorMarianov, Vladimir
dc.date.accessioned2024-01-10T13:45:53Z
dc.date.available2024-01-10T13:45:53Z
dc.date.issued2007
dc.description.abstractThe hierarchical network design problem consists of finding a minimum cost bilevel network that connects all the nodes in a set, created by a loopless main path and a forest. The main path is formed by primary (higher cost) arcs, providing a path between an origin node and a destination node. The forest, built using secondary (lower cost) arcs, connects all the nodes not on the main path, to the path itself. We state and prove some properties of the problem, which allow finding good upper bounds to the solution in polynomial time when the primary costs are proportional to secondary costs. We also propose an O(n(4)) procedure to improve on these bounds. In turn, these bounds are used to significantly reduce the number of nodes and arcs of the problem. Once the problem is reduced, large instances can be solved to optimality. At this stage, we use one of two linear integer optimization formulations. The first and preferred one is based on multicommodity flows, which avoids the formation of subtours. The second formulation avoids subtours by iteratively adding ad hoc constraints. We show some examples and provide computational experiments performed on networks with sizes up to 600 nodes and 14 000 arcs.
dc.fechaingreso.objetodigital2024-04-30
dc.format.extent12 páginas
dc.fuente.origenWOS
dc.identifier.doi10.1080/07408170600941615
dc.identifier.eissn1545-8830
dc.identifier.issn0740-817X
dc.identifier.urihttps://doi.org/10.1080/07408170600941615
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/79092
dc.identifier.wosidWOS:000245029700008
dc.information.autorucIngeniería;Marianov V;S/I;99349
dc.issue.numero5
dc.language.isoen
dc.nota.accesoSin adjunto
dc.pagina.final524
dc.pagina.inicio513
dc.publisherTAYLOR & FRANCIS INC
dc.revistaIIE TRANSACTIONS
dc.rightsregistro bibliográfico
dc.subjecthierarchical network design problem
dc.subjectproblem reduction
dc.subjectshortest path containing a node or an arc
dc.subjectinteger programming
dc.subjectFORMULATION
dc.subjectCOST
dc.subject.ods11 Sustainable Cities and Communities
dc.subject.odspa11 Ciudades y comunidades sostenibles
dc.titleAn optimal procedure for solving the hierarchical network design problem
dc.typeartículo
dc.volumen39
sipa.codpersvinculados99349
sipa.indexWOS
sipa.indexScopus
sipa.trazabilidadCarga SIPA;09-01-2024
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
An optimal procedure for solving the hierarchical network design problem.pdf
Size:
98.43 KB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Artículos de revistas