Seit mehreren Jahrzehnten werden Heuristiken konzipiert, um sich dem TSP möglichst gut anzunähern. Dennoch ist es bis heute nicht gelungen einen Algorithmus zu schreiben, der jede TSP Problemgröße optimal lösen kann. Deswegen ist es von enormer Bedeutung die bereits bestehenden Approximationsalgorithmen bezüglich ihrer Attribute und Lösungsqualität zu evaluieren.
Ziel dieser Ausarbeitung ist, die Nearest Neighbor Heuristik, Farthest Insertion und den Algorithmus von Christofides zu analysieren und untereinander zu vergleichen. Zusätzlich werden diese drei Heuristiken separat und in Verbindung mit dem 2-opt Verfahren an einem eigens implementierten Beispiel „dr13“ angewendet. Nachdem einige weitere Annäherungsmethoden zur Übersicht vorgestellt werden, wird die Metaheuristik Tabu Search1 ebenfalls evaluiert und fortführend anhand der Beispielimplementierung getestet, sodass die erhöhte Leistungsfähigkeit von Metaheuristiken gegenüber reinen Nachoptimierungsverfahren deutlich wird.
Inhaltsverzeichnis
- 1. Einleitung
- 2. Das Rundreiseproblem
- 2.1 Herkunft und Ziel des Reisenden
- 2.2 Graphentheorie
- 2.3 Mathematische Formulierung des STSP
- 2.4 Komplexität
- 3. Heuristische Verfahren
- 3.1 Konstruktionsheuristiken
- 3.1.1 Nearest Neighbor Heuristik
- 3.1.2 Farthest Insertion
- 3.1.3 Christofides' Heuristik
- 3.2 Verbesserungsheuristiken
- 3.2.1 2-opt Heuristik
- 3.2.2 Übersicht reiner Verbesserungsverfahren
- 4. Metaheuristische Verfahren zur Lösung des TSP
- 4.1 Metaheuristiken
- 4.2 Tabu Search
- 5. Fazit
Zielsetzung und Themenschwerpunkte
Die vorliegende Bachelorarbeit befasst sich mit dem "Traveling Salesman Problem" (TSP), einem klassischen Problem der kombinatorischen Optimierung, das darin besteht, die kürzeste Route zu finden, die alle Knoten eines gegebenen Graphen genau einmal besucht. Das Ziel der Arbeit ist es, verschiedene Heuristiken und Metaheuristiken zur Lösung des TSP zu analysieren und zu vergleichen.
- Analyse und Vergleich verschiedener Heuristiken, insbesondere Nearest Neighbor, Farthest Insertion und Christofides' Heuristik.
- Bewertung der Leistungsfähigkeit von Heuristiken in Kombination mit Verbesserungsverfahren wie 2-opt.
- Einführung in das Konzept der Metaheuristiken und die Evaluierung der Tabu Search Methode.
- Anwendung der analysierten Verfahren auf ein praktisches Beispiel.
- Bewertung der Effizienz und Genauigkeit der verschiedenen Ansätze.
Zusammenfassung der Kapitel
Kapitel 1 führt in das Thema des TSP ein und erläutert die Relevanz des Problems in der heutigen Zeit. Kapitel 2 stellt das TSP in seiner mathematischen Formulierung vor und beleuchtet die Komplexität des Problems. Kapitel 3 befasst sich mit verschiedenen Heuristiken, die zur Annäherung an eine optimale Lösung des TSP eingesetzt werden können. Kapitel 4 widmet sich Metaheuristiken, insbesondere der Tabu Search Methode, die eine höhere Effizienz und Genauigkeit gegenüber reinen Heuristiken aufweisen. Kapitel 5 fasst die Ergebnisse der Arbeit zusammen und diskutiert die Bedeutung der verschiedenen Ansätze für die Lösung des TSP.
Schlüsselwörter
Traveling Salesman Problem, Heuristiken, Metaheuristiken, Tabu Search, Nearest Neighbor, Farthest Insertion, Christofides' Heuristik, 2-opt, kombinatorische Optimierung, Graphentheorie, Komplexität, Approximationsalgorithmen.
- Citation du texte
- Dominik Richter (Auteur), 2013, Single Vehicle Round-Trip Routing. Das Problem des Handlungsreisenden, Munich, GRIN Verlag, https://www.grin.com/document/302684
