Metaheuristics for the Network Steiner Tree Problem

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26210%2F02%3APU31526" target="_blank" >RIV/00216305:26210/02:PU31526 - 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 Network Steiner Tree Problem

Popis výsledku v původním jazyce

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 propooses 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

Název v anglickém jazyce

Metaheuristics for the Network Steiner Tree Problem

Popis výsledku anglicky

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 propooses 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

Druh

C - Kapitola v odborné knize

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í

2002

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 knihy nebo sborníku

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

ISBN

3-901509-30-5

Počet stran výsledku

14

Strana od-do

525-538

Počet stran knihy

—

Název nakladatele

DAAAM International, Wien

Místo vydání

Wien (Austria)

Kód UT WoS kapitoly

—