<div class="csl-bib-body">
<div class="csl-entry">Jahrmann, P. (2013). <i>Metaheuristics for the regenerator location problem</i> [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-46305</div>
</div>
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 />
de
dc.description.abstract
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 />
en
dc.language
Deutsch
-
dc.language.iso
de
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Optimierung
de
dc.subject
Regenerator Location Problem
de
dc.subject
Netzwerkdesign
de
dc.subject
Metaheuristik
de
dc.subject
Clique
de
dc.subject
Independent Set
de
dc.subject
GRASP
de
dc.subject
VNS
de
dc.subject
optimization
en
dc.subject
Regenerator Location Problem
en
dc.subject
network design
en
dc.subject
metaheuristics
en
dc.subject
clique
en
dc.subject
independent set
en
dc.subject
GRASP
en
dc.subject
VNS
en
dc.title
Metaheuristics for the regenerator location problem
de
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Peter Jahrmann
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
tuw.publication.orgunit
E186 - Institut für Computergraphik und Algorithmen