Titelaufnahme

Titel
Entwicklung und Implementierung von Algorithmen zur Optimierung von Drehbewegungen in der Tourenplanung / Andreas Tramper
Weitere Titel
Development and implementation of algorithms for optimizing angular motion in route planning
Verfasser/ VerfasserinTramper, Andreas
Begutachter / BegutachterinPferschy, Ulrich
ErschienenGraz, September 2016
Umfang49 Blätter : Zusammenfassungen (2 Blatt) ; Illustrationen
HochschulschriftKarl-Franzens-Universität Graz, Masterarbeit, 2016
Anmerkung
Abweichender Titel laut Übersetzung des Verfassers/der Verfasserin
Zusammenfassungen in Deutsch und Englisch
SpracheDeutsch
DokumenttypMasterarbeit
Schlagwörter (GND)Tourenplanung / Algorithmus
URNurn:nbn:at:at-ubg:1-105148 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
Entwicklung und Implementierung von Algorithmen zur Optimierung von Drehbewegungen in der Tourenplanung [0.56 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

Das Traveling Salesman Problem beschäftigt sich mit der Ermittlung einer günstigsten (kürzesten) Verbindung einer Menge von Knoten mittels Kanten, wobei jeder Knoten mit genau zwei Kanten verbunden ist, und durch die Verbindung sämtlicher Knoten ein Kreis (eine Tour) gebildet wird. Beim Quadratischen Traveling Salesman Problem wird ebenfalls die günstigste Tour gesucht, wobei je zwei in der Tour hintereinander angeordneten Kanten ein Kostenwert zugewiesen ist. Diese Arbeit umfasst die Implementierung und Darlegung von Heuristiken für das symmetrische Angular Traveling Salesman Problem und das symmetrische AngularDistance Traveling Salesman Problem. Beim Angular Traveling Salesman Problem werden die Winkel in den Knoten, die sich durch eine Tour ergeben als zu minimierende Kosten betrachtet. Beim Angular-Distance Traveling Salesman Problem werden Winkeländerungen und Distanzen in Kombination berücksichtigt. Es wird ausgeführt, dass die genannten Probleme nicht effizient optimal lösbar sind. Daher ist es sinnvoll, sich einer heuristischen Methoden zur Lösungsfindung zu bedienen. Zum einen werden klassische Ansätze des Traveling Salesman Problems wie zum Beispiel die Nearest Neighbor Methode aufgegriffen. Zum anderen werden völlig neu entwickelte Heuristiken wie zum Beispiel die Verwendung von konvexen Hüllen vorgestellt, welche die geometrische Struktur der Knoten als Punkte in der Ebene nutzen. Die in der Arbeit verwendeten mathematischen Aspekte werden formal eingeführt und die implementierten Heuristiken verbal, technisch und in Form von Pseudocodes präsentiert. Eine umfangreiche Auswertung vergleicht die Ergebnisse der Heuristiken auf Testinstanzen mit den bereits bekannten Optimalwerten und mit heuristischen Resultaten aus der Literatur. Es zeigt sich, dass die neu entwickelten Algorithmen eine deutliche Verbesserung gegenüber bisher bekannten Methoden liefern.

Zusammenfassung (Englisch)

The Traveling Salesman Problem asks for a cheapest (shortest) connection of nodes from a node set by a selection of arcs. Thereby it has to be considered, that each node is connected to exactly two arcs and furthermore, that the result yields exactly one cycle, called a tour. The Quadratic Traveling Salesman Problem also asks for a cheapest tour, but in this case any two in a tour consecutive arcs are assigned a certain cost value. This master thesis enfolds the development and implementation of heuristics for the symmetric Angular Traveling Salesman Problem and the symmetric Angular-Distance Traveling Salesman Problem. For the Angular Traveling Salesman Problem the angles at nodes, which are formed by creating a tour, are the cost factors which should be minimized. For the Angular-Distance Traveling Salesman Problem these angles and the distances between the nodes are considered in combination. It is stated, that the mentioned problems cannot be solved optimally in an efficient way. Therefore, for finding solutions, it is useful to use heuristic approaches. This master thesis presents classical approaches used for the Traveling Salesman Problem like the Nearest Neighbor method and moreover new developed heuristics like working with convex hulls, which are using the special geometrical structure of the nodes which are given as points in the plane. Mathematical terms used in this thesis get introduced in a formal way and the implemented heuristics are explained verbally, technically and in the form of pseudocodes. An extensive evaluation compares the heuristic results with already known optimal values and with heuristic results from reference literature. It can be shown, that the new developed algorithms can distinctly outperform previously known methods.