Integrating machine learning in combinatorial dynamic optimization for urban transportation services

• Applicant: Professor Dr. Marlin Ulmer
• Subject Area: Management and Marketing
• Term: from 2022 to 2024
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 510629371

• Final Report Year: 2025

Final Report Abstract

The goal of the project was to combine Mixed-Integer Linear Programming (MILP) and Reinforcement Learning (RL) solution strategies for stochastic dynamic pickup and delivery problems (SDPDPs). To this end, RL, MILP, and combined methods were first implemented and analyzed on synthetic problem instances. The results obtained were used to identify suitable real-world SDPDPs and solve them through combined methods. We chose the Same-Day Delivery Problem, the Restaurant Meal Delivery Problem, and the Technician Routing Problem. The problems were modeled each as a Markov Decision Process. For each problem, a combined MILP and RL method was developed and analyzed from both an algorithmic and business perspective. For the Same-Day Delivery Problem, we use RL to learn state-dependent tour length restrictions in order to balance efficiency and flexibility in the delivery process. For the Restaurant Meal Delivery Problem, we integrate the long-term value of decisions into the search of the decision space. For the Technician Routing Problem, we use RL to learn the weighting of different objectives (efficiency, robustness, customer satisfaction) state-dependently to achieve a better overall trade-off. Our publications convincingly demonstrate how MILP and RL methods can be combined, allowing the advantages of both methods to be retained while minimizing individual disadvantages. The methodically concepts are generic and can be applied to any dynamic routing problem characterized by a Markov Decision Process with complex decisions and high uncertainty.

Publications

• 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.