Travelling-Salesman-Problem
Travelling-Salesman-Problem Definition
Das Travelling-Salesman-Problem (kurz: TSP) ist ein Optimierungsproblem, genauer: ein Tourenplanungsproblem.
Ein Handlungsreisender (Travelling Salesman, z.B. ein Staubsaugervertreter) muss eine bestimmte Anzahl von Städten (z.B. Aachen, Bonn und Celle) besuchen; dabei soll jede Stadt nur einmal besucht werden.
Der Handlungsreisende macht eine Rundreise bzw. Tour: er beginnt in einer Stadt (z.B. Aachen), fährt zur nächsten (z.B. Bonn), dann weiter zur nächsten (z.B. Celle) und kehrt wieder zurück zu der Stadt, in der er angefangen hat (Aachen).
Die mit dem Auto gefahrenen km, d.h. die gesamte Wegstrecke der Rundreise, soll minimal sein, um Auto-/Treibstoffkosten zu sparen.
Alternativ könnten auch andere Kriterien als die Strecke optimiert werden, z.B. die Fahrzeiten minimiert (diese hängen ja nicht nur von der Strecke, sondern auch von dem Straßentyp (Autobahn oder Landstraße), Geschwindigkeitsbegrenzungen usw. ab).
Um das Problem anzugehen – eine wirklich optimale Lösung kann auch mit rechenstarken Computern nicht immer gefunden werden –, werden nur die Entfernungen zwischen jeweils 2 Städten benötigt (am besten als Tabelle).
Alternative Begriffe: Problem des Handlungsreisenden, Rundreiseproblem, Traveling-Salesman-Problem, Travelling-Salesperson-Problem.
Beispiel
Beispiel: Travelling Salesman Problem
Ein Vertreter muss die 3 Städte (A)achen, (B)onn und (C)elle besuchen.
Die (fiktiven) Entfernungen seien:
Aachen - Bonn : 100 km
Aachen - Celle: 200 km
Bonn - Celle: 300 km
Bei so wenigen Städten kann man die möglichen Touren noch an einer Hand abzählen, so dass man keinen Algorithmus braucht:
1. Möglichkeit: A - B - C - A = 100 + 300 + 200 = 600 km
2. Möglichkeit: A - C - B - A = 200 + 300 + 100 = 600 km
Mehr Varianten gibt es bei 3 Städten nicht, beide Touren sind hier gleich lang.
Es gibt bei s Städten (s - 1)! Möglichkeiten (dabei steht ! für Fakultät, dafür gibt es auf dem Taschenrechner eine Taste: x!):
bei 3 Städten also (3-1)! = 2! = 2 × 1 = 2 Möglichkeiten;
bei 4 Städten (4-1)! = 3! = 3 × 2 × 1 = 6 Möglichkeiten;
...
bei 10 Städten bereits (10-1)! = 9! = 362.880 Möglichkeiten.
Allerdings ist jeweils die Hälfte der gefundenen Rundreisen eine Umkehrung (mit gleicher Wegstrecke). Deshalb reicht es, die Hälfte der Touren zu berechnen, bei 3 Städten also 1 statt 2 (oben sah man auch, dass beide Touren gleich lang sind).