Titelaufnahme

Titel
Praktische Analyse des Linehaul-feeder Vehicle Routing Problem / Markus Loibnegger, Bakk.rer.soc.oec.
Weitere Titel
Practical analysis of the linehaul-feeder vehicle routing problem
Praktische Analyse des Linehaul-feeder Vehicle Routing Problems
Verfasser/ VerfasserinLoibnegger, Markus
Begutachter / BegutachterinReimann, Marc
ErschienenGraz, 2016
UmfangVI, 77 Blätter : Illustrationen
HochschulschriftKarl-Franzens-Universität Graz, Masterarbeit, 2016
Anmerkung
Abweichender Titel laut Übersetzung des Verfassers/der Verfasserin
Abstracts in Deutsch und Englisch
SpracheDeutsch
DokumenttypMasterarbeit
Schlagwörter (GND)Tourenplanung
URNurn:nbn:at:at-ubg:1-98430 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
Praktische Analyse des Linehaul-feeder Vehicle Routing Problem [1.65 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

Ziel der Arbeit ist einerseits die Schaffung und Analyse von Instanzen zum NP-schweren Linehaul-feeder Vehicle Routing Problem with Time Windows (LFVRPTW) und andererseits die Analyse eines Modells zum LFVRPTW, das über eine Standardsoftware exakte Lösungen generiert. Das Modell ist aus Brandstätter (2017) entnommen, ist in der AMPL-nahen Programmiersprache GLPK/GMPL modelliert, wird im Zuge der Analyse für AMPL adaptiert und mit Hilfe des ILOG CPLEX-Solvers gelöst. Die Analyse erfolgt in zwei Teilen. Im ersten Teil wird die C101 Solomon-Instanz, die aus 25 Kunden besteht, in 20 Instanzen unterteilt. Die kleinste Instanz umfasst dabei die ersten fünf Kunden aus Solomon C101 und wird jeweils um einen Kunden bis hin zur größten Instanz mit 25 Kunden erhöht. Die Ergebnisse dieser 20 Instanzen aus der Berechnung mit dem Modell zum LFVRPTW werden im ersten Schritt mit einem Modell zum Vehicle Routing Problem with Time Windows verglichen. Im zweiten Schritt werden die Zeitfenster vernachlässigt. Dabei soll die Korrektheit des Modells ohne Kundenunterscheidung und Transshipments sichergestellt werden. Im zweiten Teil der Analyse werden symmetrisch angeordnete Instanzen ohne Zeitfenster verfasst, gelöst und analysiert. Hierbei soll der Vorteil, der sich durch die Miteinbeziehung von Transshipments gegenüber dem Vehicle Routing Problem mit heterogener Flotte und heterogenen Kunden ergibt, aufgezeigt werden. Da die Rechenzeiten von exakten Methoden exponentiell mit der Kundenanzahl bzw. dem Umfang der eingegebenen Daten ansteigen, werden Timelimits und Gaplimits eingefügt, um das Verfahren frühzeitig abzubrechen. Durch den frühzeitigen Abbruch des Verfahrens wird ein Absturz der Software aufgrund vollständiger Auslastung des Arbeitsspeichers verhindert und so die Auswertung von Zwischenergebnissen ermöglicht. Diese Zwischenergebnisse werden mit Lösungen aus einer Heuristik (Senarclens de Grancy 2015) und mit optimalen Lösungen verglichen.

Zusammenfassung (Englisch)

The purpose of this work is the creation and analysis of instances for the Linehaul-feeder Vehicle Routing Problem with Time Windows (LFVRPTW) on the one hand, and the analysis of the LFVRPTW-model, which generates exact solutions by a standard software, on the other hand. The model is taken from Brandstätter (2017), modelled by the near-AMPL language GLPK/GMPL and adapted to AMPL through the analysis and solved by the help of the ILOG CPLEX Solver. The analysis consists of two main parts. In the first part the C101 Solomon-instance, which consists of 25 customers, is divided into 20 instances. The smallest instance includes the first five customers of the C101 Solomon-instance and is added step by step up to 25 customers. The solutions of the computation of the 20 instances are compared to a model of the Vehicle Routing Problem with Time Windows at the first step. The time windows are ignored at the second step. This analysis should ensure the correctness of the model without transshipments and different customers. In the second part symmetric instances without time windows are created, solved and analysed. This analysis should show the advantage of the model with transshipments compared to the Vehicle Routing Problem with heterogeneous fleets and heterogeneous customers. The computation times of the exact method increase exponentially with the amount of data or the number of customers and therefore timelimits and gaplimits are set to interrupt the computation. The crash of the software due to full utilization of the random access memory is prevented by a premature interruption. These interim findings are compared with heuristic (Senarclens de Grancy 2015) and optimal solutions.