[Back]

Th. Bucsics:
"Metaheuristic Approaches for Designing Survivable Fiber-Optic Networks";
Supervisor: G. Raidl, D. Wagner; Institut für Computergraphik und Algorithmen, TU Wien, 2007; final examination: 2007-03.

During the last years ber-optic based communication networks have become a ordable
for individual households. Due to the costly nature of the materials and infrastructure that
have to be deployed to distribute such a network over a large area, exact algorithms for calculating
a provably optimal cable routing are desirable. However, due to the computational
complexity of the problem, such algorithms are not always able to determine an optimal
solution within acceptable time. Heuristics and metaheuristics can provide techniques to
calculate approximate solutions that are often su cient as a starting point for certain, more
time-consuming approaches, or even su cient for practical purposes. This thesis de nes
a formal way to view the problems that are posed by connecting a set of customers to an
existing infrastructure, and will split up the described problem into the construction and
augmentation of a Steiner tree. An overview of some state-of-the-art approaches for the
solution of the problem at hand, as well as for the solution of the sub-problems on which
our heuristics are based, is given. Several construction heuristics are suggested, as well as
local improvement procedures based on di erent neighborhood structures. Local Search,
Simulated Annealing, Variable Neighborhood Descent and Variable Neighborhood Search
are furthermore studied in detail. Also, hybrid methods using di erent heuristics to construct
a diverse set of candidate solutions which are then used to de ne a problem smaller
than the original problem to be solved by exact or other, more time-demanding methods,
is proposed. An implementation of these methods is described, and conducted experiments
are documented. Experimental results of the various described methods will be compared,
and their e ectiveness will be measured by comparison to existing exact methods.

In den letzten Jahren sind Glasfaser-basierte Netzwerke für einzelne Haushalte leistbar
geworden. Materialien und Konstruktionsarbeiten, um ein ächendeckendes Netzwerk
aufzubauen, bringen hohe Kosten mit sich. Daher wäre ein exakter Algorithmus zur Lö-
sung des Problems der Berechnung von optimalen Kabelrouten wünschenswert. Aufgrund
der hohen komputationalen Komplexität des Problems können in vielen Fällen nicht innerhalb
eines akzeptablen Zeitrahmens berechnet werden. Heuristiken und Meta-Heuristiken
stellen in diesem Fall Methoden zur Erstellung approximativer Lösungen dar, die oft
als Ausgangspunkt für zeitintensivere Methoden dienen können oder direkt für praktische
Zwecke ausreichend sind. Diese Arbeit beschreibt eine formale Betrachtungsweise der
mit der Anbindung von Kunden an ein bestehendes Netzwerk verbundenen Probleme, die
das beschriebene Problem in die Konstruktion und Augmentierung eines Steinerbaumes
aufspaltet. Es wird ein Überblick über den derzeitigen Stand der Forschung auf diesen
Gebieten, sowie dem Gebiet der Gesamtlösung eines solchen Problems gegeben, der sowohl
exakte als auch approximative, heuristische und meta-heuristische Methoden miteinbezieht.
Einige mögliche Konstruktionsheuristiken zur Lösung dieser Probleme, sowie mögliche Optimierungsalgorithmen
zur Verbesserung solcher Lösungen werden im Detail dargestellt.
Weiters werden Move-Operatoren und Nachbarschaften beschrieben. Meta-heuristische
Methoden wie lokale Suche, Simulated Annealing, Variable Neighborhood Descent und
Variable Neighborhood Search werden unter deren Nutzung untersucht, sowie einige hybride
Methoden, die eine Menge an heuristisch konstruierten Lösungen als Basis nutzen,
um ein Problem, das kleiner als das Gesamtproblem ist, zu de nieren, das dann von exakten
oder anderen, zeitintensiveren Methoden gelöst werden kann. Eine Beispielimplementierung,
die auch im Zuge von Experimenten genutzt wurde, sowie die durchgeführten
Experimente und verwendeten Probleminstanzen werden beschrieben. Abschliessend werden
die Resultate dieser Experimente den Resultaten einander gegenübergestellt und ihre
E ektivität anhand von Vergleichen mit exakten Verfahren gemessen.