Traveling Salesman Problem

Hinter dem Problem des Handlungsreisenden verbirgt sich ein Optimierungsproblem. Die Ausgangslage dieses Problems ist, dass ein Handlungsreisender (z. B. ein Vertreter für Elektromaschinen) eine bestimmte Anzahl von Städten besuchen muss, um seine Produkte zu verkaufen. Hierbei ist es vorgegeben, dass jede Stadt nur einmal besucht werden darf. Zur Lösung des Problems werden die Entfernungen von mindestens zwei Städten benötigt. Hierbei kann zwischen der praktischen Methode und der mathematischen Methode unterschieden werden.

In diesem Beitrag zeigen wir dir, was sich hinter dem Problem des Handlungsreisenden verbirgt. Wir erklären dir, was du über das Problem des Handlungsreisenden wissen musst und welche Rolle ein ungerichteter Graph hierbei spielt. Du erfährst, ob das Problem des Handlungsreisenden durch ein Nähverfahren gelöst werden kann und welcher Unterschied zwischen der mathematischen Methode und der praktischen Methode besteht. Abschließend stellen wir den Praxisbezug des “travelling salesman problems” anhand eines Beispiels dar. Damit du genau über das Problem des Handlungsreisenden Bescheid weißt, kannst du nach dem Abschnitt einige Übungsfragen beantworten.

• Englisch: traveling salesman problem
• Abkürzung: TSP

Was solltest du über das Problem des Handlungsreisenden wissen?

Die Tätigkeit eines Handlungsreisenden ist mit einer Tour durch mehrere Städte verbunden. Weil für die Rundreise möglichst wenig Zeit aufgewendet werden soll, besteht für den Handlungsreisenden das Problem, die beste Alternative für den Weg festzulegen. Sinnvoll ist es, wenn dieses Problem des Handlungsreisenden vor Beginn der Tour gelöst wird.

Erster Ansatzpunkt für die Lösung des Problems, dass ein Handlungsreisender hat, ist die Tatsache, dass er zum Schluss der Tour wieder an seinem Ausgangspunkt ankommt. Deshalb geht er von hier aus, wenn er nach dem kürzesten Weg zur nächsten Stadt sucht. Die Zeit, die der Handlungsreisende für die gesamte Tour einplant, stellt aber nur einen Faktor dar. Für ihn kommt es darüber hinaus auch darauf an, dass er sich für die kostengünstigste Lösung entscheidet.

Die Zeit lässt sich dahin gehend beeinflussen, dass der Handlungsreisende nicht immer nach der kürzesten Lösung sucht. Auch mit der Berücksichtigung des Straßentyps kann der Handlungsreisende Vorteile für sich schaffen, um sein Problem zu lösen.

Welche Rolle spielt der ungerichtete Graph?

Der ungerichtete Graph kommt zum Einsatz, wenn das Problem des Handlungsreisenden am Computer gelöst wird. In diesem Graphen werden Knoten markiert, die die einzelnen Städte darstellen sollen.

Für die Verbindung der einzelnen Knoten nutzt der Handlungsreisende Kanten. Diese werden von dem Computer so angelegt, dass der Handlungsreisende jede Stadt nur einmal zu besuchen braucht. Hierdurch ist das grundlegende Problem des Handlungsreisenden gelöst. Unterstützt wird diese Darstellung durch die in der Grafik eingefügten Kantengewichte. Hiermit wird deutlich, welche Länge eine einzelne Verbindung hat.

Wird das Problem des Handlungsreisenden durch ein Näherungsverfahren gelöst?

Die Lösung des Problems, das ein Handlungsreisender auf seiner Tour hat, kann mit Unterstützung des Näherungsverfahrens herbeigeführt werden. Dieses setzt voraus, dass der Handlungsreisende auf seiner Tour von Ort zu Ort fährt. Dabei entscheidet er sich immer für die nächstgelegene Stadt.

Das Näherungsverfahren birgt für den Handlungsreisenden ein zweites Problem in sich. Dieses stellt sich aber erst am Ende heraus. Dann werden die Entfernungen der Verbindungen zwischen den einzelnen Städten größer. Hiermit hätte der Handlungsreisende letztlich nichts erreicht.

Welche Unterschiede bestehen zwischen der mathematischen und der praktischen Lösung?

Für die Lösung des Problems des Handlungsreisenden können die beiden folgenden Ansätze verfolgt werden:

• Mathematische Methode
• Praktische Methode

Mathematische Methode

Die Anwendung der mathematischen Methode – diese kann auch optimal an einem Computer durchgeführt werden – fordert, dass ein Modell erstellt wird, bei dem der ungerichtete Graph eine tragende Rolle spielt. Dieses Modell funktioniert dadurch, dass die Knoten – diese stellen die einzelnen Städte dar – durch Kanten – dies sind die Wege, die der Handlungsreisende auf seiner Tour zurücklegen muss – miteinander verbunden werden.

Die Tour des Handlungsreisenden lässt sich durch einen Kreis in dem Graphen darstellen. Ziel des Handlungsreisenden muss es sein, eine Tour zu finden, die für ihn mit einem geringen Zeit- und Kostenaufwand verbunden ist. Voraussetzung für die Anwendung mathematischen Methode ist, dass es zwischen den einzelnen Städten mindestens einen Verbindungsweg gibt.

Praktische Methode

Die praktische Methode ist mit der näherungsweisen Lösung des Problems eines Handlungsreisenden identisch. Ob dieser Ansatz aber wirklich der richtige Weg ist, bleibt fraglich. Die Anwendung der praktischen Methode führt unter Umständen dazu, dass der Handlungsreisende am Ende seiner Tour längere Entfernungen zurücklegen muss. Überdies steigt die Anzahl der Wege, wenn der Handlungsreisende mehrere Städte besuchen muss. Dies führt dazu, dass er bei der schrittweisen Lösung des Problems einen erheblichen Zeitaufwand einkalkulieren muss.

Im Vergleich der beiden Methoden zeigt sich, dass die mathematische Methode nicht immer eine optimale Lösung findet. Sie ist aber leichter praktizierbar und für den Handlungsreisenden mit einem deutlichen Zeitvorteil verbunden.

Abschließendes Beispiel zum Problem des Handlungsreisenden

Übungsfragen