Groupe d’études et de recherche en analyse des décisions

G-96-03

A Tabu Search Heuristic for the Steiner Tree Problem in Graph

, et

We present several versions of a tabu search algorithm for the Steiner tree problem in graphs. A basic tabu search heuristic and versions with radical and/or continuous diversification are considered. Computational results on a large set of randomly generated problems with up to 300 nodes are reported and compared with those obtained with four well-known existing heuristics. These comparisons show that the proposed tabu search heuristic clearly outperforms existing methods. Comparisons between the four variants of the heuristic indicate that the variant with continuous diversification provides the best results but needs the most fine-tuning. Additional computational experiments on the benchmark problems of the OR-Library, for which optimal solutions are known, confirm the quality of the solutions produced by the tabu search heuristic.

, 19 pages