Lade Inhalt...

Vehicle-Routing Probleme. Eine Heuristik für die Lieferplanung von Paketdiensten

Seminararbeit 2015 13 Seiten

BWL - Beschaffung, Produktion, Logistik

Leseprobe

Inhaltsverzeichnis

Abbildungsverzeichnis

Abkürzungsverzeichnis

Symbolverzeichnis

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

Literaturverzeichnis

Abbildungsverzeichnis

Abbildung 1: Beispielhafte Durchführung des Move- und Cyclic-Exchange- Operators

Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

Symbolverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

1 Einleitung und Problemdefinition

Paketlieferdienste sehen sich bei der Auslieferung von Paketen zum Endkunden dem Prob- lem einer kostenminimalen Routenplanung gegenübergestellt. Die Auslieferung ist ein Problem der Tourenplanung, dessen Ziel die Bestimmung eines kostenminimalen Routen- netzes ist, bei der eine gegebene Anzahl an Kunden mit bekannten Bedarfen bedient wird.

Stenger et al. (2013) beschreiben in ihrer Arbeit eine Erweiterung des Tourenplanungs- problems, das sich besser auf die realen Begebenheiten bei großen Paketdienstleistern be- zieht. Dabei werden mehrere Depots betrachtet und darüber hinaus ein wichtiger Trend in der Auslieferung von Paketen einbezogen: Outsourcing von unprofitablen Kunden an Sub- unternehmen. Sie nennen dieses Problem ein Multi Depot Vehicle Routing Problem with Private fleet and Common carriers (MDVRPPC). Die Bedienung der Kundenbedarfe er- folgt durch die Nutzung eigener Fahrzeug und Fahrzeuge der Subunternehmer, die an ent- sprechenden 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 Zu- ordnung 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 Nach- barschaftssuche (AVNS) vorgestellt und durch eigene Beispiele verdeutlicht werden. Dazu gliedert sich das zweite Kapitel in die einzelnen Vorgehensschritte des Lösungsalgorith- mus. Im dritten Kapitel werden eine Zusammenfassung sowie ein Fazit gegeben.

2 Adaptive Variable Nachbarschaftssuche nach Stenger et al. (2013)

Zur Lösung des MDVRPPC verwenden Stenger et al. (2013) eine Erweiterung der Vari- ablen Nachbarschaftssuche (VNS), die eine häufig verwendete Metaheuristik für die Lö- sung kombinatorischer Optimierungsprobleme ist. Das Lösungsverfahren besteht dabei aus einem Shaking-Schritt, der zufällig eine neue Lösung in der aktuellen Nachbarschaft generiert und einer anschließenden lokalen Suche, um von dieser Lösung zu einem lokalen Optimum zu gelangen. VNS zeichnen sich dabei durch eine gute Lösungsqualität bei zu- gleich hoher Lösungsgeschwindigkeit aus. Stenger et al. (2013) implementieren zusätzlich einen adaptiven Mechanismus zur Beeinflussung des Shaking-Steps, um diesen effektiver für das MDVRPPC zu gestalten.

Die Belieferung der Kunden durch Subunternehmer wird im Algorithmus durch das Konzept virtueller Fahrzeuge berücksichtigt. Jedes Depot eines Subunternehmers, im Folgenden Fremddepot, hat dabei exakt ein virtuelles Fahrzeug mit einer Kapazität entsprechend der Depotkapazität zur Verfügung. Eine weitere wichtige Restriktion ist, dass ein Kunde dem Fremddepot nur zugeordnet werden kann, wenn er innerhalb eines bestimmten Radius um das Depot liegt. Der Vorteil des Konzepts virtueller Fahrzeuge ist, dass auch die fremdbelieferten Kunden Teil des Cyclic-Exchange werden können. Der Unterschied zu den normalen Routen liegt lediglich in der Vernachlässigung der Kosten.

Dieses Kapitel soll entsprechend dem Vorgehen des Algorithmus die Abschnitte Initialisierungsphase, Definition der Nachbarschaftsstruktur, adaptives Shaking, lokale Suche und Akzeptanzentscheidung näher erläutern.

2.1 Initialisierungsphase

Ziel der Initialisierungsphase ist es, eine erste Zuordnung der Kunden zu Eigen- und Fremddepots vorzunehmen und anschließend mittels des Savings-Algorithmus Anfangs- routen für eigene Depots zu bestimmen. Für Fremddepots ist letzteres nicht notwendig, da die Kosten für das Outsourcen unabhängig der realisierten Route sind. Die so generierte Lösung darf die Kapazitäts- und Zeitrestriktion verletzen, was über Straf- kosten in der Zielfunktion berücksichtigt wird. Sind die Anfangsrouten bestimmt, wird über eine lokale Suche, wie sie in Abschnitt 2.4 beschrieben ist, eine erste Verbesserung der Startlösung vorgenommen.

2.2 Definition der Nachbarschaftsstrukturen

