Behandlung des Dynamischen Pickup and Delivery Vehicle Routing Problems mit Zeitfenstern und Ladebedingungen mittels spezieller Statusgraphen

Abstract

Das Vehicle Routing Problem (VRP) gehört zu den wichtigsten und am meisten erforschten kombinatorischen Optimierungsproblemen. Dank fortschreitender Kommunikations- und Informationstechnologie können Informationen inzwischen zu vertretbaren Kosten in Echtzeit übertragen und in angemessener Zeit verarbeitet werden. Lösungsverfahren für dynamische Entscheidungsprobleme werden damit nicht zuletzt auch wegen der enormen ökonomischen Bedeutung des Transports in der Praxis nachgefragt. In der vorliegenden Arbeit wird eine Heuristik zur Lösung des dynamischen Pickup and Delivery Vehicle Routing Problems mit Zeitfenstern entwickelt, wobei für jeden Auftrag zwei strikte Zeitfenster zu erfüllen sind. Zusätzlich werden auch die Problemvarianten mit den Ladebedingungen Backhauls, LIFO und LIFO-q untersucht und mit der Heuristik gelöst. Die Heuristik besteht aus einem sehr schnellen Algorithmus zur Lösung des Single Vehicle Pickup and Delivery Vehicle Routing Problems mit Zeitfenstern und einer heuristischen Zuordnung der Aufträge zu den Fahrzeugen. Das Single Vehicle Routing Problem wird angegangen, indem der A*-Algorithmus mit besonderen Schätzfunktionen auf einen speziellen Zustandsgraphen angewandt wird. Bei den entwickelten Benchmark-Datensätzen wurden praxistaugliche Rechenzeiten von wenigen Sekunden für interessante Problemstellungen mit mehreren hundert anzufahrenden Orten erreicht. Die Arbeit wird abgerundet durch eine genaue Analyse der entwickelten Graphenstruktur, auch im Hinblick auf die sich ergebenden Änderungen bei Einführung von Ladebedingungen.