Travelling Salesman Problem

Was das Travelling Salesman Problem ist und wie es gelöst wird, erfährst du hier und im Video dazu!

Inhaltsübersicht

Travelling Salesman Problem einfach erklärt

Das Travelling Salesman Problem (kurz TSP) ist ein Problem aus dem Bereich der Optimierung. Es besteht darin, die beste Reiseroute zwischen einer bestimmten Anzahl an Orten zu finden.

Das Problem entsteht beispielsweise, wenn ein Paketbote vier verschiedene Orte in möglichst kurzer Zeit besuchen soll. Das Ziel ist es, die schnellste Route zu finden. Zum Lösen verwendest du verschiedene Algorithmen. Dabei gibt es exakte und heuristische Lösungen:

  • Exakte Lösung: Sie ist die beste von allen möglichen Routen. Jedoch nimmt der Rechenaufwand mit steigenden Orten sehr stark zu. Schon ab 15 bis 20 Orten sind mit heutiger Technik keine exakten Lösungen mehr möglich.
  • Heuristische Lösung: Hierbei handelt es sich um Annäherungen. Mit ihnen kann das TSP auch für deutlich mehr Orte gelöst werden.
NP Problem

NP Probleme sind in der Informatik Probleme, die mit heutiger Technik praktisch nicht lösbar sind. Das Travelling Salesman Problem ist ein bekanntes NP Problem. Der Grund dafür ist die schnell ansteigende Komplexität:

Beispielsweise gibt es für 4 Städte 3·2·1 / 2 = 3 unterschiedliche Routen. Für 10 Städte sind es bereits 9·8·…·1 / 2 = 181.440 verschiedene Wege. Bei n Städten gibt es allgemein (n-1)! / 2 („!“ = Fakultät ) verschiedene Routen. Sind Hin- und Rückweg einer Strecke unterschiedlich lang, handelt es sich um (n-1)! verschiedene Routen.

Travelling Salesman Problem — grafische Darstellung

Ein Paketbote möchte jetzt die 4 Städte A, B, C und D besuchen. Um das Problem vereinfacht darzustellen, modellierst du es in einem Graphen. Dabei stellen die Punkte („Knoten“) die Städte und die Linien („Kanten“) die Wege dar.

Alle Städte werden miteinander verbunden. An die Linien schreibst du die jeweilige Reisedauer (bspw. in Minuten). Alternativ zur Reisedauer können dort auch andere Ressourcen stehen, wie: Entfernung, Kosten, Emissionen oder Kraftstoff.

Travelling Salesman Problem; Travelling Salesman; Traveling Salesman Problem; Traveling Salesman; Travelling Salesman Problem Graph; Travelling Salesman Problem Knoten; Travelling Salesman Problem Kanten
direkt ins Video springen
Travelling Salesman Problem mit 4 Orten

Der Handlungsreisende startet bei A und möchte alle Städte anfahren und am Ende wieder in A landen. Die grüne Linie ist eine mögliche Route. Addierst du die jeweiligen Zeiten, kommst du auf 5 + 5 + 20+ 15 = 45 min. 

Travelling Salesman Problem; Travelling Salesman; Traveling Salesman Problem; Traveling Salesman; Travelling Salesman Problem Graph; Travelling Salesman Problem Knoten; Travelling Salesman Problem Kanten
direkt ins Video springen
Travelling Salesman Problem mit 4 Orten

Es gibt aber eine bessere Lösung. Folgt er der orangenen Route, benötigt er nur 40 min (15 + 10 + 5 + 10).

Gerichtete und ungerichtete Kanten

In der Realität sind die Wege in Hin- und Rückrichtung häufig verschieden lang. Das kann beispielsweise durch eine Baustelle auf einer Straßenseite vorkommen. Daher wird in gerichtete und ungerichtete Kanten (Wege) unterteilt. Bei gerichteten Kanten sind Hin- und Rückweg verschieden lang. Dagegen sind ungerichtete Kanten in beide Richtungen gleich lang.

Travelling Salesman Problem; Travelling Salesman; Traveling Salesman Problem; Traveling Salesman; Travelling Salesman Problem Graph; Travelling Salesman Problem Knoten; Travelling Salesman Problem Kanten
direkt ins Video springen
Travelling Salesman Problem mit 4 Orten

Jetzt ist die rote Route mit einer Zeit von 5 + 5 + 10+ 15 = 35 min der schnellste Weg.

Übrigens: Kommen ungerichtete Kanten im Graphen vor, sprichst du von einem asymmetrischen Graphen. Liegen nur gerichtete Kanten vor, ist der Graph symmetrisch.

Travelling Salesman Problem — Algorithmen

Um das Travelling Salesman Problem zu lösen und die beste Route zu finden, werden verschiedene Algorithmen verwendet. 

Für kleinere Probleme können exakte Lösungsalgorithmen verwendet werden. Neben der Brute-Force-Methode, die einfach alle Lösungen nacheinander ausprobiert, zählen dazu:

Um auch größere Probleme zu lösen, verwendest du heuristische Algorithmen. Dazu zählen unter anderem:

  • der Nearest-Neighbor-Algorithmus
  • der 2-Opt-Algorithmus

Die Wissenschaft versucht dabei, immer bessere Algorithmen zu finden. Ein möglicher Ansatz ist der Einsatz von künstlicher Intelligenz und Quantencomputern. Mit ihnen könnte es in Zukunft auch exakte Lösungen für deutlich mehr als 15-20 Orte geben.

Travelling Salesman Problem — häufigste Fragen

  • Was ist das Travelling Salesman Problem?
    Das Travelling Salesman Problem behandelt die Frage, welche Route die schnellste ist, um alle gegebenen Orte zu besuchen. Zur Lösung gibt es aufwendige, exakte Lösungsverfahren und vereinfachte Näherungsverfahren.
     
  • Was ist ein Travelling Salesman Problem Beispiel?
    Ein typisches Beispiel ist ein Paketbote, der fünf verschiedene Orte anfahren soll. Das Travelling Salesman Problem ist es, die beste Route zu finden.

     
  • Wie löst man das Travelling Salesman Problem?
    Das Problem wird durch exakte oder heuristische Algorithmen gelöst. 

Branch-and-Bound Algorithmus

Jetzt weißt du, was das Travelling Salesman Problem ist. Um das Problem zu lösen, gibt es verschiedene Lösungsalgorithmen. Einer der Bekanntesten ist der Branch-and-Bound Algorithmus. Hier im Beitrag erfährst du, wie genau er das Problem löst.

Zum Video: Branch & Bound
Zum Video: Branch & Bound

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte .