A tabu search heuristic for the Steiner Tree Problem

The Steiner Tree Problem (STP) in graphs is a well-known NP-hard problem. I t has regained attention due to the introduction of new telecommunication t echnologies, such as ATM, since it appears as the inherent mathematical str ucture behind multicast communications. In this paper, we present a tabu se arch algorithm for the STP in graphs. The main feature of this algorithm is a sophisticated strategy for quickly obtaining a very good solution and po werful diversification mechanisms. Computational results on the benchmark p roblems of the OR-Library, for which optimal solutions are known, indicate that the proposed algorithm outperforms other recent heuristics. (C) 1999 J ohn Wiley & Sons, Inc. Networks 34: 162-172, 1999.