Publication detail
Metaheuristics for the Graphical Steiner Tree Problem
ŠEDA, M. SMUTEK, D.
English title
Metaheuristics for the Graphical Steiner Tree Problem
Type
Paper in proceedings (conference paper)
Language
en
Original abstract
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
Released
2001-10-01
Publisher
Jena University of Applied Sciences
Location
Jena
ISBN
3-901509-19-4
Book
Proceedings of the 12th International DAAAM Symposium
Pages from–to
431–
Pages count
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",
pages="2",
publisher="Jena University of Applied Sciences",
address="Jena",
isbn="3-901509-19-4"
}