Heuristics for the vehicle routing problem with multiple deliverymen

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

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.