Tabu search for the Steiner problem in graphs

Tabu search for the Steiner problem in graphs

0.00 Avg rating0 Votes
Article ID: iaor20022982
Country: United States
Volume: 36
Issue: 2
Start Page Number: 138
End Page Number: 146
Publication Date: Sep 2000
Journal: Networks
Authors: ,
Keywords: tabu search, Steiner problem
Abstract:

Given an undirected graph with weights associated with its edges, the Steiner 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 on a neighborhood defined by insertions and eliminations of Steiner nodes. Move estimations, elimination tests, and neighborhood-reduction techniques are 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. Tabu search clearly outperforms other heuristics in terms of computation times, obtaining better or comparable solutions.

Reviews

Required fields are marked *. Your email address will not be published.