Ausgehend von der Startlösung untersucht der (A)VNS-Algorithmus immer größere Nach- barschaftsstrukturen auf der Suche nach dem globalen Optimum. Stenger et al. (2013) be- nutzen für die Bestimmung dieser Strukturen die Methode des Cyclic-Exchange, bei dem ein simultaner, zyklischer Tausch von Knoten zwischen Routen erfolgt. Der Vorteil dieser Methode ist, dass sowohl nahe, als auch ferne Nachbarschaften erreicht werden können. Der Bestimmung der Nachbarschaften liegen 3 Parameter zugrunde: Anzahl der Depots, an denen Routen beginnen (Φ), Anzahl der in den Tausch involvierten Routen (Ω) und maximale Länge der zu tauschenden Sequenz (Γmax). Neben den Cyclic-Exchange-Nach- barschaften (mit einem oder mehreren Depots) werden auch Move-Nachbarschaften be- trachtet. Dabei erfolgt eine neue Lösung durch den „Move” (Verschiebung) einer Sequenz von Kunden von einer Route zu einer anderen. Es sind somit zwangsläufig zwei Routen in den Move involviert, eine Route gibt jedoch keine Kunden ab (Γmax=0). Um die Vorge- hensweise bei der Definition von Nachbarschaften zu verdeutlichen wird in der Abbildung 1 für jede der drei Gruppen ein Beispiel gegeben. Die Darstellung soll dabei nur eine Ver- anschaulichung des Prinzips zur Bildung von Lösungen einer Nachbarschaften geben und spiegelt nicht die Komplexität realer Mengen an Kunden und Depots wieder, wie sie in der computergestützten Analyse von Stenger et al. (2013) benutzt werden. Der Austausch des Kunden C von der blauen zur schwarzen Route im Beispiel (1) wurde durch einen Move- Operator erreicht. Sind nur diese beiden Routen, sechs Kunden und das eine Depot gege- ben, so erhält man die anderen Lösungen der Move-Nachbarschaft jeweils durch Aus- tausch eines anderen Kunden (insgesamt 6 Lösungen). Das Beispiel (2) betrachtet den Cyclic-Exchange-Operator an einem Depot. Es wird ersichtlich, dass die Kunden C, I und F zyklisch innerhalb der drei Routen ausgetauscht werden. Dies stellt wieder nur eine Lö- sung der entstehenden Cyclic-Exchange-Nachbarschaft dar. Im Beispiel (3) wird nochmal ein Cyclic-Exchange dargestellt, dieses Mal mit zwei Depots und einer Sequenz von je- weils zwei Kunden, die getauscht werden. Auch hier wird nur eine Lösung der Nachbar- schaft veranschaulicht.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Beispielhafte Durchführung des Move- und Cyclic-Exchange-Operators

2.3 Adaptives Shaking

Die Lösungsprozedur des Algorithmus setzt sich aus einem Shaking-Schritt und einer lo- kalen Suche zusammen. Das Shaking ermöglicht eine Verschiebung des Suchintervalls, sodass in einem neuen Bereich der Zielfunktion nach dem Optima gesucht werden kann. Im Gegensatz zum Standard VNS erfolgt beim AVNS keine zufällige Auswahl der Ele- mente, die eine neue benachbarte Lösung ergeben. Ein adaptiver Mechanismus beeinflusst die Methode zur Routen- und Kundenauswahl. In diesem Abschnitt sollen zunächst die Methoden zur Auswahl der Routen und Depots vorgestellt und anschließend der adaptive Mechanismus beschrieben werden.

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 Wahrscheinlich- keit gewählt werden, sind die Wahrscheinlichkeiten bei den anderen beiden Methoden pro- portional 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 Rou- ten 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 ge- wisses Maß nicht, so wird diese Route zur potenziellen Route. Aus allen potenziellen Rou- ten 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.

2.3.2 Kundenauswahl

Nach der Bestimmung der Routen erfolgt die Auswahl der Kunden, die auf der entspre- chenden Route ausgetauscht werden sollen. Die Auswahl erfolgt in zwei Schritten. Im ers- ten Schritt muss die Anzahl an Kunden einer Route festgelegt werden, die als Sequenz getauscht werden. Der zweite Schritt unterscheidet sich bei Routen, die durch ein eigenes Fahrzeug bedient werden und den an Subunternehmen abgegebenen Routen. Bei eigenen Routen muss der Startkunde des Tausches ausgewählt werden, während bei Fremdbedien- ten nur eine Auswahl der Kunden erfolgen muss, die aus der Fremdroute entfernt werden.

[...]

Details

Seiten
13
Jahr
2015
ISBN (eBook)
9783668229655
ISBN (Buch)
9783668229662
Dateigröße
998 KB
Sprache
Deutsch
Katalognummer
v323790
Institution / Hochschule
Technische Universität Dresden – Institut für Wirtschaft und Verkehr
Note
1,0
Schlagworte
vehicle-routing probleme eine heuristik lieferplanung paketdiensten

Autor

Zurück

Titel: Vehicle-Routing Probleme. Eine Heuristik für die Lieferplanung von Paketdiensten