Paketlieferdienste sehen sich bei der Auslieferung von Paketen zum Endkunden dem Problem einer kostenminimalen Routenplanung gegenübergestellt. Die Auslieferung ist ein Problem der Tourenplanung, dessen Ziel die Bestimmung eines kostenminimalen Routennetzes ist, bei der eine gegebene Anzahl an Kunden mit bekannten Bedarfen bedient wird.
Stenger et al. (2013) beschreiben in ihrer Arbeit eine Erweiterung des Tourenplanungsproblems, das sich besser auf die realen Begebenheiten bei großen Paketdienstleistern bezieht. Dabei werden mehrere Depots betrachtet und darüber hinaus ein wichtiger Trend in der Auslieferung von Paketen einbezogen: Outsourcing von unprofitablen Kunden an Subunternehmen. Sie nennen dieses Problem ein Multi Depot Vehicle Routing Problem with Private fleet and Common carriers (MDVRPPC). Die Bedienung der Kundenbedarfe erfolgt durch die Nutzung eigener Fahrzeug und Fahrzeuge der Subunternehmer, die an entsprechenden Depots stationiert sind. Es gilt somit zu entscheiden, ob ein Kunde an den Subunternehmer abgegeben oder einem eigenen Depot zugeordnet wird. Ferner müssen für die eigenen Depots entsprechende Auslieferungsrouten unter Berücksichtigung der Zeit- und Kapazitätsrestriktionen bestimmt werden. Ziel ist es, eine kostenminimale Zuordnung vorzunehmen.
Diese Arbeit stellt den Anspruch, eine Zusammenfassung des von Stenger et al. (2013) vorgestellten Lösungsalgorithmus für das oben definierte Problem zu geben. Dabei sollen das Prinzip und die Wirkungsweise der Problemlösung durch die Adaptive Variable Nachbarschaftssuche (AVNS) vorgestellt und durch eigene Beispiele verdeutlicht werden. Dazu gliedert sich das zweite Kapitel in die einzelnen Vorgehensschritte des Lösungsalgorithmus. Im dritten Kapitel werden eine Zusammenfassung sowie ein Fazit gegeben.
Inhaltsverzeichnis
1 Einleitung und Problemdefinition
2 Adaptive Variable Nachbarschaftssuche nach Stenger et al. (2013)
2.1 Initialisierungsphase
2.2 Definition der Nachbarschaftsstrukturen
2.3 Adaptives Shaking
2.3.1 Routenauswahl
2.3.2 Kundenauswahl
2.3.3 Adaptiver Mechanismus
2.4 Lokale Suche und Akzeptanzentscheidung
3 Zusammenfassung und Fazit
Zielsetzung & Themen
Die Arbeit hat zum Ziel, den von Stenger et al. (2013) vorgestellten Lösungsalgorithmus für das Multi Depot Vehicle Routing Problem with Private fleet and Common carriers (MDVRPPC) zusammenfassend darzustellen und dessen Prinzipien sowie Wirkungsweise anhand von Beispielen zu erläutern.
- Kostenminimale Tourenplanung für Paketlieferdienste
- Outsourcing-Entscheidungen für unprofitable Kunden
- Adaptive Variable Nachbarschaftssuche (AVNS) als Metaheuristik
- Mechanismen zur Routen- und Kundenauswahl
- Strategien zur Diversifizierung und Intensivierung der Suche
Auszug aus dem Buch
2.3.1 Routenauswahl
Die Routenauswahl widmet sich der Bestimmung der Routen, die Teil des Cyclic-Exchange werden. Die Bestimmung erfolgt in zwei Schritten, wobei zunächst die erste Route ausgewählt wird. Dazu werden die Methoden Zufall, Längste Route und Längste Route pro Bedarfseinheit (Verhältnis Tourenlänge zu Bedarf der Route) angewendet. Die Methoden unterscheiden sich jeweils in den Auswahlwahrscheinlichkeiten der einzelnen Routen. Während bei einer zufälligen Auswahl alle Routen mit derselben Wahrscheinlichkeit gewählt werden, sind die Wahrscheinlichkeiten bei den anderen beiden Methoden proportional zur Routenlänge bzw. zur Routenlänge pro Einheit. Damit wird der Austausch längerer Routen bzw. kostenineffizienter Routen präferiert. Im zweiten Schritt werden die weiteren Routen iterativ bestimmt. Der Austausch zwischen weit entfernten Routen führt selten zu einer Verbesserung der Lösung. Um dem entgegenzuwirken werden weitere Routen nur ausgewählt, wenn sie eine gewisse räumliche Nähe zur vorher ausgewählten Route aufweisen. Dazu wird um jede Route ein Rechteck gespannt, sodass alle Kunden einer Route innerhalb dieses Rechtecks liegen. Schließlich wird der Abstand des Rechtecks der vorher ausgewählten Route zu allen anderen bestimmt. Überschreitet der Abstand ein gewisses Maß nicht, so wird diese Route zur potenziellen Route. Aus allen potenziellen Routen wird eine Route per Zufall ausgewählt. Liegt keine Routen innerhalb dieses Maßes, wird aus allen verfügbaren Routen eine per Zufall bestimmt. Der zweite Schritt wird so oft wiederholt, bis die gewünschte Anzahl an Routen ausgewählt wurde. Als Bezugspunkt der Abstandsmessung gilt immer die zuletzt ausgewählte Route.
Zusammenfassung der Kapitel
1 Einleitung und Problemdefinition: Das Kapitel führt in die Herausforderungen der kostenminimalen Routenplanung bei Paketdiensten ein und definiert das MDVRPPC inklusive der Integration von Subunternehmern.
2 Adaptive Variable Nachbarschaftssuche nach Stenger et al. (2013): Dieser Abschnitt erläutert den AVNS-Algorithmus, bestehend aus Initialisierung, adaptiven Shaking-Verfahren, lokaler Suche und Akzeptanzkriterien.
3 Zusammenfassung und Fazit: Das Fazit resümiert die Effektivität des Algorithmus und unterstreicht die Relevanz des Outsourcings sowie die Übertragbarkeit auf andere Tourenplanungsprobleme.
Schlüsselwörter
Tourenplanung, MDVRPPC, Paketdienste, Adaptive Variable Nachbarschaftssuche, AVNS, Routenplanung, Outsourcing, Subunternehmer, Metaheuristik, Cyclic-Exchange, Kostenminimierung, Lokale Suche, Logistikoptimierung
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit behandelt die mathematische und algorithmische Lösung des Routenplanungsproblems von Paketdiensten, speziell unter der Berücksichtigung von Fremd- und Eigenflotten.
Welches sind die zentralen Themenfelder?
Die zentralen Themen sind das Multi Depot Vehicle Routing Problem, das Outsourcing unprofitabler Kunden und die Anwendung adaptiver Metaheuristiken zur Lösungsoptimierung.
Was ist das primäre Ziel der Untersuchung?
Das Ziel ist die verständliche Zusammenfassung und Erläuterung des AVNS-Algorithmus nach Stenger et al. (2013), um dessen Wirkungsweise bei der Routenoptimierung aufzuzeigen.
Welche wissenschaftliche Methode wird verwendet?
Es wird eine computergestützte Analyse basierend auf der Metaheuristik der Adaptiven Variablen Nachbarschaftssuche (AVNS) sowie hill climbing für die lokale Suche beschrieben.
Was wird im Hauptteil behandelt?
Im Hauptteil werden die einzelnen Phasen des Algorithmus erläutert: die Initialisierung, die Nachbarschaftsstrukturen, das adaptive Shaking (Routen- und Kundenauswahl) sowie die lokale Suche.
Welche Schlüsselwörter charakterisieren die Arbeit?
Die Arbeit wird durch Begriffe wie MDVRPPC, Routenplanung, Metaheuristik und adaptive Optimierung charakterisiert.
Warum spielt die räumliche Nähe bei der Routenauswahl eine Rolle?
Die räumliche Nähe ist entscheidend, da der Austausch zwischen weit entfernten Routen selten zu einer Verbesserung der Gesamtlösung führt, weshalb der Algorithmus räumlich nahe Routen priorisiert.
Wie passt der Algorithmus die Auswahlmethoden an?
Durch ein Scoring-System und ein Roulette-Wheel-Selection-Verfahren werden die Auswahlwahrscheinlichkeiten für erfolgreiche Methoden in nachfolgenden Iterationen erhöht.
- Arbeit zitieren
- Felix Warthmann (Autor:in), 2015, Vehicle-Routing Probleme. Eine Heuristik für die Lieferplanung von Paketdiensten, München, GRIN Verlag, https://www.grin.com/document/323790
