TSP Software 1
Inhaltsverzeichnis
NOCH IN BEARBEITUNG !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Theorie
Das 'Traveling Salesman Problem' (auch 'Problem des Handlungsreisenden') ist ein kombinatorisches Optimierungsproblem. Dabei besteht auf Aufgabe darin, eine optimale Reihenfolge für den Besuch von Knotenpunkten (z.B. Städte, Bohrungen ect.) zu finden. Das Kriterium, welches es dabei zu minimieren gilt, kann unterschiedlich sein; beispielweise kann es sinnvoll sein die Wegstrecke (Längeneinheiten), die Zeit (Zeiteinheiten) und/oder die Kosten (Geldeinheiten) oder eine Mischung aus diesen Kriterien heran zu ziehen.
Des Weiteren gibt es unterschiedliche Restriktionen für die TS-Problemantik:
Um das Beispiel so einfach wie möglich zu halten, minimieren wir die Wegstrecke und grenzen Kanten (z.B. Straßen) aus; jeder Punkt kann also frei mit jedem anderen Punkt verbunden werden.
Beispiel:
Um eine Städtereise zu planen bei denen 4 verschiedene Städte (A, B, C, D) angefahren werden sollen, gibt es (n - 1)! mögliche Routen: In diesem Fall also (4 - 1)! = 6.
In diesem Fall sind die Graphen gerichtet - es gibt also zwei unterschiedliche Wege eine Route zu befahren (auch die optimale Route).
Nach dieser Formel steigt die mögliche Lösungsmenge also mit jeder weiteren Stadt wie folgt an:
Städte: mögliche Routen: Laufzeit (3GHz Single Core):
3 2 0,063 sec
4 6 0,073 sec
5 24 0,078 sec
6 120 0,109 sec
7 720 0,125 sec
8 5.040 0,156 sec
9 4.0320 0,187 sec
10 262.880 0,265 sec
11 3.628.800 1,279 sec
12 39.916.800 12,293 sec (ca. Laufzeit von n=11 x 12)
13 479.001.600 143,474 sec (ca. Laufzeit von n=12 x 13)
14 6.227.020.800 29,987 min (ca. Laufzeit von n=13 x 14)
15 87.178.291.200 ~ 7,400 h (ca. Laufzeit von n=14 x 15)
16 1.307.674.368.000 ~ 5,000 d (ca. Laufzeit von n=15 x 16)
17 20.922.789.888.000 ~ 85,000 d (ca. Laufzeit von n=16 x 17)
18 355.687.428.096.000 ~ 4,200 y (ca. Laufzeit von n=17 x 18)
19 6.402.373.705.728.000 ~ 80,000 y (ca. Laufzeit von n=18 x 19)
20 121.645.100.408.832.000 ~ 1,600 ty (ca. Laufzeit von n=19 x 20)
Berechnung einer Route
Wie berechnet der Computer eine Strecke?
Zu allererst muss man dazu wissen wie man den Abstand 2 er Punkte im Koordinatensystem misst. Dazu benutzen wir den Satz des Pythagoras:
Man nehme zwei Punkte A(ax|ay), B (bx|by) im Koordinatensystem. Der Abstand dieser Punkte wäre dann also:
Punktabstand: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sqrt{(ax - bx)^2 + (ay - by)^2}
Wie berechnet der Computer eine Route?
Der Computer misst den Abstand jedes Punktes zu seinem Nachfolger und addiert dann das Ergebnis um so die gesamte Strecke zu bestimmen.
Route: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum_{i=0}^{n-1} \sqrt{(a_{}ix - b_{}ix)^2 + (a_{}iy - b_{}iy)^2}
Wie berechnet der Computer die schnellste Route?
Er berechnet die Route für jede mögliche Permutation und speichert sich die aktuell kürzeste Strecke ab. Ist eine neu berechnete Strecke kürzer als die Bisherige, so wird diese ersetzt. Wurden für alle möglichen Permutationen die Strecken berechnet, bleibt am Ende nur die kürzeste übrig - diese wird dann ausgegeben.
Lösungsverfahren
Um das TSP zu lösen ist eine Vielzahl von Algorithmen und Heuristiken bekannt, die teilweise in OR behandelt werden.
Exakte Lösungsverfahren
- Branch and Bound (Branch and Cut)
Heuristiken
Lösungsansätze
Quellen
- Wikipedia Eintrag zum TSP ausführliche Informationen zum Traveling Salesman Problem
- Algorithmus der Woche TSP oder die optimale Tour für den Nikolaus
- Online Touren-Planer kostenloser TSP-Solver zur Routenoptimierung
