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

G-98-01

A Tabu Search Heuristic for the Steiner Tree Problem

, et

The Steiner Tree Problem in graphs (STP) is well known NP-Hard problem. It has regained attention due to the introduction of new telecommunication technologies, such as ATM, since it appears as the inherent mathematical structure behind multicast communications. In this paper, we present a tabu search algorithm for the STP in graphs. The main features of this algorithm is a sophisticated strategy for quickly obtaining a very good solution and powerful diversification mechanisms. Computational results on the benchmark problems of the OR-Library, for which optimal solutions are known, indicate that the proposed algorithm outperforms other recent heuristics.

, 21 pages