Traveling-Salesman-Problem

Das Traveling-Salesman-Problem (auch: Rundreiseproblem) TSP gehört zu den kombinatorischen Optimierungsproblemen. Es handelt sich hierbei um ein Rundreiseproblem, bei welchem mehrere Orte unter Minimierung der Reisezeit oder der Kosten nacheinander angesteuert werden sollen. Dabei darf ein Ort nur einmal besucht werden. Die Reihenfolge ist dabei nicht von Bedeutung. 

Für die Lösung des Traveling-Salesman-Problem stehen eine Vielzahl an heuristischen und exakten Methoden zur Verfügung. Bevor mit dem Verfahren begonnen werden kann, muss dieses durch ein einfaches Modell abgebildet werden. Dies geschieht mithife eines Graphen.  

Ungerichteter unvollständiger Graph

In der obigen Grafik ist ein solcher Graph abgebildet. Die Knoten $i = 1, 2, 3, 4$ repräsentieren die Städte, die besucht werden sollen. Die ungerichteten Kanten $(i,j)$ zeigen die Verbindung zwischen den Städten an. Zu jeder Kante existieren Kosten, Zeiten oder Weglängen $c_{ij}$, welche bei Verwendung dieser Strecke anfallen. Diese Kosten bzw. Zeiten gilt es zu minimieren. Dabei darf jeder Knoten nur einmal angesteuert werden (Hamiltonkreis).

Die ungerichteten Kanten bedeuten, dass die Kantenlänge in beide Richtungen identisch sind. Die Fahrt von Stadt 1 zur Stadt 2 ist also genau so lang, wie die Fahrt von Stadt 2 zu Stadt 1.

Vollständiger Graph

Der obige Graph ist unvollständig, weil nicht alle Knoten eine direkte Verbindung zu den anderen Knoten aufweisen. Es existiert keine direkte Verbindung von der Stadt 1 zur Stadt 4. Dies könnte zum Beispiel an einer Sperrung der Autobahn liegen, an Baustellen oder eben an einer fehlenden Verbindung, so dass die Stadt 4 nur über Stadt 3 oder Stadt 2 erreichbar ist. 

Zur Vereinfachung des Problems wird der Graph so aufgestellt, dass er vollständig ist. Das bedeutet, dass zwischen zwei Knoten immer eine Kante existiert. Dies wird erreicht, indem dort wo keine Kante (also keine Verbindung) existiert eine Kante mit der Kantenbewertung $c_{ij} = \infty$ eingeführt wird. Aufgrund der hohen Länge und dem Ziel der Minimierung, wird eine solche Kante nie in die kürzeste Tour aufgenommen. 

Ungerichteter vollständiger Graph

Asymmetrisches und symmetrisches TSP

In der obigen Grafik ist der vollständige Graph mit ungerichteten Kanten angegeben. Ungerichtete Kanten bedeuten, dass die Kantenlänge von einem Knoten zum anderen in beide Richtungen identisch ist. Man spricht auch von einem symmetrischen TSP.

Bei einem asymmetrischen TSP hingegen, ist die Kantenlänge von einem zum anderen Knoten nicht in beide Richtungen identisch. Für diesen Fall müssen innerhalb des Graphen gerichtete Kanten verwendet werden:

Asymmetrischer vollständiger Graph

In der obigen Grafik ist ein asymmetrischer Graph gegeben, weil auch gerichtete Kanten im Graphen vorhanden sind. Der Graph kann natürlich auch vollständig aus gerichteten Kanten bestehen. 

Grund für die unterschiedlichen Kantenlängen können zum Beispiel Baustellen, Sperrungen, Staus etc sein. 

Das Traveling Salesman Problem kann entweder symmetrisch oder asymmetrisch sein. 

In den nächsten Abschnitten werden die folgenden Verfahren zur Lösung eines Traveling-Salesman-Problems aufgezeigt:

• Vollständige Enumeration
  
  
• Verfahren des besten Nachfolgers
  
  
• Verfahren der sukzessiven Einbeziehung von Stationen
  
  
• Branching-and-Bounding.