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. 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.
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.
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
Zielsetzung & Themen
Die vorliegende Arbeit verfolgt das Ziel, das „Traveling Salesman Problem“ (TSP) verständlich darzustellen und verschiedene Lösungsansätze für dieses kombinatorische Optimierungsproblem aufzuzeigen, um eine effiziente Routenplanung zu ermöglichen.
- Grundlagen und historische Entwicklung des Traveling Salesman Problems
- Mathematische Modellierung (symmetrisches, asymmetrisches und metrisches TSP)
- Gegenüberstellung exakter Lösungsverfahren und heuristischer Näherungsverfahren
- Erweiterung auf das M-Traveling Salesman Problem
- Praktische Relevanz und Herausforderungen moderner Tourenplanungssoftware
Auszug aus dem Buch
3.2.1 Komplette Enumeration
Bei der kompletten Enumeration prüft man jede der möglichen Strecken und ihre Dauer auf die Optimalität. Ein wesentliches Problem dieses Lösungsverfahren ist die systematische Abarbeitung der Lösungskandidaten. Es gibt (n − 1)! mögliche Lösungen, da der Start- und der Zielort identisch sein müssen. Sind alle Distanzen unabhängig von der Richtung, so gilt (n − 1)! / 2. Wobei auch diese Variante die Lösung nicht vereinfacht. Die Lösungen werden alle ermittelt und am Ende das Ergebnis mit der kleinsten Elementsumme ausgewählt. Dieses Verfahren ist sehr rechenaufwendig. Bei manueller Lösung ist der Rechenaufwand bei n = 6, das heißt 5! = 120 mögliche Lösungen, vertretbar. Jedoch stößt schon ein Computer bei der Berechnung von n = 15, das heißt 14!= 87178291200 mögliche Lösungen, an seine Grenzen.
Die Vorgehensweise bei der kompletten Enumeration geschieht auf folgende Weise. Es muss eine Matrix, i und j gegeben sein. Daraus werden die unerwünschten Verknüpfungen „i - j “, in dem man zugehörige Matrixelemente unendlich setzt, ausgeschlossen. Dies geschieht durch Subtrahieren des kleinsten Elementes einer Zeile von jedem Element dieser Zeile und durch Ersetzen der einzelnen Elemente durch die sich jeweils ergebende Differenz.
Dadurch entsteht auf jeder Zeile mindestens ein Nullelement. Reduktionskonstante kr heißt die Summe aller beim Reduktionsvorgang subtrahierten Elemente. Nun wird die komplette Enumeration, das systematische Ermitteln aller möglichen Reihenfolgen, vorgenommen.
Zusammenfassung der Kapitel
1 Einleitung: Diese Einleitung führt in die Problematik der Tourenplanung ein und definiert das Traveling Salesman Problem als kombinatorisches Optimierungsproblem.
2. Das Traveling Salesman Problem: Dieses Kapitel definiert das Problem, beleuchtet seine historische Entwicklung und führt die mathematische Klassifizierung in symmetrische, asymmetrische und metrische TSP ein.
3 Lösungsverfahren: Hier werden verschiedene Ansätze zur Lösung des TSP vorgestellt, wobei zwischen exakten Algorithmen wie Branch-and-Bound und Heuristiken wie Simulated Annealing unterschieden wird.
4 Das M-Traveling Salesman Problem: Dieser Abschnitt erweitert das klassische TSP auf den Einsatz mehrerer Fahrzeuge, die alle von einem gemeinsamen Depot starten.
5 Routenplanung gut & teuer: Dieses Kapitel thematisiert die praktische Anwendung von Tourenplanungssoftware, deren wirtschaftliche Vorteile sowie die Herausforderungen bei der Implementierung in Unternehmen.
6 Fazit: Das Fazit fasst die Lösungsansätze zusammen und weist auf die wachsende Bedeutung der Tourenoptimierung aufgrund zunehmender globaler Warenströme hin.
Schlüsselwörter
Traveling Salesman Problem, TSP, Tourenplanung, Fahrzeugflottenoptimierung, Kombinatorische Optimierung, NP-vollständige Probleme, Exakte Lösungsverfahren, Heuristiken, Branch-and-Bound, Simulated Annealing, M-Traveling Salesman Problem, Routenplanung, Logistik, Transportaufkommen, Transportkosten
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit beschäftigt sich mit dem Traveling Salesman Problem, einem klassischen kombinatorischen Optimierungsproblem, das darauf abzielt, die effizienteste Rundreise zur Bedienung verschiedener Kundenstandorte zu finden.
Was sind die zentralen Themenfelder?
Zentrale Themen sind die mathematische Definition des Problems, der historische Kontext, die Vorstellung verschiedener exakter und heuristischer Lösungsalgorithmen sowie die praktische Anwendung in der modernen Logistik.
Was ist das primäre Ziel der Untersuchung?
Das Ziel ist eine verständliche Darstellung des TSP und der verschiedenen Methoden, um die bestmögliche Reihenfolge einer Rundreise zu bestimmen.
Welche wissenschaftliche Methode wird verwendet?
Es handelt sich um eine theoretische Arbeit, die auf einer Literaturanalyse verschiedener mathematischer und logistischer Operations-Research-Verfahren basiert.
Was wird im Hauptteil behandelt?
Der Hauptteil gliedert sich in die mathematische Formulierung (symmetrisch, asymmetrisch, metrisch), die Analyse von Lösungsverfahren (Komplette Enumeration, Branch-and-Bound, Heuristiken) sowie die Erweiterung auf M-Fahrzeuge und die IT-gestützte Praxis.
Welche Schlüsselwörter charakterisieren die Arbeit?
Die wichtigsten Begriffe sind Traveling Salesman Problem, Tourenplanung, kombinatorische Optimierung, Lösungsverfahren, Heuristiken und Logistik.
Was unterscheidet das symmetrische vom asymmetrischen TSP?
Beim symmetrischen TSP sind die Kosten bzw. Entfernungen in beide Richtungen zwischen zwei Orten identisch, während sie beim asymmetrischen TSP unterschiedlich sein können, beispielsweise bedingt durch Einbahnstraßen.
Warum ist das Branch-and-Bound-Verfahren relevant?
Es handelt sich um ein exaktes Verfahren, das ein Problem in Teilprobleme zerlegt (Verzweigung) und mittels Schranken (Bounding) gezielt Bereiche des Suchbaums ausschließt, um die optimale Lösung effizienter zu finden.
Wie funktioniert das Simulated Annealing Prinzip?
Das Verfahren ahmt den Abkühlungsprozess von Metall nach, indem es ausgehend von einer zufälligen Rundreise schrittweise nach Verbesserungen sucht und dabei auch kurzzeitige Verschlechterungen in Kauf nimmt, um lokale Optima zu überwinden.
- Quote paper
- Anonym (Author), 2007, Das Traveling Salesman-Problem, Munich, GRIN Verlag, https://www.grin.com/document/90770
