Modern global optimisation heuristics in the long term planning of telecommunication networks

Telecommunication transmission networks are faced with greatly increasing bandwidth demands due largely to a growth in the number of subscriber services on offer and the nature of these services. Existing (and new) operators are presented with the problem of installing new capacity to cater for this. The scale of these networks and the immense investment being undertaken suggests that much attention in planning be given to minimum cost design. This thesis is concerned with the area of network topological optimisation Network topological design problems require the optimal configuration of a network to meet a set of requirements while minimising total cost. Network topological optimisation problems are usually computationally difficult. Many such problems belong to the ¿VP-hard class of problems, for which no polynomial-time solution algorithms have been found As there are frequently a large number of diverse local optima, the use of pure local optimisation strategies can be rather inefficient to search for the global optimum or a feasible solution close to it. The major concern of this work is to consider some approaches to global optimisation based on a non-tnvial combination and adaptation of modem optimisation heuristics, namely tabu search, simulated annealing and genetic algorithms. The performance of these algorithms is evaluated with reference to quality of solution obtained, robustness, and time taken to converge. Existing methods are also reviewed and improvements in performance are achieved. To ensure that our tests are mdependent of the idiosyncrasies of any particular network, a mechamsm for generating random, realistic test problems is developed. A classification of problems is introduced to examine how algorithm performance depends on the nature of the problem We see that a parameter defining this classification is in fact closely related to the number of local optima in the problem