A Tabu Search Algorithm for the Steiner Tree Problem.

Steiner Tree;Tabu Search;meta-heuristics

Kulkarni, Girish ; Dr. Yahya Fathi, Committee Chair,Dr Stephen Roberts, Committee Member,Dr. George Rouskas, Committee Member,Kulkarni, Girish ; Dr. Yahya Fathi ; Committee Chair ; Dr Stephen Roberts ; Committee Member ; Dr. George Rouskas ; Committee Member

University:North Carolina State University

关键词: Steiner Tree;    Tabu Search;    meta-heuristics;   

Others  :  https://repository.lib.ncsu.edu/bitstream/handle/1840.16/2754/etd.pdf?sequence=1&isAllowed=y

美国|英语

来源: null

【 摘 要 】

The Steiner Tree problem in graphs is an NP-hard problem having applications in many areas including telecommunication, distribution and transportation systems. We survey, briefly, a few exact methods and a few heuristic approaches that have been proposed for solving this problem. Further, we propose a tabu search algorithm whose key feature includes a neighborhood definition consisting of exchange of key paths. The algorithm is empirically tested by running computational experiments on problem sets, with known optimal values, that are available over the internet. The results from the tabu search are compared with the optimal values and with the results of a well-known heuristic procedure. The experimental results show that the tabu search algorithm is reasonably successful. It produces near-optimal solutions in the experiments conducted and performs better than the heuristic procedure. We also explore other avenues for future work and possible extensions to the tabu search algorithm.