A Tabu Search algorithm for the optimisation of telecommunication networks

A Tabu Search (TS) algorithm is presented for topological optimisation of broad band communication networks whose structure is based on a single exchange and on a number of multiplexing centres. Considering the high cost of the fiber optic cable, the network architecture is a minimum spanning tree. The optimisation problem is reduced to choose the number and the locations of the multiplexing centres. This leads to model the network by a binary string in which ones and zeroes indicate activation or non-activation of multiplexing centres in the nodes. A TS algorithm has been implemented using a dynamically changing tabu_tenure, a frequency based long term memory structure and an aspiration criterion. Extensive testing over networks of various sizes and configurations is made in order to choose the best values of the parameters. The performances of the algorithm are compared to those of other more traditional techniques. (C) 1998 Elsevier Science B.V. All rights reserved.