Combined Approximate Dynamic Programming for Dynamic Same-Day Delivery

• Applicant: Professor Dr. Marlin Ulmer
• Subject Area: Accounting and Finance
• Term: from 2018 to 2023
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 413322447

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.

• DFG Programme: Research Grants
• International Connection: USA
• Cooperation Partner: Professor Justin Goodson, Ph.D.