Diese Seminararbeit beschäftigt sich mit der Fahrzeugroutenplanung mit Zeitfenstern, welche ein kombinatorisches Optimierungsproblem darstellt. Wissenschaftler beschäftigen sich bereits seit den 70er Jahren mit dieser Thematik. Die Relevanz war allerdings noch nie zuvor so hoch wie jetzt, denn durch die immer weitere Verbreitung der Nutzung von E-Commerce sind Logistikunternehmen gefragt wie nie zuvor.
Diese Arbeit beschäftigt sich zum einen mit der Definition von Tourenplanungen mit Zeitfenstern und zum anderen mit Lösungsansätzen für diese Problematik.
Inhaltsverzeichnis
1. Kurzzusammenfassung
2. Einleitung
2.1 Heutige Relevanz der Thematik
2.2 Anwendungsbereiche
2.3 Literaturübersicht
2.4 Aufbau der Seminararbeit
3. Problemformulierung
3.1 Variablen und Strukturierung von Raum und Zeit
3.2 Mathematische Modellierung
4. Methoden zum Lösen des Problems
4.1 Allgemeine Verfahrensweise
4.2 Tourenplanung mit Zeitfenstern
4.2.1 Der Sweep-Algorithmus
4.2.2 Der Savings-Algorithmus
4.3 Optimierung mit lokalen Suchverfahren
4.3.1 Das Suchverfahren 2-opt
4.3.2 Das Suchverfahren 3-opt
5. Schlussfolgerung
Zielsetzung & Themen
Die Arbeit untersucht das kombinatorische Optimierungsproblem der Fahrzeugroutenplanung mit Zeitfenstern, das durch die wachsende Bedeutung des E-Commerce an hoher Relevanz gewonnen hat. Ziel ist es, die mathematischen Grundlagen zu definieren und verschiedene algorithmische Lösungsansätze, insbesondere Eröffnungsheuristiken und lokale Suchverfahren, zu analysieren.
- Relevanz der Logistik im Zeitalter des E-Commerce
- Mathematische Modellierung von Tourenplanungsproblemen
- Eröffnungsverfahren (Sweep- und Savings-Algorithmus)
- Verbesserungsverfahren mittels lokaler Suche (2-opt und 3-opt)
- Restriktionen durch Kundenzeitfenster und Kapazitäten
Auszug aus dem Buch
4.2.1 Der Sweep-Algorithmus
Der Sweep-Algorithmus wurde 1974 von Gillett und Miller veröffentlicht und gilt als sequentielles Eröffnungsverfahren, wobei zuerst die Bildung der Touren erfolgt und dann die Wahl der Reihenfolge festgelegt wird – wie wir bereits in Abschnitt 4.1 gelernt haben, nennt man dies "Cluster first, route second".
Grundlagen für die Anwendung des Algorithmus sind das Vorliegen der Knoten in Form von Polarkoordinaten oder kartesischen Koordinaten sowie ein Depot im Koordinatenursprung. Man beginnt mit dem Sortieren der Knoten nach aufsteigenden Polarwinkeln gegen den Uhrzeigersinn und nummeriert diese anschließend von 1 bis n durch. Dann startet die Tourenbildung: die erste Tour besteht aus den Kunden 1,2…,i1. Dies sind die Knoten mit den kleinsten Polarwinkeln. Man fügt solange einen weiteren Kunden in die Tour hinzu bis die Kapazität Q des Lieferfahrzeugs erreicht ist. Wenn diese erreicht ist, beginnt man mit der Bildung einer weiteren Tour. Damit fährt man fort bis alle Kunden einer Tour zugeordnet sind. Diese Vorgehensweise gilt für den Standardfall. In der Tourenplanung mit Zeitfenstern wird der Sweep-Algorithmus einfach um die Restriktion der Zeit erweitert, wie es Vahrenkamp und Mattenfeld (2007) erklären. Hierbei werden die Kunden in einem Sektor gesammelt, dessen Winkel von der Größe der Ladungskapazität des Fahrzeugs abhängig ist. Hierbei werde die konvexe Hülle zunächst nicht berücksichtigt.
Kunden, die einem Sektor aufgrund ihrer Zeitrestriktionen nicht zugeteilt werden können, müssen vorerst zurückgestellt werden und in einem neuen Planungslauf erneut mit dem Sweep-Verfahren einer Tour zugeordnet werden. Als letzter Schritt wird innerhalb jeder Tour die optimierte Reihenfolge mithilfe des Travelling Salesman Problems festgelegt. Um das Grundprinzip des Sweep-Verfahrens zu verdeutlichen, folgt ein Beispiel.
Zusammenfassung der Kapitel
1. Kurzzusammenfassung: Bietet einen kurzen Überblick über die Bedeutung der Fahrzeugroutenplanung mit Zeitfenstern und die Zielsetzung der Arbeit.
2. Einleitung: Beleuchtet die wachsende Relevanz der Logistikbranche durch E-Commerce und erläutert die praktische Bedeutung von Zeitfenstern für Unternehmen.
3. Problemformulierung: Detailliert die mathematische Modellierung des Routenproblems, inklusive der Definition von Variablen und Nebenbedingungen.
4. Methoden zum Lösen des Problems: Stellt verschiedene Lösungsansätze vor, unterteilt in Konstruktions- und Verbesserungsverfahren, und erklärt spezifische Algorithmen wie Sweep, Savings, 2-opt und 3-opt.
5. Schlussfolgerung: Bewertet die Bedeutung wissenschaftlicher Algorithmen für die betriebliche Praxis und die Komplexitätsbewältigung in der Logistik.
Schlüsselwörter
Fahrzeugroutenplanung, Zeitfenster, E-Commerce, Logistik, Optimierung, Heuristik, Sweep-Algorithmus, Savings-Algorithmus, Tourenplanung, Transportlogistik, 2-opt, 3-opt, Kapazitätsrestriktion, Operations Research, Tourenoptimierung.
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit beschäftigt sich mit der mathematischen und algorithmischen Lösung von Fahrzeugroutenplanungsproblemen, bei denen Kunden innerhalb vorgegebener Zeitfenster beliefert werden müssen.
Was sind die zentralen Themenfelder der Publikation?
Die zentralen Felder sind die Modellierung von Tourenplanung, die Anwendung von Eröffnungsheuristiken sowie der Einsatz lokaler Suchverfahren zur Optimierung bestehender Tourenpläne.
Welches primäre Ziel verfolgt die Arbeit?
Ziel ist es, die theoretischen Lösungsansätze für das "Vehicle Routing Problem with Time Windows" (VRPTW) verständlich zu machen und die Funktionsweise gängiger Algorithmen zu demonstrieren.
Welche wissenschaftlichen Methoden werden verwendet?
Es werden mathematische Modellierungen, die Zerlegung in Teilprobleme (Cluster-first, Route-second) sowie konstruktive und iterative (lokale) Suchheuristiken vorgestellt.
Was wird im Hauptteil behandelt?
Der Hauptteil gliedert sich in die formale Problembeschreibung, die mathematische Formulierung sowie die detaillierte Vorstellung der Algorithmen Sweep, Savings, 2-opt und 3-opt.
Welche Schlüsselwörter charakterisieren die Arbeit?
Die Arbeit lässt sich primär über Begriffe wie Tourenplanung, Zeitfenster, Logistik-Optimierung und heuristische Algorithmen charakterisieren.
Was unterscheidet das Tourenproblem mit Zeitfenstern vom klassischen Routing-Problem?
Der entscheidende Unterschied liegt in der zusätzlichen Restriktion, dass die Belieferung nicht nur kapazitätsorientiert, sondern innerhalb spezifischer Zeitintervalle erfolgen muss.
Warum wird der Sweep-Algorithmus als "Cluster-first, route-second" bezeichnet?
Weil das Verfahren zunächst die Kunden basierend auf ihrer geografischen Lage in Sektoren (Cluster) unterteilt und erst anschließend für jeden Sektor die optimale Reihenfolge der Anfahrpunkte festlegt.
Welche Rolle spielen 2-opt und 3-opt bei der Routenoptimierung?
Diese lokalen Suchverfahren fungieren als Verbesserungsalgorithmen, die bestehende Routen durch das Entfernen und neue Verknüpfen von Kanten optimieren, um die Gesamtdistanz zu verkürzen.
- Quote paper
- Christin Kemper (Author), 2015, Vehicle Routing Problem with Time Windows. Route Construction and Local Search Algorithms, Munich, GRIN Verlag, https://www.grin.com/document/335073
