Combined Approximate Dynamic Programming for Dynamic Same-Day Delivery
Final Report Abstract
Ziel des Projekts war die Zusammenführung von online- und offline-ADP-Verfahren für die dynamische Same-Day Belieferung (SDD). Zu diesem Zweck wurde zunächst ein geeignetes real-weltliches SDD Problem in dem Restaurant Meal Delivery Problem (RMDP) gefunden. Das identifizierte Problem wurde als Markov Entscheidungsprozess mit endogenen Kundenentscheidungen modelliert. Für das Problem wurde ein online-, offline- und ein online-offline Verfahren entwickelt und auf algorithmische und betriebswirtschaftliche Aspekte analysiert. Wir zeigen anschaulich, wie online- und offline-Verfahren kombiniert werden können, sodass Vorteile beider Verfahren erhalten bleiben und individuelle Nachteile verringert werden. Die Methode ist generisch und für jeden online Simulation eines Markov Entscheidungsprozess, der eine rechenaufwendige Entscheidungspolitik erfordert, einsetzbar. Darüber hinaus zeigen unsere Experimente auf RDMP Instanzen, dass genau Lieferzeitvorhersagen auch zu schnelleren Lieferungen und frischerem Essen führen. Über den ursprünglichen Antrag hinaus erweiterten wir unsere Forschungsfrage in zwei Hinsichten. Erstens: Unser ursprüngliches Modell des Markov Entscheidungsprozess für das RMDP integriert endogene Kundenentscheidungen. Diesen Aspekt untersuchten wir verstärkt, indem wir Kundenentscheidungen (die Wahl des Restaurants) beeinflussen, um den Lieferprozess ganzheitlich zu verbessern. Zweitens: Wir argumentieren, dass eine Kombination von online- und offline-Verfahren notwendig ist, um kontemporäre SDDs mit komplexen kombinatorischen Entscheidungsräumen effizient und effektiv zu lösen. Eine konkrete Implementierung und Analyse solcher Methoden für die Generierung von Entscheidungskandidaten wird im Folgeprojekt „Integration von Maschinellem Lernen in die kombinatorische dynamische Optimierung für urbane Transportdienste" erfolgen.
Publications
-
Supervised Learning for Arrival Time Estimations in Restaurant Meal Delivery. Transportation Science, 56(4), 1058-1084.
Hildebrandt, Florentin D. & Ulmer, Marlin W.
-
Dynamic priority rules for combining on-demand passenger transportation and transportation of goods. European Journal of Operational Research, 309(1), 399-408.
Bosse, Alexander; Ulmer, Marlin W.; Manni, Emanuele & Mattfeld, Dirk C.
-
Opportunities for reinforcement learning in stochastic dynamic vehicle routing. Computers & Operations Research, 150, 106071.
Hildebrandt, Florentin D.; Thomas, Barrett W. & Ulmer, Marlin W.
