Detailansicht
A Solution Approach for the Generalized Consistent Periodic Vehicle Routing Problem
Veronika Schulmeister
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Wirtschaftswissenschaften
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Betriebswirtschaft
Betreuer*in
Richard F. Hartl
DOI
10.25365/thesis.39202
URN
urn:nbn:at:at-ubw:1-29550.13641.708561-1
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Diese Arbeit befasst sich mit dem Generalized Consistent Periodic Vehicle Routing Problem (GenConPVRP), einer Erweiterung des Generalized Consistent Vehicle Routing Problem (GenConVRP). In beiden Fällen werden konstante Anfahrtszeiten und Fahrerzuteilungen zur Steigerung der Kundenzufriedenheit eingesetzt. Die Neuheit am GenConPVRP ist, dass der Besuchs-Terminplan eines Kunden flexibel ist. Abhängig von der kundenspezifischen Besuchsfrequenz wird aus einer Menge an möglichen Besuchsterminplänen ein passender gewählt. Mit anderen Worten, die Verteilung der Kundenbesuche über den Planungszeitraum wird zur Aufgabe des Optimierungsprozesses.
Zur Lösung des GenConPVRP wird ein Large Neighborhood Search (LNS) angewendet. Besagte Methode verbessert iterativ eine initiale Lösung unter Verwendung von mehreren Zerstör- und Reparatur-Subheuristiken. Um die erforderlichen Wechsel der Besuchskombinationen in den Optimierungsprozess zu integrieren, wird ein Zwischenschritt, der Schedule Swap, zwischen dem Zerstör- und dem Reparatur-Operator eingebaut.
Neben dem Schedule Swap wird auch ein neuer Zerstör-Operator (der Worst Removal-Demand Savings) vorgestellt. Dieser macht die Entfernung eines Kunden aus der Lösung abhängig von der dadurch erzielbaren Reduktion von Schwankungen in den Gesamttagesnachfragen.
Rechnerische Experimente zur Erhebung, sowohl exakter, als auch heuristischer Daten werden auf das GenConPVRP angewendet. Kleine Instanzen (10 bis 12 Kunden) werden mit einem MIP-solver optimal gelöst, große Instanzen (50 bis 199 Kunden) heuristisch mit dem LNS. Die Resultate zeigen Schwächen der Lösungsansätze auf Grund der hohen Komplexität des vorliegenden Problems.
Abstract
(Englisch)
This thesis introduces the Generalized Consistent Periodic Vehicle Routing Problem (GenConPVRP), an extension of the Generalized Consistent Vehicle Routing Problem (GenConVRP). Both problems consider consistency in arrival times and driver allocation to improve customer satisfaction. The novelty of the GenConPVRP is that the visiting schedule of a customer is flexible. Contingent on a customer specific visiting frequency, a suitable visiting combination is chosen from a set of available visiting schedules. With other words, the customer visiting distribution over the planning horizon is made part of the optimization process.
A Large Neighborhood Search (LNS) is applied on the GenConPVRP. The method iteratively improves an initial solution by employing several destroy and repair sub-heuristics. In order to integrate the necessary changes in visiting combinations into the optimization process, an intermediate step, the schedule swap, is executed between the destroy and the repair operator. Besides the schedule swap, a new destroy operator (worst removal-demand savings) is introduced.
It attaches customer removes to the potential of reducing fluctuations in the total day demands.
Computational experiments for the GenConPVRP include both exact and heuristic results.
Small instances (10 to 12 customers) are solved to optimality by a MIP-solver, large instances (50 to 199 customers) are heuristically solved by the LNS. Results reveal struggles of these approaches with the high level of complexity of the present problem.
Schlagwörter
Schlagwörter
(Englisch)
Vehicle Routing Periodic Vehicle Routing Generalized Consistent Vehicle Routing Large Neighborhood Search Metaheuristics
Schlagwörter
(Deutsch)
ohne Angaben
Autor*innen
Veronika Schulmeister
Haupttitel (Englisch)
A Solution Approach for the Generalized Consistent Periodic Vehicle Routing Problem
Publikationsjahr
2015
Umfangsangabe
V, 62 Seiten : Diagramme
Sprache
Englisch
Beurteiler*in
Richard F. Hartl
Klassifikationen
85 Betriebswirtschaft > 85.03 Methoden und Techniken der Betriebswirtschaft ,
85 Betriebswirtschaft > 85.99 Betriebswirtschaft: Sonstiges
AC Nummer
AC12663960
Utheses ID
34723
Studienkennzahl
UA | 066 | 915 | |