||Methods for hierarchical network design
||Thomadsen, Tommy (Informatics and Mathematical Modelling, Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark)
||Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark
||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.
||hierarchical networks; topological networks; multilevel networks; capacitated networks; multicommodity flow; network design; operations research; heuristics
Creation date: 2006-06-22
Update date: 2007-09-11