Detail publikace

Metaheuristics for the Network Steiner Tree Problem

Š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

ŠEDA, M.

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"
}