[Back]


Diploma and Master Theses (authored and supervised):

P. Jahrmann:
"Metaheuristics for the regenerator location problem";
Supervisor: G. Raidl; Institut für Computergraphik and Algorithmen, 2013; final examination: 2013-03.



English abstract:
During the past years optical networks have proven to be the best technology in terms of highspeed
data transmission. They offer high transmission rates together with a high bandwidth.
Moreover optical fiber is more robust against interferences than copper cable. Nevertheless the
quality of an optical signal detoriates as it travels through the network depending on the covered
distance due to impairments in the fiber. Therefore regenerators are installed at certain nodes
in the network for a periodical signal regeneration, ensuring that all nodes can communicate
with each other flawlessly. Since these regenerators are usually considered to be expensive the
regenerator location problem (RLP) demands for a minimum cardinality subset of regenerators
to achieve the required condition. A typical instance of the RLP is given by an arbitrary network
graph G = (V;E; d) and a parameter dmax indicating the maximum distance a signal can travel
without loss of quality. Since it is an NP-hard problem the utilization of heuristical optimization
methods is reasonable to obtain solutions for problems with arbitrary sizes. In literature a
branch-and-cut algorithm was presented to obtain exact solutions for the RLP. Another work
describes the application of a Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic
with a randomized construction heuristic and a 2x1 local search procedure. In the
course of this thesis advanced selection strategies for regenerator placement have been developed
and utilized in new construction and local search based procedures. For this purpose special
node sets like cliques and independent sets exploit the structure of the underlying network graph
more efficently. All developed heuristics use the communication graph M = (V;E0), which
is the result of a graph transformation procedure applied to the original graph G. In M the information
about the actual need of regenerators is presented in an easier way, which correlates
with the existance of not directly connected node pairs E0. 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. In this case the chosen regenerators form a feasible solution.
An independent set represents the information of several not connected node pairs. Therefore
regenerators are placed in the graph trying to neighbor as many nodes of different independent
sets as possible until there are no independent sets left.
The heuristic strategies were employed in a GRASP framework as well as in a Variable
Neighborhood Search (VNS). They were tested on two different test sets and the results were
compared to those of the GRASP heuristic from the literature. The developed GRASP heuristics
using clique and independent set strategies obtained most of the best known solutions. Also the
VNS heuristics performed quite good on the test sets and reached similar results as the GRASP
from the previous literature.

German abstract:
In modernen Telekommunikationsnetzwerken haben sich im Laufe der letzten Jahre vor allem
Glasfaserverbindungen durch ihre hohe Bandbreite und Übertragungsgeschwindigkeit als
Grundlage für eine schnelle Informationsübertragung etabliert. Obwohl sie im Vergleich zu den
Kupferleitungen weniger anfällig für Störeinflüsse sind, treten trotzdem mit zunehmender Kabellänge
Qualitätsverluste bei der Signalübertragung auf. Daher ist es notwendig an speziellen
Knoten eines optischen Netzwerks so genannte Regeneratoren zu installieren, damit durch
Signalregenerierung eine zuverlässige Kommunikation zwischen allen Knotenpaaren sichergestellt
ist. Das Regenerator Location Problem (RLP) fordert dabei die Platzierung von so wenigen
Regeneratoren wie nur möglich, um diese Bedingung zu erfüllen. Eine typische Instanz ist
in Form eines Netzwerkgraphen G = (V;E; d) und eines Parameters dmax gegeben, der die
maximale Distanz, die ein optisches Signal zurücklegen kann beschreibt. Beim RLP handelt
es sich um ein NP-schwieriges Problem, das den Einsatz von heuristischen Verfahren nahelegt,
um auch für große Instanzen Lösungen in annehmbarer Zeit zu berechnen. In der Literatur
wurden bisher exakte Verfahren in Form eines Branch-and-Cut Ansatzes betrachtet, sowie die
Anwendung einer Greedy Randomized Adaptive Search Procedure (GRASP) Metaheuristik mit
randomisierter Konstruktionsheuristik und so genannter 2x1 Move Nachbarschaftsstruktur vorgestellt.
Im Zuge dieser Arbeit werden weitere Mechanismen vor allem im Zusammenhang mit
speziellen Knotenmengen im Graphen wie z.B. Cliques oder Independent Sets erforscht und in
Konstruktionsheuristiken, sowie Nachbarschaftsstrukturen für die lokale Suche eingesetzt. Die
entwickelten Heuristiken nutzen dabei den Communication Graph M = (V;E0), der den Bedarf
an tatsächlich benötigten Regeneratoren in einfacherer Form darstellt. Einerseits ist die Idee
bestehende Cliques in M durch die Einführung von Regeneratoren immer weiter zusammenzufassen,
bis nur noch eine einzige übrig bleibt, die dem gesamten Graphen entspricht, wobei
die gefundenen Regeneratoren eine gültige Lösung formen. Andererseits werden Independent
Sets als fehlende Kommunikationsmöglichkeit zwischen mehreren Knotenpaaren identifiziert
und diese durch Regeneratoren, die möglichst viele Knoten unterschiedlicher Independent Sets
benachbarn immer weiter reduziert, bis ebenfalls eine gültige Lösung entstanden ist.
Die entwickelten Heuristiken wurden sowohl in GRASP, als auch in Variable Neighborhood
Search (VNS) Heuristiken eingebettet und im Zuge der Arbeit mit dem in der Literatur
beschriebenen GRASP Ansatz verglichen. Es stellt sich heraus, dass die entwickelten GRASP
Heuristiken durch die vergleichsweise kurze Laufzeit die besten Ergebnisse erzielen und die
VNS Heuristiken ebenso in der Lage sind mit der in der Literatur vorgeschlagenen Lösung mitzuhalten.


Electronic version of the publication:
http://publik.tuwien.ac.at/files/PubDat_222012.pdf


Created from the Publication Database of the Vienna University of Technology.