Schuster, R. (2011). Clustering heuristics for the hierarchical ring network problem [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-58321
E186 - Institut für Computergraphik und Algorithmen
-
Date (published):
2011
-
Number of Pages:
59
-
Keywords:
Clustering; Hierarchie; Ringe
de
clustering; hierarchy; rings
en
Abstract:
In dieser Diplomarbeit wird die Anwendung von Clusteringalgorithmen untersucht, um das 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 definiert: Gegeben ist Menge von Knoten welche jeweils einer von drei Schichten zugewiesen sind, und eine Kostenfunktion, welche die Verbindungskosten zwischen zwei Knoten 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.<br />Die grundlegende Idee 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. 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.<br />Zuletzt werden lokale Suchverfahren eingesetzt, um die Gesamtkosten zu verbessern.<br />Um den Lösungsansatz zu überprüfen, wurden zwei Testinstanz-Generatoren implementiert, ein zufallsbasierter und einer der auf dem bekannten TSPLIB-Archiv aufbaut.<br />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.<br />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.<br />
de
In this thesis the application of clustering algorithms for solving the Hierarchical Ring Network Problem (HRNP) is investigated.<br />When the network is represented as a graph, an informal problem definition for this NP-complete problem is: Given a set of network sites (nodes) assigned to one of three layers and the costs for establishing connections between sites the objective is to find a minimum cost connected network under certain constraints that are explained in detail in the thesis. 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.<br />Three clustering heuristics were implemented: Girvan-Newman, K-means and Kernighan-Lin.<br />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.<br />Third a 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 test instance generators were implemented. One generates instances randomly and the second generates instances based on the popular TSPLIB archive.<br />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 were 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.