TSP Software 1: Unterschied zwischen den Versionen

Version vom 26. Juni 2013, 15:19 Uhr

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 Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (n - 1)!

mögliche Routen: In diesem Fall also Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (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_{i}x - b_{i}x)^2 + (a_{i}y - b_{i}y)^2}

Wie berechnet der Computer die schnellste Route (durch Permutation)?

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

- Minimal Spanning Tree

- Nearest Neighbor

- Nearest Insertion Heuristik

Implementiertes Verfahren

(Ähnlichkeiten zu RANDIN-Algorithmus)

Man betrachte drei Punkte im Koordinaten System A, B, C mit beliebigen Koordinaten, wobei A der Start und Endpunkt darstellt. Um einen Kreislauf zu bilden hat man nun 2 Möglichkeiten ((3-1)! = 2! = 2):

A -> B -> C-> A

A -> C -> B -> A

Beide Kreisläufe haben jedoch die gleiche Strecke, da sich lediglich die Richtung ändert. Damit wissen wir, dass egal wie wir 3 Punkte im Koordinatensystem verbinden, wir immer die optimale Strecke haben. Genau hier setzt unsere Heuristik an. Es werden 3 beliebige Punkte ausgewählt, über die wir wissen, dass ihre Verbindungsstrecke optimal ist:

A -> B -> C -> A

Kommt jetzt ein weiterer beliebiger Punkt D hinzu, so wird überprüft, an welcher Stelle D einzusetzen ist, damit die Router weiterhin optimal bleibt:

A->B -> C -> D -> A

A->B -> D -> C -> A

A->D -> B -> C -> A

Die Heuristik braucht bei 4 Punkten also 3 Möglichkeiten zu berechnen während die Permutation 6 bräuchte. Dieser Unterschied ist bei wenigen Punkten noch vernachlässigbar klein, aber mit wachsender Punktanzahl steigt dieser Unterschied stark an (s. Tabelle).

Wir nehmen einmal an A->B -> C -> D -> A wäre optimal.

Soll nun ein weiterer beliebiger Punkt E angefahren werden, so wird wieder die vorher optimale Strecke verwendet um zu überprüfen, an welcher Stelle Punkt E optimal in die Route integriert werden kann:

A->B -> C -> D -> E -> A

A->B -> C -> E -> D -> A

A->B -> E-> C -> D -> A

A->E -> B-> C -> D -> A

Wieder wird die beste Kombination ausgewählt um dann einen weiteren Punkt hinzuzufügen.

Auf diese Weise braucht der Computer nur Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum_{i=0}^{n-1} i

Schritte anstatt Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.):   (n-1)!

Die Resultate decken sich wie im folgenden Beispiel zu sehen oft mit der optimalen Lösung, wobei nur ein Bruchteil der Zeit benötigt wird:

13 Knoten:

60 Knoten:

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