Metaheuristics for the Graphical Steiner Tree Problem

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26210%2F01%3APU21358" target="_blank" >RIV/00216305:26210/01:PU21358 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Metaheuristics for the Graphical Steiner Tree Problem

Popis výsledku v původním jazyce

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 candiddates. These methods are tested on standard benchmarks from OR-Library and suitable parameter settings are recommended to achieve good solutions

Název v anglickém jazyce

Metaheuristics for the Graphical Steiner Tree Problem

Popis výsledku anglicky

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 candiddates. These methods are tested on standard benchmarks from OR-Library and suitable parameter settings are recommended to achieve good solutions

Druh

D - Stať ve sborníku

CEP obor

BB - Aplikovaná statistika, operační výzkum

OECD FORD obor

—

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2001

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the 12th International DAAAM Symposium

ISBN

3-901509-19-4

ISSN

—

e-ISSN

—

Počet stran výsledku

2

Strana od-do

431-432

Název nakladatele

Jena University of Applied Sciences

Místo vydání

Jena

Místo konání akce

Jena, Germany

Datum konání akce

24. 10. 2001

Typ akce podle státní příslušnosti

CST - Celostátní akce

Kód UT WoS článku

—