A Matching Algorithm with Reinforcement Learning and Decoupling Strategy for Order Dispatching in On-Demand Food Delivery  

作　　者：Jingfang Chen Ling Wang Zixiao Pan Yuting Wu Jie Zheng Xuetao Ding 

机构地区：[1]Department of Automation,Tsinghua University,Beijing 100084,China [2]Department of Delivery Technology,Meituan,Beijing 100102,China

出　　处：《Tsinghua Science and Technology》2024年第2期386-399,共14页清华大学学报（自然科学版（英文版）

基　　金：supported in part by the National Natural Science Foundation of China(No.62273193);Tsinghua University-Meituan Joint Institute for Digital Life,and the Research and Development Project of CRSC Research&Design Institute Group Co.,Ltd.

摘　　要：The on-demand food delivery(OFD)service has gained rapid development in the past decades but meanwhile encounters challenges for further improving operation quality.The order dispatching problem is one of the most concerning issues for the OFD platforms,which refer to dynamically dispatching a large number of orders to riders reasonably in very limited decision time.To solve such a challenging combinatorial optimization problem,an effective matching algorithm is proposed by fusing the reinforcement learning technique and the optimization method.First,to deal with the large-scale complexity,a decoupling method is designed by reducing the matching space between new orders and riders.Second,to overcome the high dynamism and satisfy the stringent requirements on decision time,a reinforcement learning based dispatching heuristic is presented.To be specific,a sequence-to-sequence neural network is constructed based on the problem characteristic to generate an order priority sequence.Besides,a training approach is specially designed to improve learning performance.Furthermore,a greedy heuristic is employed to effectively dispatch new orders according to the order priority sequence.On real-world datasets,numerical experiments are conducted to validate the effectiveness of the proposed algorithm.Statistical results show that the proposed algorithm can effectively solve the problem by improving delivery efficiency and maintaining customer satisfaction.

关 键 词：order dispatching on-demand delivery reinforcement learning decoupling strategy sequence-to-sequence neural network 

分 类 号：TP242[自动化与计算机技术—检测技术与自动化装置] TP18[自动化与计算机技术—控制科学与工程]