Titelaufnahme

Titel
Entwicklung von komplexen Heuristiken für ein Transport- und Routenproblem mit Restriktionen für die Güterkombination / Lukas Johannes Herzog
Weitere Titel
Development of complex heuristics for a transportation and routing problem with restricted loading combinations
Verfasser/ VerfasserinHerzog, Lukas Johannes
Begutachter / BegutachterinPferschy, Ulrich
ErschienenGraz, April 2017
UmfangVII, 80 Blätter : Zusammenfassungen (2 Blätter)
HochschulschriftKarl-Franzens-Universität Graz, Masterarbeit, 2017
Anmerkung
Abweichender Titel laut Übersetzung des Verfassers/der Verfasserin
Zusammenfassungen in Deutsch und Englisch
SpracheDeutsch
DokumenttypMasterarbeit
Schlagwörter (GND)Tourenplanung / Heuristik
URNurn:nbn:at:at-ubg:1-113041 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
Entwicklung von komplexen Heuristiken für ein Transport- und Routenproblem mit Restriktionen für die Güterkombination [0.98 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

Ziel dieser Arbeit ist es eine Heuristik zur Lösung des Heterogenen Vehicle Routing Problems mit Zeitfenstern und einer Ladungsbeschränkung für inkompatible Güter, auch bekannt als HVRPTW-ILC, zu finden. Dazu werden zuerst verschiedene verwandte Probleme und die dafür bekannten Lösungsansätze vorgestellt. Ein aktueller Lösungsansatz aus der Literatur wird im Detail analysiert und seine Fehlerhaftigkeit nachgewiesen. Der Nachweis der Fehlerhaftigkeit gelingt auf Basis der publizierten Ergebnisse. Zusätzlich wird ein ganzzahliges, lineares Programm (ILP) aufgestellt und erweitert. Das hier vorgestellte ILP ermöglicht das Finden einer Optimallösung bzw. einer unteren Schranke durch eine Relaxation für verschiedene Varianten des Problems. Das ILP wird in PuLP implementiert und mit dem Gurobi Solver gelöst. Das ermöglicht nochmals den Nachweis der Inkorrektheit der publizierten Lösungen. Anschließend wird ein neuer Ruin and Recreate Ansatz vorgestellt. Diese Heuristik basiert auf dem gleichen Grundprinzip wie die Heuristik, mit der die bereits publizierte inkorrekte Lösung gefunden wurde. Mit der neuen Heuristik können schnell akzeptable Lösungen gefunden werden. Zusätzlich zu der Ruin and Recreate Heuristik wird eine neue Möglichkeit zur Findung einer Startlösung vorgestellt. Die Ruin and Recreate Heuristik wird auf die bekannten Solomon Instanzen sowie ein reales Problem angewandt. Diese Heuristik wird anschließend mit einem anderen Lösungsansatz, der auf Tabu Search basiert, verglichen. Der Vergleich der beiden Lösungsansätze zeigt, dass beide Lösungsansätze gute Ergebnisse liefern können. Abschließend werden für die neu vorgestellte Heuristik verschiedenste Verbesserungsmöglichkeiten und weitere Anwendungsgebiete besprochen.

Zusammenfassung (Englisch)

The purpose of this thesis is to find a solution for the heterogeneous vehicle routing problem with time windows and loading constraints for incompatible items, also known as HVRPTW-ILC. Therefore, well-known related problems will be discussed and several different approaches will be presented. One recent approach from the literature will be discussed in detail and shown to be incorrect. The incorrectness will be shown based on the published results. In addition an integer linear programming model (ILP) is set up and extended. The presented mathematical model will allow finding optimal solutions or at least lower bounds by relaxations for different versions of the problem. The model will be implemented in PuLP and solved with the Gurobi solver. This allows to proof the incorrectness of the published solutions once again. Subsequently a new ruin and recreate procedure will be introduced. This heuristic is based on the same basic principles as the heuristic that has been published, but shown to deliver incorrect solutions. This heuristics allows finding acceptable solutions within a short running time. In addition to the ruin and recreate procedure a new approach to find an initial solution will be presented. The ruin and recreate heuristic will be applied to the well-known Solomon instances and a real world problem. This approach will then be compared to another heuristic approach based on a tabu search strategy. The comparison will show that both, the ruin and recreate and also the tabu search strategy, are able to deliver good results. Finally, further improvements and possibilities for future applications of the newly presented ruin and recreate heuristics will be discussed.