USING TABU SEARCH TO SOLVE THE STEINER TREE-STAR PROBLEM IN TELECOMMUNICATIONS NETWORK DESIGN

We present a study of using tabu search to solve a specific network de sign problem arising in the telecommunication industry. We develop a t abu search heuristic for this problem that incorporates long-term memo ry and probabilistic move selections. Computational results show that the new heuristic consistently outperforms the best local search curre ntly available, with significantly increased performance differences o n more difficult problems.