Lösung zeitabhängiger logistischer Optimierungsprobleme mit Hilfe zeitreduzierter Relaxierungen

• Antragsteller: Professor Dr.-Ing. Uwe Clausen; Professor Dr. Armin Fügenschuh
• Fachliche Zuordnung: Verkehrs- und Transportsysteme, Intelligenter und automatisierter Verkehr ; Accounting und Finance ; Mathematik
• Förderung: Förderung von 2016 bis 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 289354542

Optimierungsprobleme in der Logistik enthalten oft eine zeitabhängige Komponente. Im einfachsten Fall handelt es sich um früheste und späteste Ankunftszeitpunkte von Sendungen oder Fahrzeugen. Komplexere Anwendungsfälle beinhalten die zeitliche Synchronisation von zwei oder mehr Vorgängen oder die Einhaltung von Vorrangbeziehungen ("erst... danach..."). Unter Beachtung solcher Bedingungen ist eine Zielgröße zu optimieren (minimieren oder maximieren). Derartige Optimierungsprobleme können häufig als gemischt-ganzzahlige Programme formuliert werden. Als Methode zur Berechnung von numerischen Lösungen können Heuristiken entwickelt werden, die erfahrungsgemäß in kurzer Zeit zulässige Lösungen generieren. Um die Optimalität solcher Lösungen zu zeigen, kann man auf Branch-and-Bound-and-Cut-Methoden zurückgreifen, welche im Kern auf Relaxierungen der gemischt-ganzzahligen Formulierung beruhen. Wenngleich dieses Vorgehen für etliche Probleme verwertbare Ergebnisse liefert - stellvertretend sei hier Handlungsreisendenproblem genannt - so findet es vielfach seine Grenzen, wenn zeitliche Aspekte mit diskreten Entscheidungen gekoppelt werden müssen. Die gängigen Modellierungstechniken verwenden entweder eine Big-M-Formulierung, bei der eine kontinuierliche Zeitvariable an eine binäre Entscheidungsvariable mittels Ungleichungen gekoppelt wird. Oder sie verwenden zeitexpandierte Graphen, bei denen die Zeit diskretisiert und in die kombinatorische Struktur des zugrundeliegenden Graphen eingebettet wird. Beide Techniken haben ihre individuellen Probleme: die Big-M-Formulierung kann zu schwachen Relaxierungen führen, bei denen die Zielfunktionswerte der ganzzahligen Optimallösung und der kontinuierlichen Relaxierung weit voneinander entfernt liegen. Die zeitexpandierten Graphen können auf sehr große Instanzen führen, die mit der gegenwärtigen Computertechnik nicht mehr handhabbar sind. Der neue Ansatz, den wir in diesem Forschungsprojekt entwickeln und erproben wollen, besteht darin, von einem zeitabhängigen logistischen Optimierungsproblem ausgehend zu einer zeitfreien Relaxierung zu gelangen, indem die zeitabhängigen Teile der Modelle vernachlässigt werden. Bei dieser Relaxierung handelt es sich weiterhin um ein gemischt-ganzzahliges Problem, welches jedoch wesentlich einfacher numerisch lösbar ist. Im Allgemeinen wird diese Lösung jedoch nicht zulässig in Bezug auf die zeitlichen Aspekte sein, so dass die zeitlichen Bedingungen in die Formulierung sukzessive dort re-integriert werden müssen, wo zeitliche Konflikte auftreten. Wir entwickeln hierzu verschiedene Techniken, die auf Schnittebenen und Branching-Strategien beruhen. Ferner entwickeln wir spezielle Heuristiken, welche versuchen, unzulässige zeitfreie Lösungen in zulässige zeitabhängige Lösungen zu verwandeln. Beide Lösungsansätze, die exakten und die heuristischen, werden in einem Gesamtlöser integriert und anhand ausgewählter Problemklassen getestet.

• DFG-Verfahren: Sachbeihilfen