Premium
Tabu search for the Steiner problem in graphs
Author(s) -
Ribeiro Celso C.,
De Souza Maurício C.
Publication year - 2000
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/1097-0037(200009)36:2<138::aid-net9>3.0.co;2-u
Subject(s) - tabu search , steiner tree problem , heuristics , mathematical optimization , benchmark (surveying) , mathematics , computation , combinatorics , reduction (mathematics) , vertex connectivity , graph , undirected graph , computer science , algorithm , vertex (graph theory) , geometry , geodesy , geography
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. © 2000 John Wiley & Sons, Inc.