Das Travelling-Salesman-Problem
Finde eine Rundreise/"Tour" möglichst kurzer Länge,
die jede von n gegebenen Städten genau einmal besucht
und zum Ausgangspunkt zurückkehrt. In den Beispielen
unten (n Punkte/"Knoten" im [0,1]x[0,1] Quadrat, jeden Tag neu!) kommt jeweils
nur ein Punkt dazu, dennoch verändert sich die beste Tour
meist deutlich. Versuche selbst die beste Tour
zu finden, indem Du die Knoten der Reihe nach
anklickst!
Eigenes Problem hochladen
"Klick"-Regeln:
- Nur Knoten sind durch Klick markierbar (rot unterlegt), ein zweiter Klick
entfernt die Markierung.
- Wird zu einem markierten Knoten mit keiner oder einer Verbindung/"Kante"
ein zweiter solcher markiert, fügt dies eine Kante
zwischen beiden ein; der zweite Knoten bleibt markiert.
- Hat ein markierter Knoten bereits zwei Kanten, ist nur einer
der zwei "benachtbarten" Knoten markierbar; das markiert die
Kante.
- Eine markierte Kante kann über einen Button gelöscht werden.
- Ist eine Kante markiert und wird dazu ein weiterer Knoten
markiert, wird dieser zwischen die zwei Knoten der Kante
eingefügt/umgehängt.
Zur Mathematik des Problems
Das Travelling-Salesman Problem (kurz TSP) heißt auf Deutsch das Rundreiseproblem oder das Problem des Handlungsreisenden und ist eines der
klassischen kombinatorischen Optimierungsprobleme. Es tritt sowohl direkt in
dieser Form als auch als Teilproblem in vielen praktischen Anwendungen
auf (alles, was mit reihenfolgeabghängigen Übergangszeiten/-längen/-kosten zu tun hat: Routenplanung für Auslieferungsdienste, Reihenfolgeplanung in
der Produktion, Färbungsreihenfolgen in der Autoindustrie, Bearbeitungsfolgen von Schweißpunkten in der Robotik, etc.). Aus komplexitätstheoretischer Sicht gehört es zur Klasse der NP-vollständigen Probleme, d.h., man kann zwar Lösungen leicht auf ihre Richtigkeit überprüfen, aber vermutlich gibt es keinen Algorithmus, der die beste Lösung nachweislich immer in "kurzer" Zeit findet.
Anhand dieses Problems wurde eine Vielzahl an algorithmischen Lösungsansätzen zur Behandlung kombinatorischer Optimierungsaufgaben entwickelt und erprobt. Das Spektrum reicht von reiner Zufallssuche über Approximationsalgorithmen bis hin zur exakten Lösung riesiger Aufgaben. Letztere basieren auf der Formulierung und Lösung sogenannter linearer Relaxationen. Darunter darf man sich hochdimensionale Polyeder vorstellen, durch die man die möglichen Lösungen möglichst eng
umfängt. Über diese Polyeder kann man nun effizient die Optimallösung hinsichtlich einer linearen Zielfunktion (hier Summe der Kantenlängen) mit linearen Optimierungsalgorithmen bestimmen. Um die exakte Lösung zu finden, muss man dies nun mit Rundungsmethoden und systematischen Suchtechniken (branch-and-bound) verbinden. Dazu sei auf die sehr schöne Internetseite zum derzeit besten Lösungsalgorithmus Concorde verwiesen.
Die neuesten Arbeiten an unserer Professur zu diesem Thema beschäftigen sich
mit quadratischen Kostenstrukturen, in denen der Aufwand nicht mehr nur von zwei direkt aufeinanderfolgenden Städten, sondern nun von jeweils drei Städten in Folge abhängt. Damit lassen sich etwa auch gute Touren für den Fall suchen, dass spitze Winkel als ungünstig erachtet werden. Letzteres ist zum Beispiel in Anwendungen der Robotik von Bedeutung.