Hierarchical Network Design Using Simulated Annealing

Tommy Thomadsen (ttimm.dtu.dk)
Jens Clausen (jcimm.dtu.dk)

Abstract: The hierarchical network problem is the problem of finding the least cost network, with nodes divided into groups, edges connecting nodes in each groups and groups ordered in a hierarchy. The idea of hierarchical networks comes from telecommunication networks where hierarchies exist. Hierarchical networks are described and a mathematical model is proposed for a two level version of the hierarchical network problem. The problem is to determine which edges should connect nodes, and how demand is routed in the network. The problem is solved heuristically using simulated annealing which as a sub-algorithm uses a construction algorithm to determine edges and route the demand. Performance for different versions of the algorithm are reported in terms of runtime and quality of the solutions. The algorithm is able to find solutions of reasonable quality in approximately 1 hour for networks with 100 nodes.

Keywords: Hierarchical Networks, Network Design

Category 1: Applications -- OR and Management Sciences (Telecommunications )

Category 2: Network Optimization

Category 3: Combinatorial Optimization (Meta Heuristics )

Citation: Unpublished: Technical report, IMM-2002-14 Informatics and Mathematical Modelling, Technical University of Denmark, Kgs. Lyngby, Denmark September 2002

Download: [Postscript][PDF]

Entry Submitted: 10/03/2002
Entry Accepted: 10/03/2002
Entry Last Modified: 10/03/2002

Modify/Update this entry