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
- Introduction
- Problem description
- Vehicle Routing with Time Windows
- Vehicle Routing with Multiple Deliverymen
- Literature Overview
- Operators
- Overview
- 2-opt
- Description
- Implementation
- Further comments
- Cross
- Description
- Implementation
- Further comments
- Relocate
- Description
- Implementation
- Ejection Chains
- Description
- Implementation
- Further comments
- Testing and its environment
- Construction Heuristic
- Test environment
- Tests
- Tests on construction parameters
- Tests on truck reduction
- Tests on deliverymen reduction
- Tests on distance reduction
- Algorithm
- Description
- Test results and comparison
Zielsetzung und Themenschwerpunkte
Diese Masterarbeit untersucht die Eignung verschiedener lokaler Such-Operatoren für eine Erweiterung des Vehicle Routing Problems. Der Fokus liegt dabei auf dem Vehicle Routing Problem with Time Windows and Multiple Deliverymen (VRPTWMD), einer neuen Problemstruktur, die sich im Kontext der Routenplanung für die Auslieferung von Gütern wie Getränken und Tabakwaren in dicht besiedelten städtischen Gebieten in Brasilien ergibt. Das Ziel der Arbeit ist es herauszufinden, welche Operatoren aus dem VRPTW-Bereich am besten geeignet sind, um VRPTWMD-Probleme effektiv zu lösen.
- Analyse verschiedener lokaler Such-Operatoren für das VRPTWMD
- Bewertung der Effizienz von Operatoren zur Routenminimierung und zur Reduzierung der Fahrstrecke
- Entwicklung einer optimalen Variante des Algorithmus basierend auf den Testergebnissen
- Anwendung und Evaluierung des Algorithmus auf realen Daten des Solomon R101-R112 Datensatzes
Zusammenfassung der Kapitel
Die Arbeit beginnt mit einer Einführung in das Vehicle Routing Problem (VRP), das Vehicle Routing Problem with Time Windows (VRPTW) und die neuere Erweiterung VRPTWMD. Es werden wichtige Forschungsarbeiten in diesem Bereich zusammengefasst. Kapitel 2 beschreibt vier verschiedene lokale Such-Operatoren: 2-opt, Cross, Relocate und Ejection Chains. Es werden die Funktionsweise und die Implementierung jedes Operators detailliert erklärt. In Kapitel 3 werden die verwendeten Testmethoden und die Testumgebung vorgestellt, einschließlich der Konstruktion einer Heuristik für die Generierung von Startlösungen. Die verschiedenen Tests, die durchgeführt wurden, um die Eignung der Operatoren zu bewerten, werden ebenfalls in diesem Kapitel diskutiert. Dies beinhaltet Tests zur Reduktion von Fahrzeugen und Zustellern sowie Tests zur Minimierung der Gesamtfahrstrecke. Die Erkenntnisse aus diesen Tests werden dann in Kapitel 4 verwendet, um einen effizienten Algorithmus zu entwickeln, der anschließend mit verschiedenen Solomon-Instanzen getestet wird. Die Ergebnisse dieser Tests werden im Detail analysiert.
Schlüsselwörter
Vehicle Routing Problem, Time Windows, Multiple Deliverymen, Lokale Suche, 2-opt, Cross, Relocate, Ejection Chains, Routenplanung, Optimierung, Algorithmus, Solomon-Instanzen
- Citar trabajo
- Michael Huemer (Autor), 2011, Heuristics for the vehicle routing problem with multiple deliverymen, Múnich, GRIN Verlag, https://www.grin.com/document/232841
