Clustering Heuristics for the Hierarchical Ring Network Problem
Type:
Master thesis
Proceedings:
Publisher:
Institut für Computergraphik und Algorithmen
Pages:
ISBN:
Year:
2011
Abstract:
In this thesis the application of clustering algorithms for solving the Hierarchical Ring Network<br> Problem (HRNP) is investigated.<br> When the network is represented as a graph, an informal problem definition for this NPcomplete<br> problem is: Given a set of network sites (nodes) assigned to one of three layers and<br> the costs for establishing connections between sites (i.e., edge costs) the objective is to find a<br> minimum cost connected network under certain constraints that are explained in detail in the<br> thesis. The most important constraint is that the nodes have to be assigned to rings of bounded<br> size that connect the layers hierarchically.<br> The ring structure is a good compromise between the robustness of a network and the cost<br> for establishing it. It is guaranteed, that the network can continue to provide its service if one<br> network node per ring fails.<br> The basic idea in this thesis for solving this network design problem was to cluster the sites<br> with hierarchical clustering heuristics and to use the resulting hierarchy as support for the ringfinding<br> heuristics. Previous apporaches for related network design problems did not use the<br> inherent network structure in such a way. Usual approaches are based on greedy heuristics.<br> Three clustering heuristics were implemented: Girvan-Newman, K-means and Kernighan-<br> Lin. Especially the first algorithm is interesting, because it was successfully applied analyzing<br> large network structures, also in the context of internet communities.<br> For finding rings three heuristics were implemented too. Strategic variation of the maximum<br> allowed ring size helps the first heuristic to find rings using the cluster hierarchy. The second<br> heuristic finds rings by searching for paths that are connected to previously found rings. Third a<br> repair heuristic was implemented that tries to add remaining nodes to existing rings.<br> Local search heuristics are applied last to improve the solution quality.<br> To check how the clustering approach performs for solving the problem of this thesis two<br> test instance generators were implemented. One generates instances randomly and the second<br> generates instances based on the popular TSPLIB archive.<br> The evaluation of the random test instances has shown, that all three clustering heuristics<br> were able to solve those test instances, while Girvan-Newman and Kernighan-Lin found valid<br> solutions in each test run this was not possible for K-means. When Kernighan-Lin was used as<br> clustering algorithm solutions could be found faster on average, but the resulting costs where<br> slightly higher. For the TSPLIB based instances the clustering algorithms had more problems to<br> find valid solutions, but for each test instance at least one type of clustering was successful.
TU Focus:
Computational Science and Engineering
Reference:
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.
Zusätzliche Informationen
Last changed:
16.12.2011 10:30:28
TU Id:
202034
Accepted:
Accepted
Invited:
Department Focus:
Business Informatics
Info Link:
https://publik.tuwien.ac.at/showentry.php?ID=202034&lang=1
Abstract German:
In dieser Diplomarbeit wird die Anwendung von Clusteringalgorithmen untersucht, um das<br> Hierarchical Ring Network Problem (HRNP) zu lösen.<br> Wenn das Netzwerk als Graph repräsentiert ist, ist dieses NP-vollständige Problem wie folgt<br> definiert: Gegeben ist Menge von Knoten welche jeweils einer von drei Schichten zugewiesen<br> sind, und eine Kostenfunktion, welche die Verbindungskosten zwischen zwei Knoten<br> (d.h. Kantenkosten) zuweist. Gesucht ist ein zusammenhängendes Netzwerk mit minimalen<br> Gesamtkosten, wobei dieses bestimmte Struktureigenschaften zu erfüllen hat, welche im Detail<br> in der Diplomarbeit beschrieben werden. Die wichtigste dieser Eigenschaften ist, dass Knoten<br> gemäß einer hierarchischen Struktur zu größenbeschränkten Ringen verbunden werden.<br> Ringstrukturen sind ein guter Kompromiss zwischen der Verfügbarkeit von Netzwerken und<br> deren Herstellungskosten. Die Verfügbarkeit ist gewährleistet, solange maximal ein Knoten pro<br> Ring ausfällt.<br> Die grundlegende Idee dieser Diplomarbeit um dieses Netzwerkdesign-Problem zu lösen,<br> ist die Knoten mit Hilfe von hierarchischen Clusteringalgorithmen anzuordnen und die resultierende<br> Hierarchie für nachfolgende Heuristiken zu verwenden, welche die Ringe finden.<br> Vorhergehende Ansätze für vergleichbare Netzwerkdesign-Probleme haben die inhärente<br> Netzwerkstruktur nicht auf solche Weise genützt und eher Greedy-Heuristiken eingesetzt.<br> Um gültige Ringe zu finden, wurden drei Heuristiken implementiert. Strategisches Variieren<br> der erlaubten Ringgröße hilft der ersten Heuristik Ringe unter Benützung der Cluster-Hierarchie<br> zu finden. Die zweite Heuristik baut auf den in der vorherigen Schicht gefundenen Ringen auf,<br> indem sie nach gültigen Pfaden sucht, die an diese Ringe angeschlossen werden können. Drittens<br> wird eine Reparaturheuristik angewendet, welche versucht verbleibende Knoten zu bestehenden<br> Ringen zuzuweisen.<br> Zuletzt werden lokale Suchverfahren eingesetzt, um die Gesamtkosten zu verbessern.<br> Um zu überprüfen, wie gut dieser Lösungsansatz funktioniert, wurden zwei Testinstanz-<br> Generatoren implementiert. Der Erste generiert Instanzen zufallsbasiert, der Zweite baut auf<br> dem bekannten TSPLIB-Archiv auf.<br> Die Evaluierung der zufallsbasierten Testinstanzen hat gezeigt, dass alle drei Heuristiken<br> sämtliche Instanzen lösen konnten, wobei Girvan-Newman und Kernighan-Lin in jedem Testlauf<br> Lösungen gefunden haben, war dies bei K-means nicht der Fall. Mit Kernighan-Lin<br> konnte im Durchschnitt schneller eine Lösung gefunden werden, aber die Gesamtkosten waren<br> bei den beiden anderen Algorithmen etwas besser. Mit den TSPLIB-basierten Testinstanzen<br> konnte nicht mit allen Clusteringalgorithmen eine Lösung erzielt werden, aber zumindest war<br> für jede Testinstanz mindestens ein Clustering-Verfahren erfolgreich.