Synchronisierte Planung interdependenter Ressourcen in der Transportlogistik
Zusammenfassung der Projektergebnisse
Im Rahmen des Projekts wurden zur Lösung von Tourenplanungsproblemen mit mehrfachen Synchronisationsbedingungen exakte und heuristische Lösungsverfahren für allgemeine zeitliche und nachfragebezogene Synchronisationsbedingungen innerhalb derselben Tour (Intra-Tour-Synchronisation) und zwischen verschiedenen Touren (kombinierte Intra- und Inter-Tour-Synchronisation) entwickelt und implementiert. Ein zentrales Studienobjekt der ersten Förderphase war das Split-Delivery Vehicle-Routing Problem mit Zeitfenstern, bei dem mehrere Besuche pro Kunde erlaubt sind. In der zweiten Förderphase wurden die Publikationen zu den Verfahren abgeschlossen. Mit den Branch-Price-and-Cut (BPC)-Algorithmen konnten zahlreiche Benchmarkinstanzen erstmals optimal gelöst werden. 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. Bei Varianten des Multiple Vehicle Traveling Purchaser Problems (MVTPP) besteht der zentrale Synchronisationsaspekt in der Koordination der einzukaufenden Güter innerhalb einer Tour und vor allem über die verschiedenen Touren hinweg. Auch hier wurde ein komplett neues BPC-Verfahren entwickelt und implementiert. Die wichtigste Neuerung ist die Art und Weise, in der die Subprobleme der Spaltengenerierung durch einen Labeling-Algorithmus (dynamische Programmierung) gelöst werden: Die genauen Kaufentscheidungen werden aufgeschoben, bis die Route vollständig de niert ist. Der entscheidende Punkt dabei ist die De nition einer effektiven Dominanzregel. Unsere neuartige Dominanzregel nutzt einige tiefliegende Eigenschaften der optimalen reduzierten Einkaufskostenfunktion, die wir als supermodular bewiesen haben. Für das UMVTPP mit Inkompatibilitäten zwischen Produkten ist der Ersatz von Inkompatibilitätsbeschränkungen durch mehrere Pricing-Subprobleme zu einem BPC-Ansatz, der frühere Methoden in Bezug auf die Rechenzeit um eine Größenordnung übertrifft. Im Allgemeinen zeigen die Berechnungsergebnisse, dass die neuen Lösungsstrategien für das Subproblem vorteilhaft sind, insbesondere wenn viele Produkte bei einem Lieferanten verfügbar sind und die Routen relativ kurz sind. Drittes Studienobjekt war das Multiple Vehicle Bike-Balancing Problem (MVBP), welches ein zentrales Planungsproblem für die Betreiber von Fahrrad-basierten Shared-Mobility-Systemen ist. Es hat zum Ziel, kostenmiminal eine passende Anzahl von Fahrrädern an jeder Station zu gewährleisten. Es wurde ausgewählt, um die Idee der Diskretisierung von Ressourcen bei der Lösung der Subprobleme in Column Generation genauer zu analysieren. Eine vorteilhafte Diskretisierung ist die hinsichtlich der Ressourcen, die die Anzahl der gelieferten oder mitgenommenen Fahrräder pro besuchter Station beschreiben. Als erfolgreich für die Lösung des statischen MVBP erwies sich eine angepasste Version der ng-route- Relaxation, die als Limited Task Memory (LTM)-Relaxation für den MVBP bezeichnet wird. Diese Relaxation erlaubt eine stärkere Dominanzregel zwischen Paaren von Labels. Im Ergbnis konnte ein exakter Branch- Price-and-Cut-Algorithmus entworfen und implementiert werden, der einen neuen Standard zur Lösung des statischen MVBP setzt. Ein generisches exaktes Lösungsverfahren wurde VRPS mit mehreren voneinander abhängigen Ressourcen entwickelt. In entsprechenden Branch-and-Price-Algorithmen können Tradeoffs zwischen dem Verbrauch mindestens dreier Ressourcen adäquat behandelt werden. Ressourcenabhängigkeiten wurde durch einen verschachtelten, zweistufigen Dekompositions-Ansatz aufgelöst, bei dem sowohl das ursprüngliche Problem als auch das Pricing-Subproblem durch jeweils einen BPC-Algorithmus gelöst wird. Das Dekompositionsverfahren ist nicht nur auf das im Artikel untersuchte VRSP anwendbar, sondern lässt sich ebenso auf andere VRPs mit Tradeoffs zwischen dem Verbrauch mindestens dreier Ressourcen anwenden. Wir erwarten daher, dass zukünftig solche Probleme auf ähnliche Weise gelöst werden.
Projektbezogene Publikationen (Auswahl)
-
(2019): Branch-and-Cut for the Split Delivery Vehicle Routing Problem with Time Windows. Transportation Science, Bd. 53, Nr. 2, S. 442–462
Nicola Bianchessi, Stefan Irnich
-
(2019): Nested branch-and-price-and-cut for vehicle routing problems with multiple resource interdependencies. European Journal of Operational Research, Bd. 276, S. 549–565
Christian Tilk, Michael Drexl, Stefan Irnich
-
(2019): The Split Delivery Vehicle Routing Problem with Time Windows and Customer Inconvenience Constraints- Transportation Science, Bd. 53, Nr. 4, S. 1067–1084
Nicola Bianchessi, Michael Drexl, Stefan Irnich
-
Branch-and-Cut for the Active-Passive Vehicle Routing Problem Technical Report LM-2019-04, Chair of Logistics Management, Johannes Gutenberg University, Mainz, 2019
Christian Tilk, Michael Forbes
-
(2021): A branch-price-and-cut algorithm for the capacitated multiple vehicle traveling purchaser problem with unitary demand. Discrete Applied Mathematics, Bd. 288, S. 152–170
Nicola Bianchessi, Stefan Irnich, Christian Tilk
-
Adapting the ng-path relaxation for bike balancing problems. Operations Research Letters, Bd. 50, Nr. 3, S. 241–24
Christian Tilk
