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 & Themen
Die Arbeit analysiert und vergleicht verschiedene heuristische Ansätze zur Lösung des Traveling Salesman Problems (TSP), um deren Effizienz und Lösungsqualität bei der Minimierung von Distanzen in logistischen Netzwerken zu bewerten.
- Methodische Analyse deterministischer Konstruktionsheuristiken (Nearest Neighbor, Farthest Insertion, Christofides).
- Evaluierung von Verbesserungsverfahren (insb. 2-opt) zur Nachoptimierung von Rundreisen.
- Untersuchung von Metaheuristiken am Beispiel von Tabu Search zur Überwindung lokaler Optima.
- Praktische Anwendung der Algorithmen auf eine spezifische TSP-Instanz (dr13).
- Vergleichende Gegenüberstellung der Algorithmen hinsichtlich Laufzeitkomplexität und Abweichung vom Optimum.
Auszug aus dem Buch
3.1.1 Nearest Neighbor Heuristik
Der Algorithmus des Nächsten Nachfolgers oder Nachbarn verfolgt einen simplen Ablauf. Gegeben eines willkürlich oder auch bewusst gewählten Startknotens v1 werden iterativ j = {2, ..., n} weitere Knoten vj der Tour hinzugefügt, bis alle Knoten in die Rundreise eingebunden sind, also vn ∈ V. Es wird jeweils der Knoten vj der Tour hinzugefügt, der die kürzeste Distanz zum zuletzt zugefügten Knoten vj-1 aufweist. Der Algorithmus ist flexibel für STSP und ATSP mit einer geschätzten Zeitkomplexität O(n²) anwendbar (vgl. Domschke und Scholl, 2010; vgl. Reinelt 1994).
Domschke und Scholl (2010) und Reinelt (1994) beschreiben die Prozedur des nächsten Nachbarn Heuristik zur Berechnung einer ersten Rundreise im STSP wie folgt:
Start Nächster Nachfolger
(1) Wähle zufälligen Knoten v1, F := 0.
(2) Iteration j = {2, ..., n}:
(2.1) Ermittle Knoten vj durch cvj-1vj = min {cvj-1i | i ∈ V − {v1, ..., vj-1}}.
(2.2) Bilde eine Kette [v1, ..., vj-1, vj].
(2.3) Setze F := F + cvj-1vj.
(3) Schließe die Tour [v1, ..., vn, v1]; setze F := F + cvnv1.
Ende Nächste Nachfolger
Zusammenfassung der Kapitel
1. Einleitung: Die Einleitung erläutert die ökonomische Relevanz effizienter Logistik und führt in das Traveling Salesman Problem (TSP) als zentrales kombinatorisches Optimierungsproblem ein.
2. Das Rundreiseproblem: Dieses Kapitel liefert historische Hintergründe, die graph-theoretische Modellierung, mathematische Formulierungen sowie eine Diskussion der Komplexität und NP-Schwere des TSPs.
3. Heuristische Verfahren: Der Hauptteil analysiert deterministische Konstruktionsheuristiken wie Nearest Neighbor, Farthest Insertion und Christofides sowie Verbesserungsverfahren wie 2-opt.
4. Metaheuristische Verfahren zur Lösung des TSP: Hier werden fortgeschrittene Ansätze wie Tabu Search beschrieben, um die Limitierungen lokaler Suchverfahren durch die Zulassung temporärer Verschlechterungen zu umgehen.
5. Fazit: Das Fazit fasst die Analyseergebnisse zusammen und gibt eine fundierte Empfehlung zur Wahl des geeigneten Algorithmus je nach Anforderung an Geschwindigkeit oder Optimierungsgüte.
Schlüsselwörter
Traveling Salesman Problem, TSP, STSP, Heuristik, Konstruktionsheuristiken, Verbesserungsverfahren, 2-opt, Tabu Search, Optimierung, Distanzmatrix, Hamiltonkreis, Laufzeitkomplexität, NP-schwer, Knoten, Rundreise.
Häufig gestellte Fragen
Worum geht es in dieser Bachelorarbeit grundsätzlich?
Die Arbeit untersucht verschiedene mathematische und heuristische Verfahren zur effizienten Lösung des sogenannten Traveling Salesman Problems, einer zentralen Fragestellung der logistischen Routenplanung.
Was sind die zentralen Themenfelder der Arbeit?
Neben der theoretischen Einbettung in die Graphentheorie bilden die Analyse von Konstruktionsalgorithmen, Nachoptimierungsmethoden und die Anwendung metaheuristischer Verfahren die inhaltlichen Säulen.
Welches primäre Ziel verfolgt der Autor?
Ziel ist es, Approximationsalgorithmen bezüglich ihrer Effizienz, Laufzeit und Lösungsqualität systematisch zu evaluieren und auf eine spezifische Instanz anzuwenden, um deren praktische Eignung zu bestimmen.
Welche wissenschaftliche Methodik wird verwendet?
Die Arbeit kombiniert theoretische Analysen mathematischer Modelle mit einer empirischen Untersuchung anhand der Beispiel-Instanz „dr13“, um die Heuristiken direkt miteinander zu vergleichen.
Was wird im Hauptteil der Arbeit behandelt?
Der Hauptteil gliedert sich in die Vorstellung deterministischer Konstruktionsheuristiken, die Erläuterung von Verbesserungsverfahren zur lokalen Optimierung und die Analyse von Metaheuristiken wie Tabu Search.
Welche Schlüsselbegriffe charakterisieren die Arbeit?
Wesentliche Begriffe sind unter anderem Traveling Salesman Problem (TSP), Nearest Neighbor, Farthest Insertion, Christofides-Heuristik, 2-opt Verfahren, Tabu Search und die Komplexitätstheorie.
Warum schneidet Farthest Insertion im Vergleich oft besser ab?
Durch das frühe Einfügen der am weitesten entfernten Knoten werden die groben Umrisse der Tour bereits zu Beginn des Algorithmus festgelegt, was eine stabilere Gesamtstruktur begünstigt.
Warum scheitern reine Verbesserungsverfahren wie 2-opt manchmal an der Nachoptimierung?
Diese Verfahren sind in lokalen Optima „gefangen“; wenn keine Kantenänderung mehr eine sofortige Verkürzung der Tour bewirkt, beendet der Algorithmus die Suche, ohne das globale Optimum zu erreichen.
- Quote paper
- Dominik Richter (Author), 2013, Single Vehicle Round-Trip Routing. Das Problem des Handlungsreisenden, Munich, GRIN Verlag, https://www.grin.com/document/302684
