Problem des Handlungsreisenden

aus ZUM-Wiki, dem Wiki für Lehr- und Lerninhalte auf ZUM.de
Wechseln zu: Navigation, Suche

Das Problem des Handlungsreisenden – TSP (travelling salesman problem)

Das TSP ist ein vor allem in der Logistik weit verbreitetes Problem, das aber auch unter Mathematikern und Informatikern ein heißes Thema ist, da es bis heute keinen Algorithmus zur Berechnung ohne exponentiellen Zeitaufwand gibt.

Die Aufgabe besteht darin, einen günstigsten Weg (W) durch eine beliebige Anzahl (n) Orte (V) zu finden. Unterschieden wird dabei zwischen asymmetrischem, symmetrischem und metrischem TSP.

Asymmetrisch bedeutet dass jeder Weg eine Richtung hat, daher der Weg W von Ort A nach Ort B nicht gleich dem Weg BA sein muss. Dies kann sich praktisch durch ungleich ausgebaute Straßen, Baustellen etc. ergeben. Symmetrisch dagegen bedeutet, dass jeder Weg ohne Richtung ist. Also gilt: AB = BA. In unserem Modell betrachten wir das metrische TSP. Das metrische TSP ist symmetrisch mit der zusätzlichen Bedingung der Erfüllung der Dreiecksgleichung (▲abc; |a-b| ≤ c ≤ a+b; Seite1 < Seite2 + Seite 3) die besagt, dass die Summe von 2 Seiten immer Größer oder gleich der Dritten sein muss. Übertragen auf unser Modell bedeutet dass, dass sich Umwege nicht lohnen. (Der direkte Weg von Ort A zu Ort B ist kürzer oder genausolang wie der Weg von Ort A über Ort C zu Ort B). In unserem Modell wollen wir außerdem einen Hamilton-Kreis, also einen geschlossenen Kreis der durch jeden Punkt nur einmal geht, abbilden.

Das Problem bei der Berechnung des kürzesten Weges stellt die im besten Fall mit n exponentiell steigende benötigte Rechenzeit dar, da es keine Berechnung für den kürzesten Weg gibt, sondern dieser nur über ‚Durchprobieren‘ (Brute Force) erlangt werden kann. Allerdings kann man einen Rahmen setzen (längster / kürzester Weg).

Für die Anzahl der Möglichkeiten bei n=5 Orten gilt für ein asymmetrisches TSP (n-1)! Also 4! = 4*3*2*1 = 24 Mögliche Wegkombinationen. Diese Zahl halbiert sich, ist das TSP symmetrisch. Da zB. ABCDE = EDCBA gibt es (n-1)!/2 Möglichkeiten also 12.

Bei 10 Städten wären das jedoch bereits 10! = 10*9*8*6*5*4*3*2*1 = 3628800 Möglichkeiten. Es gibt eine naive Möglichkeit um sich dem optimalem Weg zu nähern. Dabei geht man vom Startpunkt aus und geht immer zum nächst nahestehenden, noch nicht verwendeten Knoten bis man wieder zum Ausgangspunkt zurückkommt. Es kann jedoch passieren (vor allem bei einer großen Knotenmenge), dass man dadurch einen ungünstigen Weg einschlägt und man daher wieder einen oder mehrere Schritte zurückgehen muss.

Eine andere Möglichkeit ist das einfache Ausprobieren. Da sich das TSP mathematisch nicht berechnen lässt und unser Beispiel mit 5 Knoten noch in einem Rahmen liegt besteht die Aufgabe nun darin, alle Kombinationen zu finden. Anschließend müssen die einzelnen Wegstrecken addiert werden. Der kürzeste Weg ist unser günstigster Weg und damit die Lösung des TSP.


Chriatian Mathe tsp grafik.png


Mögliche Lösungswege Addition der Teilstrecken eines Lösungsweges Gesamtstrecke des Lösungsweges
a ABCDEA 21+35+27,5+27+30 140,5
b ABCEDA 21+35+20+27+10 113
c ABDCEA 21+15+27,5+20+30 113,5
d ABDECA 21+15+27+20+36 119
e ABECDA 21+40,5+20+27,5+10 119
f ABEDCA 21+40,5+27+27,5+36 152
g ACBDEA 36+35+15+27+30 143
h ACBEDA 36+35+40,5+27+10 148,5
i ACDBEA 36+27,5+15+40,5+30 149
j ACEBDA 36+20+40,5+15+10 121,5
k ADBCEA 10+15+35+20+30 110
l ADCBEA 10+27,5+35+40,5+30 143