Bibliographic Metadata

Title
Praktische Analyse des Linehaul-feeder Vehicle Routing Problem / Markus Loibnegger, Bakk.rer.soc.oec.
Additional Titles
Practical analysis of the linehaul-feeder vehicle routing problem
Praktische Analyse des Linehaul-feeder Vehicle Routing Problems
AuthorLoibnegger, Markus
CensorReimann, Marc
PublishedGraz, 2016
DescriptionVI, 77 Blätter : Illustrationen
Institutional NoteKarl-Franzens-Universität Graz, Masterarbeit, 2016
Annotation
Abweichender Titel laut Übersetzung des Verfassers/der Verfasserin
Abstracts in Deutsch und Englisch
LanguageGerman
Document typeMaster Thesis
Keywords (GND)Tourenplanung
URNurn:nbn:at:at-ubg:1-98430 Persistent Identifier (URN)
Restriction-Information
 The work is publicly available
Files
Praktische Analyse des Linehaul-feeder Vehicle Routing Problem [1.65 mb]
Links
Reference
Classification
Abstract (German)

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.

Abstract (English)

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.

Stats
The PDF-Document has been downloaded 77 times.