Integration von Maschinellem Lernen in die kombinatorische dynamische Optimierung für urbane Transportdienste
Zusammenfassung der Projektergebnisse
Ziel des Projekts war die Zusammenführung von Mixed-Integer Linear Programming (MILP)- und Reinforcement Learning (RL)-Lösungsstrategien für stochastisch dynamische Pickupund Delivery Probleme (SDPDPe). Zu diesem Zweck wurden zunächst RL, MILP, und kombinierte Verfahren implementiert und auf synthetischen Probleminstanzen analysiert. Die gewonnenen Ergebnisse wurden genutzt, um geeignete real-weltliche SDPDPe zu identifizieren und durch kombinierte Verfahren zu lösen. Wir entschieden uns für das Same-Day Delivery Problem, das Restaurant Meal Delivery Problem und das Technician Routing Problem. Die Problemstellungen wurden als Markov Entscheidungsprozess modelliert. Für jedes Problem wurde ein kombiniertes MILP- und RL Verfahren entwickelt und auf algorithmische und betriebswirtschaftliche Aspekte analysiert. Für das Same-Day Delivery Problem lernen wir per RL zustandsabhängige Tourlängenrestriktionen, um Effizienz und Flexibilität im Lieferprozess zu balancieren. Für das Restaurant Meal Delivery Problem integrieren wir den langfristigen Wert von Entscheidungen in die Suche des Entscheidungsraumes. Für das Technician Routing Problem lernen wir unterschiedliche Ziele (Effizienz, Robustheit, Kundenzufriedenheit) zustandsabhängig mittel RL zu gewichten, um einen ganzheitlichen zustandsabhängigen Trade-Off zu erreichen. Unsere Publikationen zeigen anschaulich, wie MILP- und RL-Verfahren kombiniert werden können, sodass Vorteile beider Verfahren erhalten bleiben und individuelle Nachteile verringert werden. Die vorgestellten Konzepte sind generisch und für alle dynamischen Tourenplanungsprobleme, die durch einen Markov Entscheidungsprozess mit komplexen Entscheidungen und hoher Unsicherheit gekennzeichnet sind, einsetzbar.
Projektbezogene Publikationen (Auswahl)
-
Learning State-Dependent Policy Parametrizations for Dynamic Technician Routing with Rework. Transportation Science, 59(5), 1153-1171.
Stein, Jonas; Hildebrandt, Florentin D.; Ulmer, Marlin W. & Thomas, Barrett W.
-
The Restaurant Meal Delivery Problem with Ghost Kitchens. Transportation Science, 59(2), 433-450.
Neria, Gal; Hildebrandt, Florentin D.; Tzur, Michal & Ulmer, Marlin W.
-
Integrated Fleet and Demand Control for On-Demand Meal Delivery Platforms. Management Science, 72(2), 932-954.
Hildebrandt, Florentin D.; Lesjak, Žiga; Strauss, Arne & Ulmer, Marlin W.
