SynchroTrans: Multi-Dimensional Synchronisation of Heterogeneous Resources in Transport
Final Report Abstract
Die wichtigsten im Projekt erzielten wissenschaftlichen Fortschritte lassen sich wie folgt zusammenfassen: Im Rahmen des Projekts wurden zur Lösung von Tourenplanungsproblemen mit mehrfachen Synchronisationsbedingungen exakte und heuristische Lösungsverfahren für allgemeine zeitliche Synchronisationsbedingungen innerhalb derselben Tour (Intra-Tour-Synchronisation) und zwischen verschiedenen Touren (kombinierte Intra- und Inter-Tour-Synchronisation) entwickelt und implementiert. Ein zentrales Studienobjekt war das Synchronized Pickup-and-Delivery Problem (SPDP), bei dem eine kostenminimale Menge von Touren zur Erfüllung von Transportaufträgen unter Berücksichtigung von Fahrzeugkapazitäten und Öffnungszeitfenstern zu bestimmen ist, wobei Synchronisationsbedingungen die Zeit zwischen der Abholung und der Zustellung eines Auftrags nach oben und unten beschränken. Zur Intra-Tour-Synchronisation beim SPDP wurden vier exakte Lösungsverfahren entwickelt, die auf unterschiedlichen Zerlegungen des Problems basieren. Es wurden umfangreiche Rechenstudien durchgeführt, die klare Aussagen zur Leistungsfähigkeit der Verfahren lieferten. Zur effizienten Zulässigkeitsprüfung von Touren im Rahmen heuristischer Verfahren wurden zwei verschiedene Zulässigkeitstests entwickelt. Es wurden Rechenexperimente mit einer großen Zahl von Testproblemen vorgenommen, um die Laufzeiten der Testroutinen zu vergleichen. Zur Untersuchung der Intra- und Inter-Tour-Synchronisation wurde zunächst das Active-Passive Vehicle-Routing Problem (APVRP) betrachtet, bei dem ein gemeinsamen Einsatz aktiver und passiver Ressourcen erforderlich ist, also z.B. von LKW und Anhängern. Zur Lösung des APVRP wurde ein exakter Algorithmus entwickelt, der auf einer nichttrivialen Netzwerkrepräsentation des Problems beruht. Rechenexperimente zeigten, dass das Verfahren optimale Lösungen für eine ganze Reihe von Benchmarkinstanzen liefert. Im Rahmen der Untersuchungen zum APVRP konnten darüber hinaus problemunabhängige methodische Erkenntnisse für sog. Branch-and-Price-Verfahren gewonnen werden. Für die kombinierte Intra- und Inter-Tour-Synchronisation wurden zudem Untersuchungen zum Nested Branch-and-Priceand-Cut durchgeführt, einem Verfahren, das sich zur Lösung von Routingproblemen mit mehrfachen Ressourceninterdependenzen eignet, bei denen herkömmliche Ansätze scheitern. Hier gelang es, die praktische Einsatzfähigkeit des Verfahrens mittels einer e zienten Implementierung zur Lösung eines Routingproblems mit mehrfachen Ressourceninterdependenzen nachzuweisen. Ein weiterer Forschungsgegenstand war das Split-Delivery Vehicle-Routing Problem mit Zeitfenstern, bei dem, im Gegensatz zu Standard-Tourenplanungsproblemen, mehrere Besuche pro Kunde erlaubt sind. Es wurde ein Verfahren für eine neuartige Modellformulierung entwickelt, mit dem zahlreiche Benchmarkinstanzen erstmals optimal gelöst werden konnten. Darauf aufbauend erfolgten Untersuchungen zur Gestaltung von Lieferstrategien in Distributionssystemen, wenn mehrere Besuche pro Kunde erlaubt sind. Es zeigte sich, dass Mehrfachbesuche grundsätzlich lohnend sind, eine Begrenzung der Anzahl der Besuche pro Kunde kaum restriktiv wirkt und eine zeitliche Abstimmung der Besuche als die geeignete Maßnahme zum Ausgleich von Lieferanten- und Kundeninteressen angesehen werden kann. Die im Rahmen des Projekts erreichten Ergebnisse stellen einen echten wissenschaftlichen Fortschritt auf dem Gebiet der Synchronisation im Transport dar. Anwendungsperspektiven sind zum einen für die heuristischen Verfahren gegeben, die direkt in kommerziellen Tourenplanungssystemen implementiert werden können und zur Lösung von Praxisproblemen geeignet sind. Zum anderen liefern die zum SDVRPTW gewonnenen Ergebnisse für Praktiker wertvolle Einsichten für die Gestaltung von Lieferstrategien zur Erhöhung der Kundenzufriedenheit. Als Überraschungen im Projektverlauf und bei den Ergebnissen können folgende Punkte erwähnt werden: Von den beiden zur heuristischen Lösung des SPDP entwickelten Zulässigkeitstests nahm derjenige mit der größeren theoretischen Worst-Case-Laufzeitkomplexität auch für Touren mit vielen Aufträgen eine im Durchschnitt kürzere Rechenzeit in Anspruch. Eine solche Diskrepanz zwischen theoretischer und praktischer Leistungsfähigkeit eines Verfahrens wird immer wieder beobachtet, stellt aber doch die Ausnahme von der Regel dar. Bei der Lösung des APVRP war zu beobachten, dass die Berücksichtigung zeitlicher Komponenten in der Zielfunktion die Lösbarkeit des Problems ganz erheblich erschwerte. Auch das war von den Projektbearbeitern so nicht erwartet worden.
Publications
- (2019) Branch-and-Cut for the Split Delivery Vehicle Routing Problem with Time Windows. Transportation Science 53 (2) 442–462
Bianchessi, Nicola; Irnich, Stefan
(See online at https://doi.org/10.1287/trsc.2018.0825) - (2019) The Split Delivery Vehicle Routing Problem with Time Windows and Customer Inconvenience Constraints. Transportation Science 53 (4) 1067–1084
Bianchessi, Nicola; Drexl, Michael; Irnich, Stefan
(See online at https://doi.org/10.1287/trsc.2018.0862) - Route Feasibility Testing and Forward Time Slack for the Synchronized Pickup and Delivery Problem. Technical Report LM-2015-01 (revised), Chair of Logistics Management, Johannes Gutenberg University, Mainz, 2015
Timo Gschwind
- (2016): A Comparison of Column-Generation Approaches to the Synchronized Pickup and Delivery Problem. European Journal of Operational Research, Bd. 247, Nr. 1, S. 60–71
Timo Gschwind
(See online at https://doi.org/10.1016/j.ejor.2015.06.017) - (2018): Branch-and-Price-and-Cut for the Active-Passive Vehicle-Routing Problem. Transportation Science, Bd. 52, Nr. 2, S. 300–319
Christian Tilk, Nicola Bianchessi, Michael Drexl, Stefan Irnich, Frank Meisel
(See online at https://doi.org/10.1287/trsc.2016.0730) - Nested Branch-and-Price-and-Cut for Vehicle Routing Problems with Multiple Resource Interdependencies. Technical Report LM-2018-01 (revised), Chair of Logistics Management, Johannes Gutenberg University, Mainz, 2018
Christian Tilk, Michael Drexl, Stefan Irnich
