Heuristic methods for the Hop Constrained Survivable Network Design Problem

Abstract

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.<br />Hop Constrained Survivable Network Design ist ein NP-schweres Problem.<br />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.<br />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.<br />Ü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.<br />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.<br />

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.<br />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 first 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.<br />In the following, 27 different 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.<br />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.<br />