Metaheuristics for the regenerator location problem

Abstract

Heutzutage bilden Glasfaserverbindungen durch ihre hohe Bandbreite und Übertragungsgeschwindigkeit den Standard für eine schnelle Informationsübertragung. Obwohl sie robust gegenüber von Störeinflüssen sind, treten mit zunehmender Übertragungsreichweite Signaldämpfungen auf, die eine Signalregeneration in Form von Regeneratorknoten erfordern. Ziel des NP-schwierigen Regenerator Location Problems (RLP) ist es durch die Installation möglichst weniger Regeneratoren eine zuverlässige Kommunikation zwischen allen Knotenpaaren sicherzustellen. In der Literatur wurden bisher exakte Verfahren in Form eines Branch-and-Cut Ansatzes beschrieben, sowie die Anwendung einer Greedy Randomized Adaptive Search Procedure (GRASP) Metaheuristik mit randomisierter Konstruktionsheuristik und 2x1 Nachbarschaftsstruktur vorgestellt. Im Zuge dieser Arbeit werden weitere Mechanismen im Zusammenhang mit Cliques und Independent Sets als spezielle Knotenmengen der Graphentheorie erforscht und sowohl in Konstruktionsheuristiken, als auch Nachbarschaftsstrukturen für die lokale Suche eingesetzt. Idee dabei ist es einerseits Cliques durch die Einführung von Regeneratoren immer weiter zusammenzufassen, bis nur noch eine einzige übrig bleibt und andererseits Independent Sets als fehlende Kommunikationsmöglichkeit zwischen mehreren Knotenpaaren zu identifizieren und diese durch Regeneratoren immer weiter zu reduzieren. Die gefundenen Regeneratorknoten formen jeweils eine gültige Lösung.<br />Die entwickelten Heuristiken wurden in GRASP und VNS Frameworks eingebettet und mit dem in der Literatur beschriebenen Ansatz verglichen. Dabei stellte sich heraus, dass GRASP Metaheuristiken, die Clique und Independent Set Strategien benutzen, hervorragende Ergebnisse auf den getesteten Instanzen erzielen.<br />

During the past years optical networks have proven to be a key technology in telecommunications, offering high transmission rates together with a large capacity. Although optical fiber is robust against interferences, the quality of an optical signal deteriorates as it gets farther from the source. Therefore regenerators are installed at certain nodes in the network, ensuring a flawless communication between all nodes. The NP-hard regenerator location problem (RLP) demands for a minimum cardinality subset of regenerators to achieve the required condition.<br />In previous a Greedy Randomized Adaptive Search Procedure (GRASP) using a randomized construction heuristic together with a 2x1 local search procedure was introduced together with an exact branch-and-cut algorithm. In the course of this thesis advanced selection strategies for regenerator placement utilizing clique and independent set principles from graph theory have been developed. The idea behind the usage of cliques is to combine them by the introduction of regenerator nodes until there is only one clique left corresponding to the whole graph. An independent set represents the information of several not connected node pairs. Therefore regenerators are placed trying to neighbor as many nodes of different independent sets as possible until there are no independent sets left. In both cases the found regenerators form feasible solutions for the RLP.<br />The heuristic strategies were employed within a GRASP framework as well as in a Variable Neighborhood Search (VNS) and tested on several instances together with the GRASP from the previous literature. The results show that GRASP heuristics using clique and independent set based strategies obtain excellent results on the tested instances.<br />