Im Kern dieser Arbeit geht es darum, darzustellen, durch welche Eigenschaften sich SVRPs von deterministischen Tourenplanungsproblemen unterscheiden. Zu diesem Zweck wird in Kapitel 3 ein Überblick über die verschiedenen SVRPs gegeben. Um die Besonderheiten der SVRPs herausarbeiten zu können, muss aber zunächst das Grundproblem, das allen Tourenplanungsproblemen gemeinsam ist, erklärt werden. Dieses Grundproblem wird in Kapitel 2 erläutert. Anschließend wird ebenfalls in Kapitel 2 ein Überblick über deterministische Tourenplanungsprobleme gegeben. Ferner wird eine Klassifizierung der verschiedenen Lösungsansätze für Tourenplanungsprobleme in diesem Kapitel vorgestellt. Zum Schluss wird in Kapitel 4 auf ein Verfahren exemplarisch etwas detaillierter eingegangen. Aufgrund der erwähnten Komplexität des Themas kann in dieser Arbeit kein allumfassender Überblick über sämtliche Besonderheiten der SVRPs gegeben werden. Hingegen geht es darum, bestimmte Ausschnitte des Themas auf exemplarischer Ebene genauer zu analysieren.
Inhaltsverzeichnis
1 Einleitung
1.1 Gegenstand und Aufbau dieser Arbeit
2 Überblick über deterministische Tourenplanungsprobleme
2.1 Ein bestimmtes Standardproblem der Tourenplanung
2.2 Exakte Verfahren und Heuristiken
3 Stochastische Tourenplanungsprobleme und ihre
3.1 Besonderheiten
3.1 Besonderheiten von Tourenplanungsproblemen mit stochastischer Nachfrage
3.1.1 Besonderheiten von Tourenplanungsproblemen mit stochastischer Nachfrage am Beispiel des Savingsverfahrens
3.1.2 Das Savingsverfahren von Clark und Wright
3.1.3 Der stochastische Clark und Wright Algorithmus
4 Fazit
Zielsetzung & Themen
Die Arbeit untersucht die grundlegenden Unterschiede zwischen deterministischen Tourenplanungsproblemen und stochastischen Tourenplanungsproblemen (SVRP). Das primäre Ziel ist es, die Komplexität stochastischer Nachfrage zu verdeutlichen und aufzuzeigen, wie modifizierte Lösungsansätze, wie der stochastische Clark und Wright Algorithmus, die erwarteten Kosten unter Berücksichtigung von Tourverletzungen minimieren können.
- Charakterisierung von SVRP im Vergleich zu deterministischen Modellen
- Einfluss stochastischer Parameter auf die Tourenplanung
- Methoden der stochastischen Programmierung (Chance Constrained Programming)
- Analyse von Tourverletzungen und deren monetäre Folgen
- Modifizierung klassischer Heuristiken für stochastische Problemstellungen
Auszug aus dem Buch
3.1.3 Der stochastische Clark und Wright Algorithmus
Die Idee, die Summe der Ersparnisse zu maximieren, wird für den stochastischen Fall wie folgt verallgemeinert:
sij = [ Die erwarteten Kosten der Route mit dem Kunden i ]
+ [ Die erwarteten Kosten der Route mit dem Kunden j ]
- [ Die erwarteten Kosten der kombinierten Route, bei der Kunde i unmittelbar nach Kunde j beliefert wird. ]
Wie die erwarteten Kosten einer Route berechnet werden, wird im Folgenden an einem Beispiel erläutert, weil damit eine weitere Besonderheit von VRPSD gezeigt werden kann.
Es wird angenommen, dass eine Route aus fünf Kunden besteht. Das Depot hat den Standort (0,0) und die Kunden haben ihre Standorte an folgenden Punkten: Kunde 1 = (5,0), Kunde 2 = (5,5), Kunde 3 = (0,5), Kunde 4 = (-5,5), Kunde 5 = (-5,0). Es gibt einen direkten Weg zwischen den einzelnen Kunden untereinander und zwischen dem Depot und den Kunden. Die insgesamt zurückgelegte Strecke soll den insgesamt angefallenen Kosten entsprechen. Das Fahrzeug startet am Depot und fährt die Kunden 1-5, wie in Abbildung 1 gezeigt, der Reihe nach an. Diese Route wird als CR bezeichnet.
Im Hinblick auf die erwartete Nachfrage der einzelnen Kunden wird angenommen, dass die Kunden 1, 2, 3 und 4 jeweils einen Anteil von 0,15 Q benötigen. Bei Kunde 5 wird erwartet, dass er einen Anteil von 0,4 Q benötigt.
Zusammenfassung der Kapitel
1 Einleitung: Einführung in die Komplexität stochastischer Tourenplanung und Zielsetzung der Arbeit.
2 Überblick über deterministische Tourenplanungsprobleme: Erläuterung des Standardproblems und der grundlegenden Lösungsverfahren (exakt vs. heuristisch).
3 Stochastische Tourenplanungsprobleme und ihre: Abgrenzung stochastischer Probleme durch den Einsatz von Zufallsvariablen.
3.1 Besonderheiten: Detaillierte Untersuchung von SVRPs unter Einbeziehung von Traveling Salesman Problemen.
3.1 Besonderheiten von Tourenplanungsproblemen mit stochastischer Nachfrage: Analyse von Modellen wie der Chance Constrained Programmierung und Einführung von Strafkosten.
3.1.1 Besonderheiten von Tourenplanungsproblemen mit stochastischer Nachfrage am Beispiel des Savingsverfahrens: Überleitung zum modifizierten Savingsverfahren.
3.1.2 Das Savingsverfahren von Clark und Wright: Darstellung des klassischen, deterministischen Savings-Ansatzes.
3.1.3 Der stochastische Clark und Wright Algorithmus: Anwendung des modifizierten Verfahrens auf stochastische Nachfragedaten.
4 Fazit: Zusammenfassende Bewertung der Relevanz von Tourverletzungen und Ausblick auf zukünftigen Forschungsbedarf.
Schlüsselwörter
Tourenplanung, Stochastik, Fahrzeugkapazität, SVRP, VRPSD, Savingsverfahren, Clark und Wright, Tourverletzung, Zufallsvariable, Kostenminimierung, Logistik, Routenplanung, Erwartungswert, Heuristik, stochastische Programmierung
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit behandelt die Besonderheiten von stochastischen Tourenplanungsproblemen (SVRP), bei denen im Gegensatz zur deterministischen Planung mit stochastischen Daten wie der Kundennachfrage gearbeitet wird.
Was sind die zentralen Themenfelder?
Die Arbeit fokussiert sich auf die mathematische Modellierung von Unsicherheiten in der Logistik, die Berechnung erwarteter Kosten bei Tourverletzungen und die Anpassung klassischer Heuristiken.
Was ist das primäre Ziel oder die Forschungsfrage?
Das Ziel ist aufzuzeigen, wie stochastische Tourenplanungsprobleme charakterisiert sind und wie moderne Algorithmen die erwarteten täglichen Kosten unter Berücksichtigung von Kapazitätsüberschreitungen optimieren können.
Welche wissenschaftliche Methode wird verwendet?
Es werden Ansätze der stochastischen Programmierung (z.B. Chance Constrained Programming) sowie eine modifizierte Version des Savingsverfahrens nach Clark und Wright analysiert.
Was wird im Hauptteil behandelt?
Der Hauptteil erörtert zunächst deterministische Grundlagen, führt dann in die stochastische Problematik ein und stellt schließlich mathematische Strafmodelle sowie den stochastischen Clark und Wright Algorithmus vor.
Welche Schlüsselwörter charakterisieren die Arbeit?
Wichtige Begriffe sind insbesondere Stochastische Tourenplanung (SVRP), Tourverletzung, Savingsverfahren, Fahrzeugkapazität und stochastische Nachfrage.
Warum spielt die Fahrtrichtung bei stochastischen Touren eine Rolle?
Da Tourverletzungen Kosten verursachen können, beeinflusst die Reihenfolge der Kunden bei einer symmetrischen Kostenmatrix das Risiko und die Höhe der erwarteten Kosten, weshalb beide Richtungen geprüft werden müssen.
Was ist eine Tourverletzung?
Eine Tourverletzung tritt auf, wenn die tatsächliche Nachfrage der Kunden die Kapazität des eingesetzten Fahrzeugs übersteigt, was Korrekturmaßnahmen oder monetäre Strafen zur Folge hat.
Kann eine hohe Tourverletzungswahrscheinlichkeit dennoch eine gute Lösung sein?
Ja, sofern die Verletzung bei einem Kunden auftritt, der sehr nah am Depot liegt, da in diesem Fall die resultierenden Kosten der Tourverletzung vergleichsweise gering ausfallen.
- Quote paper
- Patrick Schellhorn (Author), 2006, Besonderheiten stochastischer Tourenplanungsprobleme, Munich, GRIN Verlag, https://www.grin.com/document/65764
