Integration von Maschinellem Lernen in die kombinatorische dynamische Optimierung für urbane Transportdienste

• Antragsteller: Professor Dr. Marlin Ulmer
• Fachliche Zuordnung: Management und Marketing
• Förderung: Förderung seit 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 510629371

Das Ziel des Projektes ist die Kombination der gemischt-ganzzahligen linearen Programmierung (MILP) und des Reinforcement Learning (RL), um eine effektive Entscheidungsunterstützung für stochastische dynamische Pickup-and-Delivery Probleme (SDPDPe) zu erreichen.SDPDPe spielen in der urbanen Logistik eine zunehmend wichtige Rolle. Sie beschreiben den oft zeitkritischen Transport von Personen oder Waren in der Stadt. Beispiele sind Kurierdienste, Onlineessenslieferung, Same-day Lieferdienste, oder Ridesharing. Für all diese Probleme müssen operative Entscheidungen über Fahrzeugzuordnung und Tourenplanung in Echtzeit getroffen werden. Solche Entscheidungen müssen den aktuellen Bedarf effizient erfüllen und die Fahrzeugflotte gleichzeitig flexibel für zukünftige Anfragen halten.Aus Modellsicht sind SDPDPe durch eine Folge von Entscheidungszuständen unter Unsicherheit gekennzeichnet, bei der der volle Wert einer Entscheidung sich erst später im Verlauf des Tages offenbart. Das Durchsuchen des kombinatorischen Entscheidungsraums nach effizienten Touren in jeden Zustand erfordert die Lösung eines komplexen MILPs. Diese Komplexität wird nun durch die Herausforderung verstärkt, dass eine Bewertung von Entscheidungen auf ihre Effektivität angesichts zukünftiger Unsicherheit notwendig ist - eine ideale Anwendung für RL. Beides ist von zentraler Bedeutung, um den operativen Anforderungen gerecht zu werden. Somit wäre eine direkte Kombination beider Methodenklassen notwendig. Diese steht allerdings aus unterschiedlichen Gründen noch aus und ist Ziel dieses Forschungsprojektes. Konkret schlagen wir vor das MILP durch RL zu manipulieren, um sowohl effiziente als auch effektive Entscheidungen zu erhalten. Die Manipulation kann die Zielfunktion oder die Nebenbedingungen verändern. So werden Anreiz- oder Strafbedingungen hinzugefügt, um bestimmte Entscheidungen zu erzwingen oder zu verbieten. Alternativ werden Nebenbedingungen angepasst, zum Beispiel, um Flotten-Ressourcen zu reservieren.Die Herausforderung ist, zu entscheiden, wo und wie die Manipulation stattfinden sollen. Je nach SDPDPe setzt sich die Zielfunktion unterschiedlich zusammen und haben Nebenbedingungen wie Zeitfenster oder Fahrzeugkapazitäten unterschiedliche Relevanz. Der erste Schritt des Projektes zielt somit auf die Identifikation relevanter Bereiche innerhalb des MIPs mittels (un)supervised learning. Sind die "interessanten" Bereiche identifiziert, besteht die zweite Herausforderung darin, die richtige Parametrisierung zu finden. Hier werden RL-Methoden eingesetzt, die die relevanten MIP-Komponenten zustandsabhängig manipulieren.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Niederlande
• Kooperationspartner: Professor Roberto Roberti, Ph.D.