A tabu search heuristic for the Steiner tree problem

The Steiner Tree Problem (STP) in graphs is a well-known NP-hard problem. It has regained attention due to the introduction of new telecommunication technologies, such as Asynchronous Transfer Mode, 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 feature 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.