Kombinierte Approximative Dynamische Programmierung für die Dynamische Same-Day Belieferung

Der Onlinehandel wächst international in einem Rekordtempo. Ein wesentlicher zukünftiger Erfolgsfaktor des Onlinehandels sind schnelle Lieferzeiten; insbesondere Same-Day Belieferung (SDD). Allerdings ist SDD kostenintensiv, da die über den Tag eintreffenden Bestellungen in Kombination mit kurzen Lieferfristen wenig Raum für Konsolidierung bieten. Um SDD kosteneffizient anbieten zu können, ist eine methodische Unterstützung notwendig, die auf der operativen Ebene dynamische Liefertouren erstellt, fortschreibt, und bezüglich neuer Information aktualisiert. Zur effektiven Entscheidungsunterstützung muss sie sowohl kurzfristige als auch längerfristige zukünftige Entwicklungen an Fahrzeugbewegungen und Kundenbestellungen antizipieren. SDD-Probleme gehören somit zur Menge der stochastischen und dynamischen Tourenplanungs-Probleme. Diese Problemklasse ist relativ neu und generische Lösungsverfahren sind bisher kaum vorhanden.Auf Grund der hohen Komplexität dieser dynamischen Entscheidungsprobleme können exakte Verfahren nicht angewandt werden. Erste Arbeiten konzentrieren sich auf die approximative dynamische Programmierung (ADP). ADP-Verfahren nutzen Simulation innerhalb des dynamischen Entscheidungsmodelles, um die Auswirkungen einer Entscheidung abzuschätzen. ADP-Verfahren werden nach dem Zeitpunkt, wann die Simulation durchgeführt wird, unterschieden. Online ADP-Verfahren führen die Simulation in einem konkreten Entscheidungszustand durch. Offline ADP-Verfahren simulieren vor dem eigentlichen Start des Entscheidungsprozesses, speichern die Ergebnisse in aggregierter Form, und rufen diese in einem Entscheidungszustand ab. Online Verfahren können kurzfristige Entwicklungen in vollem Detail abbilden während offline Verfahren längerfristige Entwicklungen verlässlich auf aggregierten Niveau abschätzen können. Beide Aspekte sind in der SDD essentiell und keines der Verfahren kann die Erfordernisse vollständig erfüllen. Um sowohl kurzfristige Details als auch längerfristige Auswirkungen berücksichtigen zu können, ist eine Kombination notwendig. Ziel dieses Forschungsprojekt ist eine neue und generische Kombination von online und offline ADP-Verfahren vor, um ein wichtiges betriebswirtschaftliches Problem der SDD zu lösen. Das Verfahren ist so konzipiert, dass es eine zustandsabhängige Gewichtung der Simulationsergebnisse ermöglicht. Für eine neue SDD-Problemstellung werden spezifische quantitative Methoden sowie betriebswissenschaftliche Erkenntnisse zur SDD-Entscheidungsunterstützung generiert. Die vorgestellten Methoden sind hierbei jedoch nicht auf diese Problemstellung beschränkt sondern generisch und können auf eine Vielzahl von dynamischen Tourenplanungsproblemen übertragen werden. Sie sind somit ein wichtiger Schritt hin zu einem generellen Lösungsframework im Bereich der dynamischen Tourenplanung

E-Commerce has increased sales by two-digit percentages in the last years. In the future, same-day delivery (SDD) will become a major success factor for E-Commerce companies. However, offering SDD is expensive because short delivery deadlines and subsequently ordering customers leave little room for consolidation. To cost-efficiently provide SDD, decision support methods are required. On the operational level, these methods dynamically create, update, and adapt delivery tours based on newly revealed information. For effective decision making, these methods need to anticipate both the detailed short term impact as well as the general long-term impact of a decision. SDD-problems form a subgroup of stochastic dynamic vehicle routing problems. This problem class is relatively new and general methods are not established yet. Because of the high complexity of dynamic vehicle routing problems, exact methods cannot be applied. First work in this area draws on heuristic methods of approximate dynamic programming (ADP). ADP-methods use simulation of the dynamic model to approximate a decision’s impact on the future. These methods can be differentiated based on the time these simulations take place. Online methods start simulating in the actual decision state. Offline methods conduct simulations before the decision process starts. They store the aggregated results and access them during the actual decision process. Online methods can simulate using full detail of a decision state but only with limited calculation time available. Offline methods allow frequent simulations and reliable long-term approximations, however, on an aggregated level. For the SDD-problem at hand, both short-term detail and long-term reliability are essential for successful decision support. However, both online and offline methods fall short in one of the two capacities. A combination is necessary. This research projects aims on developing a combined ADP-method for the SDD-problem. The method allows a generic, state-dependent shift between online and offline simulation results. The method will provide effective decision support and business insight for a new and important SDD-problem. Further, this method will be generic and broadly applicable in the field of dynamic vehicle routing. It will therefore be an important step towards a general solution framework in dynamic vehicle routing.