Metaheuristics for the Network Steiner Tree Problem

book chapter

English

The network Steiner tree problem (or Steiner tree problem in graphs) finds a shortest tree spanning a given vertex subset within a network. For exact solutions, a mixed integer programming model is proposed and checked in GAMS optimization package. However, the studied problem is NP-complete and therefore, for large scaled instances, the optimal solution cannot be found in a reasonable amount of time. In this case it is usually solved by approximation or deterministic heuristic methods. This paper proposes an approach that is based on simple approximations in a hybrid combination with stochastic heuristic methods (genetic algorithms and simulated annealing) applied to a binary string representation of Steiner vertex candidates. These methods are tested on standard benchmarks from OR-Library and suitable parameter settings are recommended to achieve good solutions. It was shown that by this approach, we can achieve near-optimal results for instances of up to 100 vertices, 200 edges and 50 terminals in no more than a few minutes. This is very competitive with the best results known from literature. In a comparison with complex specialized approximation algorithms, our approach is compatible with the general framework of genetic algorithms and simulated annealing. It has a modular structure and by setting a few parameters it can be easily controlled to provide good solutions

Minimum spanning tree, Steiner tree problem, metaheuristic, genetic algorithm, simulated annealing

ŠEDA, M.

2002

10. 10. 2002

DAAAM International, Wien

Wien (Austria)

3-901509-30-5

Katalinic, B. (ed.): DAAAM International Scientific Book 2002

DAAAM International Scientific Books

525

538

14