Hierarchical Ring Network Design Using Branch-and-Price

Tommy Thomadsen, Thomas K. Stidsen

    Research output: Contribution to journalJournal articleResearchpeer-review

    152 Downloads (Pure)

    Abstract

    We 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. Hierarchical ring network design problems combines the following optimization problems: Clustering, hub selection, metro ring design, federal ring design and routing problems. In this paper a branch-and-price algorithm is presented for jointly solving the clustering problem, the metro ring design problem and the routing problem. Computational results are given for networks with up to 36 nodes.
    Original languageEnglish
    JournalTelecommunication Systems
    Volume29
    Issue number1
    Pages (from-to)61-76
    ISSN1018-4864
    DOIs
    Publication statusPublished - 2005

    Keywords

    • Branch-and-Price
    • Hierarchical network design
    • Ring network design

    Cite this