[Zurück]

G. Fritz:
"Heuristic methods for the hop constrained survivable network design problem";
Betreuer/in(nen): G. Raidl, M. Leitner; Institut für Computergraphik und Algorithmen, 2011; Abschlussprüfung: 09/2011.

In der vorliegenden Arbeit werden heuristische und metaheuristische Lösungsalgorithmen
für das Hop Constrained Node Survivable Network Design Problem
(HNSND) und das Hop Constrained Edge Survivable Network Design Problem
(HESND) präsentiert und miteinander verglichen.
Hop Constrained Survivable Network Design ist ein NP-schweres Problem.
Nachdem die Lösung in der vorliegenden Arbeit als Subgraph repräsentiert wird,
ist bereits der Test, ob eine Lösung gültig ist, NP-schwer. Daher liegt der erste
Schwerpunkt der Arbeit auf der Entwicklung eines fortgeschrittenen Tests,
welcher in polynomieller Zeit zumindest ungültige Lösungen ausschließen kann,
dies am besten mit einer sehr kleinen Fehlerrate, um die Anwendungen des zeitintensiven
exakten Gültigkeitstest zu minimieren. Die Ergebnisse auf den getesteten
Instanzen zeigen, dass der polynomielle \Advanced Check" eine Fehlerrate von
rund 1% in Bezug auf \False Positives" hat, mit anderen Worten rund 1% der
durchgelassenen Lösungen keine gültige Lösung darstellen. Darüber hinaus liegt
der Algorithmus insgesamt in rund 0,40% aller getesteten Instanzen mit seiner
Bewertung falsch.
Danach werden 27 verschiedene Lösungsalgorithmen entwickelt, darunter zehn
Konstruktionsheuristiken, zehn Variable Neighborhood Descent (VND) Varianten,
sechs Multi-Start VND Varianten, sowie ein Greedy Randomized Adaptive Search
Procedure Ansatz. Weiters wird ein verbesserter exakter Gültigkeitstest präsentiert.
Die Ergebnisse auf den getesteten Instanzen zeigen, dass einige Verfahren
optimale Ergebnisse erzielen. Überblicksmäßig ergibt sich für das HESND im
Schnitt eine Abweichung von 5-25% von der Optimallösung, für das HNSND gibt
es keine Vergleichswerte auf den getesteten Instanzen.
Zusammenfassend ist zu sagen, dass die vorliegende Arbeit eine große Toolbox
an heuristischen Methoden für Hop Constrained Survivable Network Design
Probleme präsentiert, welche gute Resultate in vernünftiger Zeit erzielen.

In this thesis, heuristic and meta-heuristic algorithms for solving the Hop Constraind
Node Survivable Network Design Problem (HNSND) and the Hop Constrained
Edge Survivable Network Design Problem (HESND) are presented and
compared to each other.
Hop constrained survivable network design is an NP-hard problem. Since solutions
are encoded as subgraphs in this thesis, the feasibility test is NP-hard
too. Hence, the rst main focus is developing a (fast) advanced feasibility check,
which checks in polynomial time that at least a given solution provably is not
feasible, at best with a very small error rate, in order to minimize applications of
the time-consuming exact feasibility test. Computational results show that this
polynomial-time advanced feasibility check has an error rate of about 1% regarding
\false positives" and furthermore this algorithm has a total error rate of about
0,40% over all tested instances.
In the following, 27 di erent problem solution algorithms are developed, including
ten constructive heuristic variants, ten Variable Neighborhood Descent (VND)
variants, six Multi-Start VND variants and a Greedy Randomized Adaptive Search
Procedure approach. In addition, an improved exact feasibility test is introduced.
Computational results show that some solution methods meet the optimal results
regarding the edge-disjointness variant. On a general view, the best approaches
yield a gap of about 5-25% on average. Regarding the node-disjointness variant
there are no comparable results for the test instance sets.
Finally, it can be said that this thesis provides a big toolbox of heuristic methods
for solving hop constrained network design problems, which yield good results
in a reasonable amount of time.

http://publik.tuwien.ac.at/files/PubDat_200743.pdf