Detail publikace

Metaheuristics for the Graphical Steiner Tree Problem

ŠEDA, M. SMUTEK, D.

Anglický název

Metaheuristics for the Graphical Steiner Tree Problem

Typ

článek ve sborníku ve WoS nebo Scopus

Jazyk

en

Originální abstrakt

The graphical Steiner tree problem finds a shortest tree spanning a given vertex subset within a network. It is an NP-complete problem and therefore for large scaled instances, the optimal solution cannot be found in a reasonable amount of time, being usually solved by approximation or deterministic heuristic methods. This paper proposes an approach that uses two stochastic heuristic methods (genetic algorithms and simulated annealing) applied to a binary string representation of Steiner vertices candidates. These methods are tested on standard benchmarks from OR-Library and suitable parameter settings are recommended to achieve good solutions

Anglický abstrakt

The graphical Steiner tree problem finds a shortest tree spanning a given vertex subset within a network. It is an NP-complete problem and therefore for large scaled instances, the optimal solution cannot be found in a reasonable amount of time, being usually solved by approximation or deterministic heuristic methods. This paper proposes an approach that uses two stochastic heuristic methods (genetic algorithms and simulated annealing) applied to a binary string representation of Steiner vertices candidates. These methods are tested on standard benchmarks from OR-Library and suitable parameter settings are recommended to achieve good solutions

Klíčová slova anglicky

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

Rok RIV

2001

Vydáno

01.10.2001

Nakladatel

Jena University of Applied Sciences

Místo

Jena

ISBN

3-901509-19-4

Kniha

Proceedings of the 12th International DAAAM Symposium

Počet stran

2

BIBTEX


@inproceedings{BUT6618,
  author="Miloš {Šeda} and Daniel {Smutek},
  title="Metaheuristics for the Graphical Steiner Tree Problem",
  booktitle="Proceedings of the 12th International DAAAM Symposium",
  year="2001",
  month="October",
  publisher="Jena University of Applied Sciences",
  address="Jena",
  isbn="3-901509-19-4"
}