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
- Zusammenfassung und Fazit
- Literaturverzeichnis
Zielsetzung und Themenschwerpunkte
Diese Seminararbeit befasst sich mit dem Vehicle-Routing Problem (VRP) im Kontext der Lieferplanung von Paketdiensten. Das Ziel ist es, eine Heuristik zu entwickeln, die effiziente Routen für die Zustellung von Paketen generiert und gleichzeitig die Kosten minimiert.
- Adaptive Variable Nachbarschaftssuche (AVNS) als Lösungsansatz
- Definition von Nachbarschaftsstrukturen für die Routenplanung
- Entwicklung eines adaptiven Shaking-Mechanismus zur Verbesserung der Lösungsqualität
- Lokale Suche und Akzeptanzentscheidung in der AVNS
- Bewertung der Performance der entwickelten Heuristik
Zusammenfassung der Kapitel
Das erste Kapitel führt in das Thema Vehicle-Routing Problem ein und definiert die Problematik im Kontext der Lieferplanung von Paketdiensten. Das zweite Kapitel stellt die Adaptive Variable Nachbarschaftssuche (AVNS) als Lösungsansatz vor. Es werden die Initialisierungsphase, die Definition der Nachbarschaftsstrukturen, der adaptive Shaking-Mechanismus und die lokale Suche sowie die Akzeptanzentscheidung beschrieben. Die Arbeit schließt mit einer Zusammenfassung der Ergebnisse und einem Fazit.
Schlüsselwörter
Vehicle-Routing Problem, Lieferplanung, Paketdienste, Adaptive Variable Nachbarschaftssuche (AVNS), Heuristik, Routenplanung, Kostenminimierung, Shaking-Mechanismus, Lokale Suche, Akzeptanzentscheidung.
- Arbeit zitieren
- Felix Warthmann (Autor:in), 2015, Vehicle-Routing Probleme. Eine Heuristik für die Lieferplanung von Paketdiensten, München, GRIN Verlag, https://www.hausarbeiten.de/document/323790
