动态随机餐食外卖配送在线决策模型与算法  

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

作　　者：张晓楠 张建雄[1] 李相芊[1] ZHANG Xiaonan;ZHANG Jianxiong;LI Xiangqian(College of Management and Economics,Tianjin University,Tianjin 300072,China;College of Mechanical and Electrical Engineering,Shaanxi University of Science and Technology,Xi'an 710021,China)

机构地区：[1]天津大学管理与经济学部,天津300072 [2]陕西科技大学机电工程学院,西安710021

出　　处：《系统工程理论与实践》2025年第1期269-289,共21页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(72471167);教育部人文社会科学研究一般项目(23XJCZH019);陕西省社会科学项目(2022R002);中国博士后科学基金(2021M702432)。

摘　　要：餐食外卖配送问题具有订单请求动态到来和餐厅备餐时间不确定等特征,且通常需要在订单到来时以“快速响应”和“秒级决策”的方式进行在线管理.本文针对同时考虑动态订单和随机备餐时间的动态随机餐食外卖配送问题,以最小化交付延迟为目标,建立了基于路径的马尔可夫动态决策模型.基于强化学习中的离线价值逼近算法,将未来事件的影响明确刻画为与决策动作相关的未来期望回报值,同时,设计新订单延迟策略和动态时间缓冲策略加以整合,提出一种有效的在线决策方法进行求解.为快速有效地估计未来期望回报值,定义决策时间、订单服务状态、订单时间松弛和订单时间缓冲为回报值的成本结构的关键特征,并将回报值分解到决策后状态下的每个订单层面来近似.数值实验表明:本文方法能做出即时有效的在线决策,单决策点的平均决策时间为0.04 s;设计的新订单延迟策略和动态时间缓冲策略合理有效.所获得的管理启示可为外卖平台配送运营决策提供借鉴.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.

关 键 词：外卖配送优化 马尔可夫决策 强化学习 价值逼近算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]