Tabu search for the Steiner problem in graphs

Given an undirected graph with weights associated with its edges, the Stein er tree problem consists of finding a minimum-weighted subgraph spanning a given subset of nodes (terminals) of the original graph. In this paper, we describe a tabu search algorithm for the Steiner problem in graphs, based o n a neighborhood defined by insertions and eliminations of Steiner nodes. M ove estimations, elimination tests, and neighborhood-reduction techniques a re used to speed up the local search, leading to a very fast algorithm with very good results in terms of solution quality. Computational experiments on benchmark problems are reported, comparing the behavior of the proposed tabu search algorithm with that of other heuristics from the literature. Ta bu search clearly outperforms other heuristics in terms of computation time s, obtaining better or comparable solutions. (C) 2000 John Wiley & Sons, In c.