Das Problem des Handlungsreisenden. Ein Kompendium

Inhaltsverzeichnis

• Einleitung und Motivation dieser Arbeit
• Definitionen, Konventionen, Begriffe und Problemstellung des TSP
  • Aktuelle Ergebnisse und Rekorde - Die Geschichte des TSP
  • Einordnung des TSP
    • Komplexitätstheorie
    • Entscheidungs- und Optimierungsproblem
    • TSP in NP und NP-schwere des Problems
  • Asymmetrisches, symmetrisches und metrisches TSP
  • Hamiltonischer Kreis (Hamiltonkreis) und Euler Weg
  • Multiple-TSP (mTSP) und Vehicle Routing Problem (VRP)
• TSP exakt lösen
  • Brute Force
  • Dynamische Programmierung
  • Branch and Bound
• Approximierbarkeit des TSP
  • Nearest Neighbor und Greedy
  • Insertion Heuristiken
  • Minimum Spanning Tree (MST)
  • Christofides
  • K-Opt Verbesserungsverfahren
  • Lin-Kernighan (LK) und Lin-Kernighan-Helsgaun (LKH)
• Fazit und Ausblick
• Literaturverzeichnis
• Abbildungsverzeichnis

Zielsetzung und Themenschwerpunkte

Die vorliegende Studienabschlussarbeit widmet sich dem Problem des Handlungsreisenden (Traveling Salesman Problem, TSP), einem klassischen Minimierungsproblem aus der theoretischen Informatik. Ziel ist es, ein umfassendes Kompendium zu diesem Thema zu erstellen, das die Geschichte, Definition, Einordnung und Lösungsansätze des TSP beleuchtet.

• Die Geschichte des TSP und die wichtigsten Meilensteine in der Lösungsfindung
• Die Einordnung des TSP in die Komplexitätstheorie und die NP-Vollständigkeit
• Die verschiedenen Arten des TSP, wie das asymmetrische, symmetrische und metrische TSP
• Exakte Lösungsverfahren, wie Brute Force, dynamische Programmierung und Branch and Bound
• Approximationsalgorithmen, sogenannte Heuristiken, zur effizienten Näherung an optimale Lösungen

Zusammenfassung der Kapitel

Die Arbeit beginnt mit einer Einführung in die Problematik des Handlungsreisenden. Sie definiert den TSP und erläutert die verschiedenen Arten und Begrifflichkeiten, die mit diesem Problem verbunden sind. Die Einordnung des TSP in die Komplexitätstheorie wird beleuchtet, wobei die NP-Vollständigkeit des Problems im Vordergrund steht. Es werden verschiedene Varianten und Spezialfälle des TSP, wie das asymmetrische, symmetrische und metrische TSP, sowie das Multiple-TSP und das Vehicle Routing Problem, vorgestellt.

Die Arbeit widmet sich anschließend den Verfahren zur exakten Lösung des TSP, darunter die Brute Force Methode, die dynamische Programmierung und das Branch and Bound Verfahren. Die Limitationen und die exponentielle Laufzeit dieser Methoden werden diskutiert.

Im weiteren Verlauf werden verschiedene Approximationsalgorithmen, sogenannte Heuristiken, vorgestellt, die in Polynomialzeit gute Näherungslösungen liefern. Dazu gehören Verfahren wie Nearest Neighbor, Greedy, Insertion Heuristiken, Minimum Spanning Tree, Christofides und das Lin-Kernighan Verfahren. Die Funktionsweise und die Approximationsgüte dieser Algorithmen werden anhand von Beispielen erläutert. Die Arbeit beleuchtet auch die Weiterentwicklung des Lin-Kernighan Algorithmus durch Keld Helsgaun, den Lin-Kernighan-Helsgaun (LKH) Algorithmus, der einen neuen Standard in der Tourenfindung setzt.

Schlüsselwörter

Die Schlüsselwörter und Schwerpunktthemen des Textes umfassen das Problem des Handlungsreisenden (Traveling Salesman Problem, TSP), die Komplexitätstheorie, NP-Vollständigkeit, exakte Lösungsverfahren, Approximationsalgorithmen, Heuristiken, Brute Force, dynamische Programmierung, Branch and Bound, Nearest Neighbor, Greedy, Insertion Heuristiken, Minimum Spanning Tree, Christofides, Lin-Kernighan, Lin-Kernighan-Helsgaun (LKH), Simulated Annealing, genetische Algorithmen, Ant Colonies und Ant Colony Optimization (ACO).