Das Traveling Salesman-Problem

Inhaltsverzeichnis

1 Einleitung

2. Das Traveling Salesman Problem
2.1 Definition
2.2 Historischer Abriss
2.3 Mathematische Formulierung
2.3.1 Symmetrisches TSP
2.3.2 Asymmetrisches TSP
2.3.3 Metrisches TSP

3 Lösungsverfahren
3.1 Übersicht der Verfahren
3.2 Exakte Lösungsverfahren
3.2.1 Komplette Enumeration
3.2.2 Branch- and-Bound-Verfahren
3.3 Heuristiken
3.3.1 Paarweise Vertauschung
3.3.2 Simulated Annealing

4 Das M-Traveling Salesman Problem

5 Routenplanung gut & teuer

6 Fazit

Literaturverzeichnis

Bücher

Zeitschriften

Internetquellen

1 Einleitung

Das Traveling Salesman Problem (TSP) gliedert sich ein in die Schwierigkeiten der Tourenplanung. Dabei steht die Fahrzeugflottenoptimierung an erster Stelle. Es wird bestimmt, welches Fahrzeug welchen Kunden zu welchem Zeitpunkt bedient. Die Tourenplanung stellt also die Weichen dafür, dass Kundennachfragen pünktlich und zu geringen Kosten erfüllt werden.^[1] Als deutlich formuliertes Ziel besteht die Aufgabe der Tourenplanung darin, den Einsatz des Fuhrparks zu koordinieren. Dies soll optimal oder so weit wie möglich optimal geschehen. Als Optimierungskriterium zählt die Anpassung an die reale Problemstellung, an die verfügbaren Daten und an mögliche Lösungsverfahren. In den meisten Anwendungsfällen handelt es sich um das Leiten von Fahrzeugen. Bei dem TSP berücksichtigt man nur ein einzelnes Fahrzeug. Es ist ein kombinatorisches Optimierungsproblem, auch als Reihenfolgeproblem bezeichnet, welches das Ziel hat, die bestmöglichste Abfolge einer Rundreise zu bestimmen. Bei der Ermittlung der optimalen Reihenfolge ist zum Beispiel auf Kriterien wie die geringsten Kosten, die kürzeste Durchlaufzeit, und eine gleichmäßige Auslastung der Betriebsmittel zu achten. Weiterhin gehört das TSP zu einer Klasse von sehr schwierigen Problemen, den sogenannten NP-vollständigen Problemen. Dafür ist kein effizienter Algorithmus vorhanden. Die kombinatorische Optimierung tritt des Weiteren mitunter auch bei der Fertigungsablaufplanung und der Maschinenbelegungsplanung auf.^[2]

Der Aufbau der Arbeit unterteilt sich in die unter Punkt zwei dargestellten Grundlagen des Traveling Salesman Problem, die Erläuterung einiger Lösungsverfahren in Abschnitt drei, in die Darstellung des M-Traveling Salesman Problem unter Punkt 4 und unter die in Abschnitt fünf veranschaulichte aktuelle Situation „Routenplanung gut & teuer“.

Außerdem wird am Ende im sechsten Punkt eine kurze Zusammenfassung gegeben, die einen zukunftsorientierten Ausblick und den aktuellen Bezug zum Thema aufzeigen soll.

Das Ziel dieser Arbeit beinhaltet grundlegend die verständliche Darstellung des Problems und das Aufzeigen einiger Lösungsversuche.

Da das Traveling Salesman Problem eine sehr vielseitige Thematik ist, welche von einigen unterschiedlichen Sichtweisen betrachten werden kann, besteht in dieser Arbeit nur die Möglichkeit, einen kurzen Einblick zu gewähren.

2. Das Traveling Salesman Problem

2.1 Definition

Ein Traveling Salesman Probelm, auch als Rundreiseproblem oder Handlungsreisendenproblem bezeichnet, der Praxis könnte wie folgt lauten:

„Ein Handlungsreisender möchte eine Anzahl von Kunden in verschiedenen Orten besuchen. Nach Abschluss der Besuche möchte er in seinen Ausgangsort zurückkehren. Welchen Weg soll er wählen (in welcher Reihenfolge soll er die Kunden besuchen), damit die dabei insgesamt zurückzulegende Entfernung so gering wie möglich ist?“^[3]

Dabei müssen neben der geringst möglichen Entfernung weiterhin die minimal aufzuwendenden Transportkosten und Transportzeiten beachtet werden. Im weiteren Verlauf sind zwei Abbildungen zu sehen. Ein Handlungsreisender, welcher in Köln startet, möchte die Städte Dortmund, Düsseldorf, Essen und Frankfurt bereisen. Am Ende soll er in Köln wieder ankommen. Abbildung 1 stellt alle möglichen Touren dar und Abbildung 2 die kosten- und zeitminimierenste Rundreise.

[...]

^[1] Vgl. Thonemann (2005), S. 405.

^[2] Vgl. Neitzel (1977), S. 26.

^[3] Domschke (1997), S. 100.