[Zurück]

R. Schuster:
"Clustering Heuristics for the Hierarchical Ring Network Problem";
Betreuer/in(nen): G. Raidl, C. Schauer; Institut für Computergraphik und Algorithmen, 2011; Abschlussprüfung: 11/2011.

In dieser Diplomarbeit wird die Anwendung von Clusteringalgorithmen untersucht, um das
Hierarchical Ring Network Problem (HRNP) zu lösen.
Wenn das Netzwerk als Graph repräsentiert ist, ist dieses NP-vollständige Problem wie folgt
definiert: Gegeben ist Menge von Knoten welche jeweils einer von drei Schichten zugewiesen
sind, und eine Kostenfunktion, welche die Verbindungskosten zwischen zwei Knoten
(d.h. Kantenkosten) zuweist. Gesucht ist ein zusammenhängendes Netzwerk mit minimalen
Gesamtkosten, wobei dieses bestimmte Struktureigenschaften zu erfüllen hat, welche im Detail
in der Diplomarbeit beschrieben werden. Die wichtigste dieser Eigenschaften ist, dass Knoten
gemäß einer hierarchischen Struktur zu größenbeschränkten Ringen verbunden werden.
Ringstrukturen sind ein guter Kompromiss zwischen der Verfügbarkeit von Netzwerken und
deren Herstellungskosten. Die Verfügbarkeit ist gewährleistet, solange maximal ein Knoten pro
Ring ausfällt.
Die grundlegende Idee dieser Diplomarbeit um dieses Netzwerkdesign-Problem zu lösen,
ist die Knoten mit Hilfe von hierarchischen Clusteringalgorithmen anzuordnen und die resultierende
Hierarchie für nachfolgende Heuristiken zu verwenden, welche die Ringe finden.
Vorhergehende Ansätze für vergleichbare Netzwerkdesign-Probleme haben die inhärente
Netzwerkstruktur nicht auf solche Weise genützt und eher Greedy-Heuristiken eingesetzt.
Um gültige Ringe zu finden, wurden drei Heuristiken implementiert. Strategisches Variieren
der erlaubten Ringgröße hilft der ersten Heuristik Ringe unter Benützung der Cluster-Hierarchie
zu finden. Die zweite Heuristik baut auf den in der vorherigen Schicht gefundenen Ringen auf,
indem sie nach gültigen Pfaden sucht, die an diese Ringe angeschlossen werden können. Drittens
wird eine Reparaturheuristik angewendet, welche versucht verbleibende Knoten zu bestehenden
Ringen zuzuweisen.
Zuletzt werden lokale Suchverfahren eingesetzt, um die Gesamtkosten zu verbessern.
Um zu überprüfen, wie gut dieser Lösungsansatz funktioniert, wurden zwei Testinstanz-
Generatoren implementiert. Der Erste generiert Instanzen zufallsbasiert, der Zweite baut auf
dem bekannten TSPLIB-Archiv auf.
Die Evaluierung der zufallsbasierten Testinstanzen hat gezeigt, dass alle drei Heuristiken
sämtliche Instanzen lösen konnten, wobei Girvan-Newman und Kernighan-Lin in jedem Testlauf
Lösungen gefunden haben, war dies bei K-means nicht der Fall. Mit Kernighan-Lin
konnte im Durchschnitt schneller eine Lösung gefunden werden, aber die Gesamtkosten waren
bei den beiden anderen Algorithmen etwas besser. Mit den TSPLIB-basierten Testinstanzen
konnte nicht mit allen Clusteringalgorithmen eine Lösung erzielt werden, aber zumindest war
für jede Testinstanz mindestens ein Clustering-Verfahren erfolgreich.

In this thesis the application of clustering algorithms for solving the Hierarchical Ring Network
Problem (HRNP) is investigated.
When the network is represented as a graph, an informal problem definition for this NPcomplete
problem is: Given a set of network sites (nodes) assigned to one of three layers and
the costs for establishing connections between sites (i.e., edge costs) the objective is to find a
minimum cost connected network under certain constraints that are explained in detail in the
thesis. The most important constraint is that the nodes have to be assigned to rings of bounded
size that connect the layers hierarchically.
The ring structure is a good compromise between the robustness of a network and the cost
for establishing it. It is guaranteed, that the network can continue to provide its service if one
network node per ring fails.
The basic idea in this thesis for solving this network design problem was to cluster the sites
with hierarchical clustering heuristics and to use the resulting hierarchy as support for the ringfinding
heuristics. Previous apporaches for related network design problems did not use the
inherent network structure in such a way. Usual approaches are based on greedy heuristics.
Three clustering heuristics were implemented: Girvan-Newman, K-means and Kernighan-
Lin. Especially the first algorithm is interesting, because it was successfully applied analyzing
large network structures, also in the context of internet communities.
For finding rings three heuristics were implemented too. Strategic variation of the maximum
allowed ring size helps the first heuristic to find rings using the cluster hierarchy. The second
heuristic finds rings by searching for paths that are connected to previously found rings. Third a
repair heuristic was implemented that tries to add remaining nodes to existing rings.
Local search heuristics are applied last to improve the solution quality.
To check how the clustering approach performs for solving the problem of this thesis two
test instance generators were implemented. One generates instances randomly and the second
generates instances based on the popular TSPLIB archive.
The evaluation of the random test instances has shown, that all three clustering heuristics
were able to solve those test instances, while Girvan-Newman and Kernighan-Lin found valid
solutions in each test run this was not possible for K-means. When Kernighan-Lin was used as
clustering algorithm solutions could be found faster on average, but the resulting costs where
slightly higher. For the TSPLIB based instances the clustering algorithms had more problems to
find valid solutions, but for each test instance at least one type of clustering was successful.

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