The thesis addresses two classes of well-known network optimisation problems; those of finding minimum cost multi-commodity flow networks and those of finding centralised tree-like networks. Five specific problems falling into these broad categories have been solved.
The first two problems are closely related versions of the minimum concave-cost multi-commodity network design. In a telecommunications context, the networks are undirected and large numbers of commodities may be involved. A modification of an existing greedy heuristic is proposed leading to better quality solutions. For directed networks, the problem can take the form of a non-linear cost transshipment. Following an improvement over an existing method, it is solved using the recently developed Tabu search metaheuristic.
The second part of the thesis studies three selected graph problems on centralised networks and their solutions with special emphasis on practical performance. The problems investigated include the ordinary uncapacitated minimum spanning tree, the minimum spanning tree verification and the capacitated minimum spanning tree. There have been remarkable achievements over the last two decades in inventing faster and faster minimum spanning tree algorithms. A comprehensive survey and an empirical comparative study is carried out on both the classical and modern methods for solving the ordinary uncapacitated case. The linear-time solution of the verification problem is important since it arises as a subproblem in a recently developed linear-time minimum spanning tree algorithm. A linear-time implementation of an existing verification approach, which until recently was thought not to be possible, is proposed. It simplifies the previous techniques significantly. Finally, a study of the capacitated minimum spanning tree problem, which is devoted mainly to investigating the Lagrangean relaxation based lower bounding schemes and developing a branch and bound strategy using a directed formulation, is presented.