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.
|