Der Hauptbestandteil dieser Arbeit ist das Testen verschiedener lokaler Suchoperatoren
für eine Erweiterung des gutbekannten Vehicle Routing Problems.
Diese erst vor kurzem eingeführte Erweiterung wurde notwendig um ein
Routenplanungsproblem zu lösen, das daraus bestand, Getränke und Tabakwaren
in dichtbesiedelten Groÿstädten in Brasilien auszuliefern. Es wurde
nun versucht herauszunden, welche der VRPTW Operatoren geeignet sind,
um das Vehicle Routing Problem with Time Windows and Multiple Deliverymen
(VRPTWMD) möglichst gut zu lösen. Insgesamt wurden vier Operatoren
implementiert, wobei Relocate und Ejection Chains auf die Routenminimierung
abzielen und Cross bzw. 2-opt entsprechend die gefahrene Distanz
verringern sollten. Um die Operatoren zu testen, wurden die benötigten
Startlösungen mit der von Solomon entwickelten I1 Einfügeheuristik generiert.
Die Erkenntnisse aus den Tests wurden schieÿlich dazu verwendet, eine
best performance Variante zu entwickeln, welche anhand der Solomon Instanzen
R101 bis R112 getestet wurde. Die Ergebnisse der Tests benden
sich am Ende der Arbeit.
The Vehicle Routing Problem with time windows is a well studied problem
in literature. The extension to Vehicle Routing Problem with Time Windows
and Multiple Deliverymen (VRPTWMD) has been proposed to solve a
delivery problem of commodities, like beverages and tobacco in highly populated
areas in Brazil. This rather new problem structure in the VRPTW
context, is the main subject of the work. In this thesis, the aim is to nd
out, which operators used for VRP are most suitable for the VRPTWMS.
Relocate and Ejection Chain operators were tested for truck and deliverymen
reduction, Cross and 2-opt were implemented to reduce distance. The
Solomon I1 insertion heuristic was used to obtain starting solutions, for the
tests and the nal version of the algorithm proposed. To complete this work,
several tests have been performed and the results of the algorithm running
Solomon R101- R112 instances can be found at the end.
Inhaltsverzeichnis
1 Introduction
1.1 Problem description
1.2 Vehicle Routing with Time Windows
1.3 Vehicle Routing with Multiple Deliverymen
1.4 Literature Overview
2 Operators
2.1 Overview
2.2 2-opt
2.2.1 Description
2.2.2 Implementation
2.2.3 Further comments
2.3 Cross
2.3.1 Description
2.3.2 Implementation
2.3.3 Further comments
2.4 Relocate
2.4.1 Description
2.4.2 Implementation
2.5 Ejection Chains
2.5.1 Description
2.5.2 Implementation
2.5.3 Further comments
3 Testing and its environment
3.1 Construction Heuristic
3.2 Test environment
3.3 Tests
3.3.1 Tests on construction parameters
3.3.2 Tests on truck reduction
3.3.3 Tests on deliverymen reduction
3.3.4 Tests on distance reduction
4 Algorithm
4.1 Description
4.2 Test results and comparison
5 Conclusion
Bibliography
Zielsetzung & Themen
Die Arbeit befasst sich mit der Erweiterung des klassischen Vehicle Routing Problems mit Zeitfenstern (VRPTW) um die Komponente der mehreren Zusteller (Multiple Deliverymen), um die Effizienz der Warenbelieferung in dicht besiedelten Gebieten zu steigern. Das primäre Ziel ist die Entwicklung und Erprobung effizienter heuristischer Operatoren, um die Anzahl der benötigten Fahrzeuge sowie die Zustellzeiten zu minimieren.
- Analyse und Anpassung bestehender Routenplanungs-Operatoren (2-opt, Cross, Relocate, Ejection Chains) für die VRPTW-Erweiterung.
- Untersuchung der Auswirkungen von Parametrisierung auf die Qualität der initialen Routenkonstruktion.
- Entwicklung eines Algorithmus zur iterativen Optimierung von Fahrzeug- und Zustellerkapazitäten.
- Empirische Evaluierung des Algorithmus anhand von Standard-Instanzen nach Solomon (R101-R112).
Auszug aus dem Buch
1.1 Problem description
Logistics and Transportation are major growing segments in research as well as in real world applications. Daily activities are not possible without well designed transportation policies. Today´s world requires not only cheap transportation, but also flexibility. Transportation has become an integral part of customer satisfaction, as the environment gets more demanding. Nowadays more and more products can be ordered online, including books, electronics or even groceries. Most of these products are delivered to households or small shops without big storage areas and therefore deliveries become smaller but more frequent. If a company only owns one truck, the problem solution can be found by solving the classical Traveling Salesman Problem (TSP), the root of all routing problems. As this is not the typical case more research has been done since then. What if the deliveries are performed by more than one truck? The routing of these trucks is not a trivial issue. This routing problem with variable trucks is called Vehicle Routing Problem (VRP) and was first mentioned by Dantzig and Ramser [7]. A more recent description can be found in Toth and Vigo [30]. Even though TSP and VRP are just focusing on the geographical dimension, there is a wide area of applications. As the timing of the deliveries has become more and more important, a model adaption was needed. Time slots were included into the problem formulation. With this adaptation much more companies could use computer aided routing for their delivery systems. The distribution problem capable to deal with this setting became widely known as Vehicle Routing Problem with Time Windows (VRPTW).
Zusammenfassung der Kapitel
1 Introduction: Dieses Kapitel führt in die Problematik der Routenplanung ein und erläutert die Erweiterung des klassischen VRP zu komplexeren Modellen wie dem VRPTW und VRPTWMD.
2 Operators: Hier werden verschiedene lokale Suchoperatoren wie 2-opt, Cross, Relocate und Ejection Chains im Detail beschrieben, die zur Optimierung der Routen verwendet werden.
3 Testing and its environment: Dieses Kapitel erläutert die gewählte Konstruktionsheuristik zur Erstellung initialer Lösungen sowie die Testumgebung, einschließlich der verwendeten Datensätze und Parametereinstellungen.
4 Algorithm: Es wird die Implementierung des Algorithmus mittels Python beschrieben, wobei der Fokus auf dem Ablauf der verschiedenen Optimierungsphasen zur Reduktion von Fahrzeugen und Zustellern liegt.
5 Conclusion: Die Arbeit schließt mit einer Zusammenfassung der Ergebnisse und gibt einen Ausblick auf zukünftige Forschungsmöglichkeiten im Bereich der Routenoptimierung.
Schlüsselwörter
Vehicle Routing Problem, VRPTW, Multiple Deliverymen, Routenoptimierung, Heuristiken, Ejection Chains, 2-opt, Relocate, Cross-Operator, Logistik, Transportwesen, Solomon-Instanzen, Kapazitätsoptimierung, Zeitfenster, Algorithmenentwicklung.
Häufig gestellte Fragen
Worum geht es in dieser Masterarbeit grundsätzlich?
Die Arbeit behandelt die Optimierung von Lieferrouten in einem Szenario, in dem Fahrzeuge nicht nur Waren transportieren, sondern zusätzlich von mehreren Zustellern begleitet werden, um die Effizienz der Auslieferung in dicht besiedelten Gebieten zu erhöhen.
Welche zentralen Themenfelder werden bearbeitet?
Die Arbeit konzentriert sich auf die Anpassung und den Test von lokalen Suchoperatoren wie 2-opt, Relocate und Ejection Chains, um Routen hinsichtlich der Anzahl der LKWs, der Zusteller und der gefahrenen Gesamtdistanz zu verbessern.
Was ist das primäre Ziel der Forschungsarbeit?
Das Hauptziel besteht darin, einen effektiven Algorithmus zu entwickeln, der auf Basis von Solomon-Standardinstanzen die Kostenstruktur einer Auslieferung durch die Minimierung der Fahrzeugflotte und Personaleinsatzzeiten optimiert.
Welche wissenschaftliche Methodik wird verwendet?
Die Arbeit nutzt heuristische Optimierungsverfahren (lokale Suche), führt eine detaillierte Literaturübersicht durch und evaluiert die entwickelten Lösungsansätze anhand systematischer Tests mit etablierten Datensätzen.
Was wird im Hauptteil der Arbeit behandelt?
Der Hauptteil befasst sich detailliert mit der theoretischen Beschreibung und Implementierung der Operatoren, gefolgt von einer umfangreichen empirischen Testphase, in der die Parameter des Algorithmus (wie der Alpha-Wert) systematisch variiert werden.
Welche Schlüsselwörter charakterisieren die Arbeit?
Wichtige Schlagworte sind VRPTWMD (Vehicle Routing Problem with Time Windows and Multiple Deliverymen), Ejection Chains, Heuristiken, Solomon-Instanzen und die operative Optimierung von Logistikprozessen.
Warum ist die Erweiterung um "Multiple Deliverymen" wichtig?
In städtischen Gebieten mit hoher Dichte ermöglicht es der Einsatz zusätzlicher Zusteller, die Standzeit des LKWs zu verringern und somit mehr Kunden pro Tag zu bedienen, was mit klassischen VRP-Modellen nicht abgebildet werden kann.
Welche Rolle spielt der "Alpha-Wert" in den Testergebnissen?
Der Alpha-Wert steuert in der Konstruktionsheuristik die Gewichtung bei der Wahl des nächsten Kunden. Die Tests zeigen, dass eine sorgfältige Anpassung dieses Parameters wesentlich zur Qualität der initialen Lösungen beiträgt.
- Citation du texte
- Michael Huemer (Auteur), 2011, Heuristics for the vehicle routing problem with multiple deliverymen, Munich, GRIN Verlag, https://www.grin.com/document/232841
