Studiengang

Verkehrsbetriebswirtschaft und Logistik

Proseminar

Sommersemester 2007

Das Traveling Salesman Problem

Inhaltsverzeichnis

1 Einleitung 1

2. Das Traveling Salesman Problem 2

2.1 Definition 2

2.2 Historischer Abriss 3

2.3 Mathematische Formulierung 5

2.3.1 Symmetrisches TSP 5

2.3.2 Asymmetrisches TSP 5

2.3.3 Metrisches TSP 6

3 Lösungsverfahren 6

3.1 Übersicht der Verfahren 6

3.2 Exakte Lösungsverfahren 7

3.2.1 Komplette Enumeration 8

3.2.2 Branch- and-Bound-Verfahren 8

3.3 Heuristiken 10

3.3.1 Paarweise Vertauschung 10

3.3.2 Simulated Annealing 11

4 Das M-Traveling Salesman Problem 12

5 Routenplanung gut & teuer 12

6 Fazit 14

Literaturverzeichnis IV

Bücher: IV

Zeitschriften: V

Internetquel en: V

II

1 Einleitung

Das Traveling Salesman Problem (TSP) gliedert sich ein in die Schwierigkeiten der

Tourenplanung. Dabei steht die Fahrzeugflottenoptimierung an erster Stel e. Es wird

bestimmt, welches Fahrzeug welchen Kunden zu welchem Zeitpunkt bedient. Die

Tourenplanung stel t also die Weichen dafür, dass Kundennachfragen pünktlich und

zu geringen Kosten erfül t werden.1 Als deutlich formuliertes Ziel besteht die Aufgabe

der Tourenplanung darin, den Einsatz des Fuhrparks zu koordinieren. Dies sol

optimal oder so weit wie möglich optimal geschehen. Als Optimierungskriterium zählt

die Anpassung an die reale Problemstel ung, an die verfügbaren Daten und an

mögliche Lösungsverfahren. In den meisten Anwendungsfäl en 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-vol stä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 dargestel ten Grundlagen

des Traveling Salesman Problem, die Erläuterung einiger Lösungsverfahren in

Abschnitt drei, in die Darstel ung des M-Traveling Salesman Problem unter Punkt 4

und unter die in Abschnitt fünf veranschaulichte aktuel e Situation ,,Routenplanung gut

& teuer".

Außerdem wird am Ende im sechsten Punkt eine kurze Zusammenfassung gegeben,

die einen zukunftsorientierten Ausblick und den aktuel en Bezug zum Thema

aufzeigen sol .

Das Ziel dieser Arbeit beinhaltet grundlegend die verständliche Darstel ung des

Problems und das Aufzeigen einiger Lösungsversuche.

1 Vgl. Thonemann (2005), S. 405.

2 Vgl. Neitzel (1977), S. 26.

1

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 sol er wählen (in welcher Reihenfolge sol 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 sol er in Köln wieder ankommen. Abbildung 1 stel t al e möglichen Touren dar

und Abbildung 2 die kosten- und zeitminimierenste Rundreise.

3 Domschke (1997), S. 100.

2