Optimale Lösungen von Tourenoptimierungsproblemen mit geteilter Belieferung, Zeitfenstern, Servicezeiten und vier LKW-Typen

Diese kurze Arbeit stellt vier optimale Lösungen für das sogenannte 'Split Delivery Vehicle Routing Problem with Time Windows' (SDVRPTW) vor. Eine detaillierte Beschreibung dieser Problemklasse findet man in [Des2010]. Diese Arbeit nimmt insofern eine Erweiterung gegenüber [Des2010] vor, als das hier mehrere (vier) LKW-Typen zugelassen wurden und gegenüber [Mu2011], dass Zeitfenster hinzugekommen sind. Die hier vorgestellten optimalen Beispiel-Lösungen wurden mit einem gemischt ganzzahligem Linearen Programm in der Sprache GLPK beschrieben und mittels IBM-ILOG-CPLEX-Solver in der Version 12.3 berechnet. Als Zwischenformat diente das lp-Format. Es werden sämtliche Eingabedaten und Parameter angegeben, so dass Hersteller von Tourenplanungssoftware und deren Nutzer die hier vorgestellten Lösungen als Maßstab für die Qualität ihrer Software verwenden können. Die hier betrachteten Probleme haben eine kombinatorische Komplexität, d.h. ab einer gewissen Problemgröße wird es niemals optimale Lösungen mit den heutigen Computerarchitekturen geben können. Weil in der Praxis aber häufig gar nicht so große Problemstellungen auftreten, z.B. weil ein LKW-Fahrer pro Tag nur eine begrenzte Zeit, z.B. 600 Minuten, einen LKW lenken darf, oder eine Firma ihr Vertriebsgebiet bereits in Vertriebsgebiete mit weniger als zehn Orten aufgeteilt hat, wird weltweit nach Methoden zur Bestimmung optimaler Lösungen des SDVRPTW gesucht.