|
Abstract : |
Abstract. This paper presents a computational study of a digital line network design problem arising in the telecommunication industry. The objective can be formulated as that of finding an optimal degree constrained Steiner tree in a graph whose nodes and edges are weighted by costs. We develop a Tabu Search heuristic for this problem that incorporates long term memory and probabilistic move selections. We address move evaluation, error correction and candidate list strategies. Computational results for test data whose distributions yield difficult problem instances show that the new heuristic yields optimal solutions for all problems where such solutions could be found by exact algorithms, while requiring a fraction of the solution time. In addition, for larger and more realistic sized problems, which the exact methods were unable to solve, comparative tests show our method also outperforms the best local search heuristic currently available. The performance differences favoring tabu search significantly increase for more difficult problem instances., |
