Design of Hierarchical Ring Networks Using Branch-and-Price

Tommy Thomadsen, Thomas Stidsen

AbstractWe consider the problem of designing hierarchical two layer ring networks. The top layer consists of a federal-ring which establishes connection between a number of node disjoint metro-rings in a bottom layer. The objective is to minimize the costs of links in the network, taking both the fixed link establishment costs and the link capacity costs into account.

The hierarchical two layer ring network design problem is solved in two stages: First the bottom layer, i.e. the metro-rings are designed, implicitly taking into account the capacity cost of the federal-ring. Then the federal-ring is designed connecting the metro-rings, minimizing fixed link establishment costs of the federal-ring. A branch-and-price algorithm is presented for the design of the bottom layer and it is suggested that existing methods are used for the design of the federal-ring. Computational results are given for networks with up to 36 nodes.
KeywordsRing network design, Hierarchical network design, Branch-and Price
TypeTechnical report
PublisherInformatics and Mathematical Modelling, Technical University of Denmark, DTU
AddressRichard Petersens Plads, Building 321, DK-2800 Kgs. Lyngby
SeriesIMM-Technical Report-2004-7
BibTeX data [bibtex]
IMM Group(s)Operations Research

Back  ::  IMM Publications