Titelaufnahme

Titel
Computergestützte Analyse zur Variantenuntersuchung der MST-Heuristik für das Rundreiseproblem / Miachel Pirih
Verfasser/ VerfasserinPirih, Michael
Begutachter / BegutachterinPferschy, Ulrich
Erschienen2014
UmfangIV, 53 Bl. : Zsfassungen (2 Bl.) ; graph. Darst.
HochschulschriftGraz, Univ., Masterarb., 2014
Anmerkung
Zsfassungen in dt. und engl. Sprache
SpracheDeutsch
DokumenttypMasterarbeit
Schlagwörter (GND)Travelling-salesman-Problem / Minimal spannender Baum / Travelling-salesman-Problem / Minimal spannender Baum / Online-Publikation
URNurn:nbn:at:at-ubg:1-62129 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
Computergestützte Analyse zur Variantenuntersuchung der MST-Heuristik für das Rundreiseproblem [0.52 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

Diese Forschungsarbeit befasst sich mit einer Variante der MST-Heuristik zur Findung von Lösungen für das Rundreiseproblem. Die Variante erstellt zulässige Startlösungen basierend auf dem minimal spannenden Baum eines Graphen. Bei der Anwendung wird ein spezieller Fokus auf Knoten der konvexen Hülle und eines eigens um den Schwerpunkt definierten Bereiches gelegt ? das Schwerpunktareal. Das Ziel ist es, bei Analyse dieser beiden Knotenteilmengen Empfehlungen zu formulieren, ob ein strukturiertes Vorgehen Vorteile mit sich bringt oder nicht. Dadurch sollen Zeitvorteile in der Berechnung entstehen gleichzeitig aber sehr gute Lösungen erzielt werden. Als Datenbasis dient ein in Matlab geschriebener Quellcode, der zulässige Rundreisen auf Basis der Variante der MST-Heuristik für zufällige Ausgansgraphen im Intervall x,y ?[0,10] erstellt. Vor allem auf Rundreisen, deren Startknoten Teil der konvexen Hülle oder des Schwerpunktareals sind, wird ein spezieller Fokus gelegt. Das Ziel der Analyse von konvexer Hülle und Schwerpunktareal ist die Berechnung der Erfolgsrate. Diese Erfolgsrate steht für die Wahrscheinlichkeit bei ausschließlicher Untersuchung der Knoten aus konvexer Hülle bzw. des Schwerpunktareals zumindest eine Rundreise zu finden, die nicht mehr als 5 % von der besten Lösung abweicht. Als Vergleichsbasis dient eine zufällig gewählte Stichprobe, deren Ergebnisse die Aussagekraft der Werte aus konvexer Hülle und Schwerpunktareal überprüfen soll. Der Vergleich von Ergebnissen aus konvexer Hülle und Schwerpunktareal mit der zufällig erstellten Stichprobe führt zur Schlussfolgerung, dass die geringfügig höheren Erfolgsraten der beiden analysierten Knotenmengen in keiner Relation zur benötigten Zeit für die Erstellung dieser beiden Mengen stehen. Es kann konstatiert werden, dass für diese Variante der MST-Heuristik eine willkürliche Auswahl an Knoten der Erstellung der konvexen Hülle oder des Schwerpunktareals stets zu bevorzugen ist.

Zusammenfassung (Englisch)

This paper deals with a variant of the MST-heuristic for finding starting solutions for the Traveling Salesman Problem. The variant creates proper starting solutions based on the Minimum Spanning Tree of a graph. By creating tours based on this variant of the MST-heuristic there is a special focus on nodes of the convex hull and on an area around the centroid. This area is especially created for the purpose of this research. This area is called centroid area. The paper tries to answer the question if it is possible to find qualitative advantages by solely analyzing nodes from these two sets. For this purpose every node from the two sets is used as a starting point to create a tour based on the variant of the MST-heuristic. The data is based on a Matlab source code. This source code creates random starting solutions within a range of x,y ?[0,10] and applies the variant of the MST-heuristic to create tours. One main purpose of this paper is to define a success rate for the two sets. This success rate refers to the probability that by solely analyzing one of the two sets you find at least one solution that differs not more than 5 % from the best one found by this variant. For testing the significance of the success rates, two random samples are created. These random samples include the same amount of nodes as the set of the convex hull and the centroid area. The idea behind this random sample is to test, if a structured approach, such as the convex hull or the centroid area, leads to a better solution than a randomized approach. The comparison of each set with its random sample leads to the conclusion that a randomized approached is preferable. The success rates of the structured approaches are only a little bit higher than the ones of the randomized approach. If you consider the time for defining the two sets of the structured approached it can be concluded that an arbitrarily picking of nodes is better.