Online decision-making model and algorithm for dynamic and stochastic meal takeout routing problem

ZHANG Xiaonan, ZHANG Jianxiong, LI Xiangqian

Systems Engineering - Theory & Practice ›› 2025, Vol. 45 ›› Issue (1) : 269-289.

PDF(1554 KB)
PDF(1554 KB)
Systems Engineering - Theory & Practice ›› 2025, Vol. 45 ›› Issue (1) : 269-289. DOI: 10.12011/SETP2023-1068

Online decision-making model and algorithm for dynamic and stochastic meal takeout routing problem

  • ZHANG Xiaonan1,2, ZHANG Jianxiong1, LI Xiangqian1
Author information +
History +

Abstract

Meal takeout routing problem is characterized by dynamic orders and uncertain preparation time, and it usually needs to be managed online in a "fast response" and "seconds-computation" manner when orders arrive. This paper studies the meal takeout routing problem with dynamic requests and stochastic meal preparation time (MTRP-DRST). We formulate a route-based Markov decision process to minimize delivery delays. We develop an effective online decision-making method for solving it. Specifically, based on offline value approximation iteration algorithm, the impact of future events is captured through the reward-to-go value associated with each action. A novel order postponement strategy and a dynamic time buffer strategy are integrated. To fast and effectively approximate the reward-to-go value, decision time, order's service status, order's time slack and order's time buffer are defined as key features of the reward-to-go value, which is approximated in per-order level. Experiments show that the proposed method can provide fast and effective online decisions, with an average decision time of 0.04 s at a decision epoch. Novel order postponement and dynamic time buffer strategies are effective. The management insights are provided to takeaway routing operations.

Key words

takeout routing / Markov decision process / reinforcement learning / value approximation iteration

Cite this article

Download Citations
ZHANG Xiaonan , ZHANG Jianxiong , LI Xiangqian. Online decision-making model and algorithm for dynamic and stochastic meal takeout routing problem. Systems Engineering - Theory & Practice, 2025, 45(1): 269-289 https://doi.org/10.12011/SETP2023-1068

References

