Inhalt

1. Einleitung
2. Definition
   • Das Traveling Salesman Problem
   • Komplexität von Algorithmen
     • Die O-Notation
     • Die Klassen und
   • Testinstanzen
3. Das TSP in der Praxis
   • Platinenproduktion
   • Auftrags-Abarbeitung in einem Lagerhaus
   • Kristall-Analyse
   • Zuschneiden von Tapeten
   • Gruppierung von Datenfeldern
   • Verwaltung eines Fuhrparks
4. Bekannte Lösungsstrategien
   • Kandidatenmengen
     • Nächste Nachbarn
     • Delaunay Graph
   • Konstruktive Heuristiken
     • Nearest-Neighbour Heuristik
     • Insertion Heuristiken
     • Doubletree-Heuristik
     • Verfahren von Christofides
     • Savings Heuristik
     • Greedy Algorithmus
   • Iterative Verfahren
     • Node und Edge Insertion
     • 2-Opt Verfahren
     • Lin-Kernighan-Heuristiken
     • Simulated Annealing, Genetische Algorithmen
5. Eine Heuristik mit iteriertem Matching
   • Begriffsdefinitionen
   • Skizze des Lösungsalgorithmus
   • Darstellung einer Lösung
   • Speichern mehrerer Wege
   • Wahl der Benefitfunktion
   • Einsatz von Kandidatenmengen
   • Zusammenfassen zweier Knoten
   • Vor- und Nachbereitung des Matchings
     • Berechnung des Pre-Benefits
       • Bestmögliche Kombination
       • Durchschnitt aller Kombinationen
       • Schlechteste Kombinationsmöglichkeit
       • Abstand der Schwerpunkte
     • Kandidatenmengen auf echten Clustergraphen
   • Artikulationskanten
   • Zusammenfassende Beschreibung des Algorithmus
6. Ergebnisse und Vergleich
   • Einfluß der Parameter auf die Ergebnisse
     • Einsatz der Kandidatenmengen
     • Wahl der Benefitfunktion
     • Einfluß der Benefit-Optionen
     • Einfluß der Selektion
   • Ergebnisse im Vergleich zu anderen Heuristiken
7. Beschreibung der Benutzeroberfläche
   • Menüführung
   • Darstellung des Graphen und der Lösung
   • Einstellung der Parameter
   • Abfrage statistischer Daten
8. Zusammenfassung und Ausblick
9. References