A tabu search algorithm for the optimisation of telecommunication networks

A Tabu Search (TS) algorithm is presented for topological optimisation of broadband communication networks whose structure is based on a single exchange and on a number of multiplexing centres. Considering the high cost of the fibre optic cable, the network architecture is a minimum spanning tree. The optimisation problem is reduced to choosing the number and the locations of the multiplexing centres. This leads to modelling the network by a binary string in which ones and zeros 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.