The Euclidean Steiner Tree Problem: Simulated Annealing and Other Heuristics

Abstract

In this thesis the Euclidean Steiner tree problem and the optimisation technique called simulated annealing are studied. In particular, there is an investigation of whether simulated annealing is a viable solution method for the problem. The Euclidean Steiner tree problem is a topological network design problem and is relevant to the design of communication, transportation and distribution networks. The problem is to find the shortest connection of a set of points in the Euclidean plane. Simulated annealing is a generally applicable method of finding solutions of combinatorial optimisation problems. The results of the investigation are very satisfactory. The quality of simulated annealing solutions compare favourably with those of the best known tailored heuristic method for the Euclidean Steiner tree problem