Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/147649 
Autor:innen: 
Erscheinungsjahr: 
2005
Schriftenreihe/Nr.: 
Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel No. 591
Verlag: 
Universität Kiel, Institut für Betriebswirtschaftslehre, Kiel
Zusammenfassung: 
This paper addresses the robust spanning tree problem with interval data, i.e. the case of classical minimum spanning tree problem when edge weights are not fixed but take their values from some intervals associated with edges. The problem consists in finding a spanning tree that minimizes so-called robust deviation, i.e. deviation from an optimal solution under the worst case realization of interval weights. As it was proven in [8], the problem is NP-hard, therefore it is of great interest to tackle it with some metaheuristic approach, namely simulated annealing, in order to calculate an approximate solution for large scale instances efficiently. We describe theoretical aspects and present the results of computational experiments. To the best of our knowledge, this is the first attempt to develop a metaheuristic approach for solving the robust spanning tree problem.
Schlagwörter: 
robust spanning tree
simulated annealing
uncertainty
Dokumentart: 
Working Paper
Dokumentversion: 
Digitized Version

Datei(en):
Datei
Größe
557.04 kB





Publikationen in EconStor sind urheberrechtlich geschützt.