Beta 1


Title Methods for hierarchical network design
Author Thomadsen, Tommy (Informatics and Mathematical Modelling, Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark)
Institution Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark
Thesis level Master's thesis
Year 2002
Abstract This thesis investigates hierarchical networks. We start by considering telecommunication networks where hierarchies exists. Telecommunication networks can be modeled as capacitated networks; hence the hierarchical networks are defined based on the capacitated networks. A mathematical model is set up for a two level version of the hierarchical network problem and the hierarchical network problem is solved to optimality for up to 15 nodes and heuristically for up to 100 nodes. The optimal solution algorithm is a branch-and-bound algorithm and the heuristic solution algorithm is a simulated annealing algorithm. They both solve the hierarchical network problem by solving a number of capacitated networks and aggregating the results. Performance is measured for different versions of both algorithms, and the quality of the heuristic solutions are estimated by comparing these with optimal solutions when these can be found. We conclude, that hierarchical networks using capacitated networks as the underlying network type can be meaningfully described and optimized. When solved heuristically, rather large networks (up to 100 nodes) can be handled easily.
Keywords hierarchical networks; topological networks; multilevel networks; capacitated networks; multicommodity flow; network design; operations research; heuristics
Fulltext
Original Postscript imm431.ps (1.23 MB)
Derived PDF imm431.pdf (0.62 MB)
Admin Creation date: 2006-06-22    Update date: 2007-09-11    Source: dtu    ID: 58348    Original MXD