[1] 田丹, 唐加福, 任悦. O2O模式下即时配送服务系统弹性的提升策略优化[J]. 系统工程理论与实践, 2021, 41(2): 310-318. Tian D, Tang J F, Ren Y. Improving operation resilience of instant delivery service in online to offline business model[J]. Systems Engineering—Theory & Practice, 2021, 41(2): 310-318. [1] Liu S, He L, Shen Z J. On-time last-mile delivery: Order assignment with travel-time predictors[J]. Management Science, 2021, 67(7): 4095-4119.
[2] 胡祥培, 王明征, 王子卓, 等. 线上线下融合的新零售模式运营管理研究现状与展望[J]. 系统工程理论与实践, 2020, 40(8): 2023-2036. Hu X P, Wang M Z, Wang Z Z, et al. The overviews on operation management for the new retail mode of online and offline integration[J]. Systems Engineering—Theory & Practice, 2020, 40(8): 2023-2036.
[3] 周鲜成, 周开军, 王莉, 等. 物流配送中的绿色车辆路径模型与求解算法研究综述[J]. 系统工程理论与实践, 2021, 41(1): 213-230. Zhou X C, Zhou K J, Wang L, et al. Review of green vehicle routing model and its algorithm in logistics distribution[J]. Systems Engineering—Theory & Practice, 2021, 41(1): 213-230.
[4] 范厚明, 张轩, 任晓雪, 等. 多中心开放且需求可拆分的VRPSDP问题优化[J]. 系统工程理论与实践, 2021, 41(6): 1521-1534. Fan H M, Zhang X, Ren X X, et al. Optimization of multi-depot open split delivery vehicle routing problem with simultaneous delivery and pick-up[J]. Systems Engineering—Theory & Practice, 2021, 41(6): 1521-1534.
[5] 葛显龙, 温鹏哲, 薛桂琴. 基于需求预测的两级动态配送路径优化研究[J]. 中国管理科学, 2022, 30(8): 210-220. Ge X L, Wen P Z, Xue G Q. Two-echelon dynamic vehicle routing problem with request forecasting[J]. Chinese Journal of Management Science, 2022, 30(8): 210-220.
[6] 王新玉, 赵志明. 动态取送问题研究综述[J]. 系统工程理论与实践, 2021, 41(2): 319-331. Wang X Y, Zhao Z M. Survey of the dynamic pickup and delivery problems[J]. Systems Engineering—Theory & Practice, 2021, 41(2): 319-331.
[7] 陈萍, 李航. 基于时间满意度的外卖配送路径优化问题研究[J]. 中国管理科学, 2016, 24(S1): 170-176. Chen P, Li H. Optimization model and algorithm based on time satisfaction for food delivery[J]. Chinese Journal of Management Science, 2016, 24(S1): 170-176.
[8] 郭昊颖, 熊浩, 任汭杨, 等. 允许取送交叉和中途接单的外卖配送路径优化[J]. 系统工程, 2022, 40(5): 70-81. Guo H Y, Xiong H, Ren R Y, et al. Research on the optimization of takeout delivery route that allows cross picking and delivery and order halfway[J]. Systems Engineering, 2022, 40(5): 70-81.
[9] 靳志宏, 鞠新诚, 郭加佳, 等. O2O模式下外卖骑手的配送路径优化[J]. 大连海事大学学报, 2019, 45(4): 55-64. Jin Z H, Ju X C, Guo J J, et al. Optimization on distribution routes of the takeaway delivery staff under the O2O mode[J]. Journal of Dalian Maritime University, 2019, 45(4): 55-64.
[10] 张涛, 余绰娅, 刘岚, 等. 同时送取货的随机旅行时间车辆路径问题方法[J]. 系统工程理论与实践, 2011, 31(10): 1912-1920. Zhang T, Yu C Y, Liu L, et al. Method for the stochastic traveling time VRPSPD problem[J]. Systems Engineering—Theory & Practice, 2011, 31(10): 1912-1920.
[11] 赵向南, 邢磊, 靳志宏. 考虑不确定行驶时间的双目标外卖配送路径优化[J]. 大连海事大学学报, 2019, 45(4): 66-72. Zhao X N, Xing L, Jin Z H. Bi-objective takeaway distribution route optimization considering uncertain driving time[J]. Journal of Dalian Maritime University, 2019, 45(4): 66-72.
[12] 张力娅, 张锦, 肖斌. 考虑顾客优先级的多目标外卖即时配送路径优化研究[J]. 工业工程与管理, 2021, 26(2): 196-204. Zhang L Y, Zhang J, Xiao B. Multi-objective take-out instant delivery routing optimization considering customer priority[J]. Industrial Engineering and Management, 2021, 26(2): 196-204.
[13] Liu Y C. An optimization-driven dynamic vehicle routing algorithm for on-demand meal delivery using drones[J]. Computers and Operations Research, 2019, 111: 1-20.
[14] 余海燕, 唐婉倩, 吴腾宇. 带硬时间窗的生鲜外卖即时配送路径优化[J]. 系统管理学报, 2021, 30(3): 584-591. Yu H Y, Tang W Q, Wu T Y. Vehicle Routing Problem with hard time windows for instant delivery of fresh takeout orders[J]. Journal of Systems & Management, 2021, 30(3): 584-591.
[15] 李桃迎, 吕晓宁, 李峰, 等. 考虑动态需求的外卖配送路径优化模型及算法[J]. 控制与决策, 2019, 34(2): 406-413. Li T Y, Lu X N, Li F, et al. Routing optimization model and algorithm for takeout distribution with multiple fuzzy variables under dynamics demand[J]. Control and Decision, 2019, 34(2): 406-413.
[16] Steever Z, Karwan M, Murray C. Dynamic courier routing for a food delivery service[J]. Computers and Operations Research, 2019, 107: 173-188.
[17] Reyes D, Erera A, Savelsbergh M, et al. The meal delivery routing problem[J]. Optimization Online, 2018.
[18] Ulmer M W, Thomas B W, Campbell A M, et al. The restaurant meal delivery problem: Dynamic pickup and delivery with deadlines and random ready times[J]. Transportation Science, 2021, 55(1): 75-100.
[19] Ulmer M W, Goodson J C, Mattfeld D C, et al. Offline-online approximate dynamic programming for dynamic vehicle routing with stochastic requests[J]. Transportation Science, 2019, 53(1): 185-202.
[20] Ulmer M W, Soeker N, Mattfeld D C. Value function approximation for dynamic multi-period vehicle routing[J]. European Journal of Operational Research, 2018, 269(3): 883-899.
[21] Van Heeswijk W J A, Mes M R K, Schutten J M J. The delivery dispatching problem with time windows for urban consolidation centers[J]. Transportation Science, 2019, 53(1): 203-221.
[22] 张晓楠, 张建雄. 随机需求车辆路径问题的价值逼近在线决策[J]. 控制理论与应用, 2022, 39(2): 241-254. Zhang X N, Zhang J X. Value-approximation-based online policy for vehicle routing problem with stochastic demand[J]. Control Theory & Applications, 2022, 39(2): 241-254.
[23] Pillac V, Gendreau M, Gueret C, et al. A review of dynamic vehicle routing problems[J]. European Journal of Operational Research, 2013, 225(1): 1-11.
[24] Secomandi N, Margot F. Reoptimization Approaches for the vehicle-routing problem with stochastic demands[J]. Operations Research, 2009, 57(1): 214-230.
[25] Novoa C, Storer R. An approximate dynamic programming approach for the vehicle routing problem with stochastic demands[J]. European Journal of Operational Research, 2009, 196(2): 509-515.
[26] Wang Z. Delivering meals for multiple suppliers: Exclusive or sharing logistics service[J]. Transportation Research Part E: Logistics and Transportation Review, 2018, 118: 496-512.
PDF(1554 KB)

393

Accesses

0

Citation

Detail

Sections
Recommended

/