Single Vehicle Round-Trip Routing. Das Problem des Handlungsreisenden

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.