Přístupnostní navigace
E-přihláška
Vyhledávání Vyhledat Zavřít
Detail publikace
ŠEDA, M.
Originální název
Metaheuristics for the Network Steiner Tree Problem
Typ
kapitola v knize
Jazyk
angličtina
Originální abstrakt
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
Klíčová slova v angličtině
Minimum spanning tree, Steiner tree problem, metaheuristic, genetic algorithm, simulated annealing
Autoři
Rok RIV
2002
Vydáno
10. 10. 2002
Nakladatel
DAAAM International, Wien
Místo
Wien (Austria)
ISBN
3-901509-30-5
Kniha
Katalinic, B. (ed.): DAAAM International Scientific Book 2002
Edice
DAAAM International Scientific Books
Strany od
525
Strany do
538
Strany počet
14
BibTex
@inbook{BUT54861, author="Miloš {Šeda}", title="Metaheuristics for the Network Steiner Tree Problem", booktitle="Katalinic, B. (ed.): DAAAM International Scientific Book 2002", year="2002", publisher="DAAAM International, Wien", address="Wien (Austria)", series="DAAAM International Scientific Books", pages="14", isbn="3-901509-30-5" }