Das Rundreise- oder auch Travelling Salesman Problem ist eines der bekanntesten Probleme der kombinatorischen Optimierung. Leicht zu verstehen und daher häufig vorschnell als einfach lösbar eingestuft, stellte und stellt es die Wissenschaft immer noch vor große Herausforderungen, denn die Ergebnisfindung gestaltet sich schon bei geringer Problemgröße aufgrund sehr großer Lösungsräume als äußerst schwierig.
Die Nachbarschaftssuche ist ein heuristisches Verfahren, das sehr gut zur Ermittlung der Lösung eines Rundreiseproblems eingesetzt werden kann. Durch den Vergleich verschiedener alternativer Lösungen erfolgt eine schrittweise Annäherung an das optimale Ergebnis, das in einer Minimierung der Reisekosten liegt. Dieses Prinzip machen sich alle in dieser Arbeit vorgestellten Heuristiken zu Nutze. Die Güte des Ergebnisses variiert dabei in Abhängigkeit von den jeweiligen Verfahrensregeln. In Kapitel 2 wird zunächst das Travelling Salesman Problem vorgestellt. In seiner Eigenschaft als Benchmark für Forschung und Entwicklung sind im Laufe der Zeit vor dem Hintergrund der schweren Lösbarkeit vielfältige Methoden entwickelt worden, die auf verschiedene Art und Weise zu Lösungen führen. Die bisher effizientesten und damit am häufigsten einsetzbaren Methoden sind Heuristiken, die jedoch nur annähernd optimale Ergebnisse liefern. In Kapitel 3 wird zunächst der Begriff Heuristik definiert. Im Anschluss daran folgt die Erläuterung der Systematik der Nachbarschaftssuche in ihrer Eigenschaft als Basis für heuristische Verfahren im Allgemeinen und im Hinblick auf den Zielgedanken des Rundreiseproblems. Der Darstellung eines Eröffnungsverfahrens, schließen sich in den nächsten Unterkapiteln Ausführungen zu Optimierungsverfahren an. Am Beispiel zweier r-optimaler Verfahren wird die Anwendung von reinen Verbesserungsverfahren in Bezug auf das Rundreiseproblem dargestellt. Simulated Annealing und Tabu Search dienen als Beispiele für lokale Suchverfahren im selben Kontext. Abschließend erfolgt ein kurzer Blick in das Feld der Forschung, die sich mit der Entwicklung immer neuer Varianten und Methoden von auf Nachbarschaftssuche basierenden Optimierungsverfahren beschäftigt.
Inhaltsverzeichnis
1 Einleitung
2 Das Travelling Salesman Problem
2.1 Eine Benchmark des Operations Research
2.2 Lösungsmethoden
3 Heuristiken
3.1 Nachbarschaftssuche
3.2 Eröffnungsverfahren
3.3 Verbesserungsverfahren und lokale Suchverfahren
3.3.1 Reine Verbesserungsverfahren
3.3.1.1 2-opt Verfahren
3.3.1.2 3-opt Verfahren
3.3.2 Lokale Suchverfahren
3.3.2.1 Simulated Annealing
3.3.2.2 Tabu Search
4 Ausblick
5 Literatur
6 Abbildungen
Zielsetzung & Themen
Die vorliegende Arbeit untersucht heuristische Optimierungsverfahren am Beispiel des klassischen Travelling Salesman Problems. Ziel ist es, die Funktionsweise verschiedener Algorithmen zur Nachbarschaftssuche zu analysieren und deren Effektivität bei der Bewältigung kombinatorischer Optimierungsprobleme zu bewerten.
- Grundlagen des Travelling Salesman Problems als Benchmark im Operations Research.
- Systematik und Funktionsweise der allgemeinen Nachbarschaftssuche.
- Differenzierung zwischen Eröffnungsverfahren, reinen Verbesserungsverfahren und lokalen Suchverfahren.
- Praktische Analyse der Verfahren 2-opt, 3-opt, Simulated Annealing und Tabu Search.
Auszug aus dem Buch
3.3.2.1 Simulated Annealing
Das Simulated Annealing wurde in Anlehnung an einen thermodynamischen physikalischen Abkühlungsprozess entwickelt. Wird ein Metall zunächst stark, bis über seinen Schmelzpunkt hinaus erhitzt und dann wieder abgekühlt, so lassen sich in Abhängigkeit vom Kühlvorgang Unterschiede in der Beschaffenheit des wieder erkalteten Materials entdecken. Wiederholtes Erhitzen und erneutes langsames Abkühlen führen zur besseren Ausbildung der Kristallstruktur und damit zu einer höheren Qualität des Endprodukts.
Im Hinblick auf die Zielsetzungen des Travelling Salesman Problems ist der Verfahrensablauf des Simulated Annealing wie folgt darzustellen: Unter Einsatz einer Transformationsvorschrift, z. B. des 2-opt Verfahrens, wird auf Basis einer zulässigen Rundreise x eine Nachbarlösung x’ ∈ N(x) bestimmt. Sind die Kosten dieser Rundreise geringer als jene der ursprünglichen, so wird das Verfahren mit x’ als Basislösung fortgesetzt. Sind sie höher, wird ein Übergang zu x’ nicht generell verworfen. Die Verschlechterung wird mit einer gewissen Wahrscheinlichkeit P(∆,α) zugelassen; mit ∆ als Variable für die Höhe der Verschlechterung und der reellwertigen Hilfsvariablen α (α > 1) als vorgegebenen Temperaturparameter. Abbildung 10 erfasst die Verfahrensregeln des Simulated Annealing in Form eines Pseudo-Codes.
Zusammenfassung der Kapitel
1 Einleitung: Diese Einleitung führt in die Problemstellung des Travelling Salesman Problems ein und erläutert die Bedeutung heuristischer Methoden für kombinatorische Optimierungsprobleme.
2 Das Travelling Salesman Problem: Hier wird das Problem als klassische Benchmark des Operations Research vorgestellt und die mathematische Zielsetzung der Wegoptimierung definiert.
3 Heuristiken: Das Kapitel definiert den Begriff der Heuristik und erläutert die methodischen Grundlagen der Nachbarschaftssuche, Eröffnungsverfahren sowie lokale Suchverfahren wie Simulated Annealing und Tabu Search.
4 Ausblick: Der Ausblick reflektiert den aktuellen Forschungsstand zu heuristischen Optimierungsverfahren und deutet zukünftige Entwicklungen im Bereich der kombinatorischen Optimierung an.
Schlüsselwörter
Travelling Salesman Problem, Kombinatorische Optimierung, Heuristik, Nachbarschaftssuche, Operations Research, 2-opt Verfahren, 3-opt Verfahren, Lokale Suchverfahren, Simulated Annealing, Tabu Search, Zielfunktion, Komplemente, Tabuliste, Kostenminimierung, Optimierungsprozess.
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit befasst sich mit der Optimierung des Travelling Salesman Problems durch den Einsatz verschiedener heuristischer Verfahren.
Was sind die zentralen Themenfelder?
Die zentralen Felder sind die kombinatorische Optimierung, die Anwendung der Nachbarschaftssuche sowie die Implementierung von Verbesserungs- und lokalen Suchstrategien.
Was ist das primäre Ziel der Arbeit?
Das Ziel ist die Erläuterung und der Vergleich unterschiedlicher heuristischer Methoden, um annähernd optimale Lösungen für das Rundreiseproblem zu finden.
Welche wissenschaftliche Methode wird verwendet?
Die Arbeit nutzt Literaturanalysen und vergleicht Algorithmen (Pseudo-Codes), um die Struktur von Nachbarschaftssuchen und deren Verhalten bei der Lösungsfindung zu demonstrieren.
Was wird im Hauptteil behandelt?
Der Hauptteil gliedert sich in die Darstellung des Travelling Salesman Problems, die Definition von Heuristiken sowie die detaillierte Beschreibung von 2-opt, 3-opt, Simulated Annealing und Tabu Search.
Welche Schlüsselwörter charakterisieren die Arbeit?
Wichtige Begriffe sind Travelling Salesman Problem, Heuristik, Nachbarschaftssuche, Simulated Annealing und Tabu Search.
Warum ist Simulated Annealing ein lokales Suchverfahren?
Es wird als solches klassifiziert, da es durch die stochastische Akzeptanz auch schlechterer Lösungen die Gefahr umgeht, dauerhaft in einem lokalen Optimum gefangen zu bleiben.
Wie vermeidet Tabu Search das Kreisen in lokalen Optima?
Tabu Search verwendet eine „Tabuliste“ als künstliches Gedächtnis, das bestimmte Züge für eine gewisse Zeit sperrt und so verhindert, dass das Verfahren bereits besuchte Lösungen unmittelbar wiederholt.
- Quote paper
- Christian Hippe (Author), 2004, Optimierung mittels Nachbarschaftssuche am Beispiel des Rundreiseproblems, Munich, GRIN Verlag, https://www.grin.com/document/44152
