Beim Travelling Salesman Problem wird eine Route gesucht, die eine gegebene Anzahl an Knoten verbindet. Sollen beispielsweise die Städte Hamburg, Bremen, Stuttgart, München und Köln besucht werden, muss eine Besuchsreihenfolge festgelegt werden.

Viele verschiedene Möglichkeiten sind dabei denkbar. Hier zwei Beispiele:

• Berlin – Hamburg – Stuttgart – Bremen – München – Köln – Berlin (rote Tour)
• Berlin – München – Stuttgart – Köln – Bremen – Hamburg – Berlin (grüne Tour)

Hier lässt sich leicht erkennen, dass die grüne Tour insgesamt viel kürzer als die rote ist. Um nun z.B. Kosten oder Zeit zu sparen, würde jeder ökonomisch denkender Mensch, der alle Städte besuchen muss die grüne Tour nehmen. Das TSP hat hier genau einen Startpunkt an dem der Reisende zum Ende der Tour wieder ankommen muss.

Dieses Beispiel ist so einfach, dass die grüne Tour gefunden wird, wenn in jeder Stadt einfach die nächstgelegene angefahren wird. Leider liefert diese Heuristik des nächsten Nachbarn oft sehr schlechte Routen.

Für das TSP gibt es vielfältige Lösungsalgorithmen. Ein berühmtes Beispiel ist der Ameisenalgorithmus. Dabei werden verschiedene Varianten der Rundreise durchgerechnet und die beste vorgeschlagen. Mathematisch wird dabei immitiert, dass bei der Wahl des als nächstes zu besuchenden Ortes, Kanten (z.B. Straßen) gewählt werden, die sich schon bei vorherigen möglichen Rundreisen als sinnvoll erwiesen haben.

Ein weiteres sehr einfaches Verfahren ist der Threshold Accepting Algorithmus, bei dem irgendeine Route durch Verändern der Besuchsreihenfolge verbessert wird. Dabei werden einfach zwei Orte in der Reihenfolge getauscht und es entsteht eine neue Rundreise.

Beide Algorithmen ist in der folgenden Excel Datei als Macros implementiert. Auf der ersten Seite („dij“) müssen dazu die Entfernungen von jeden zu jedem anderen Knoten eingegeben werden.

TSPalgorithmen
Auf der Seite http://www.gebweb.net/optimap/ lässt sich das TSP bedeutend einfacher ausprobieren. Dabei können beliebige Orte auf der ganzen Welt zur Generierung einer Rundreise eingegeben werden.