Das Traveling Salesman-Problem


Seminararbeit, 2007

18 Seiten, Note: 2,7

Anonym


Leseprobe

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.

Ende der Leseprobe aus 18 Seiten

Details

Titel
Das Traveling Salesman-Problem
Hochschule
Hochschule Heilbronn Technik Wirtschaft Informatik
Veranstaltung
Proseminar
Note
2,7
Jahr
2007
Seiten
18
Katalognummer
V90770
ISBN (eBook)
9783638054317
ISBN (Buch)
9783640634002
Dateigröße
521 KB
Sprache
Deutsch
Schlagworte
Traveling, Salesman-Problem, Proseminar
Arbeit zitieren
Anonym, 2007, Das Traveling Salesman-Problem, München, GRIN Verlag, https://www.grin.com/document/90770

Kommentare

  • Noch keine Kommentare.
Im eBook lesen
Titel: Das Traveling Salesman-Problem



Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden