外卖平台在线订单分配及骑手调度优化  

Online order assignment and rider scheduling optimization for take-away platform

作　　者：王新玉[1,2] 唐加福 赵志明[1] 张琪 Wang Xinyu;Tang Jiafu;Zhao Zhiming;Zhang Qi(School of Management Science and Engineering,Dongbei University of Finance and Economics,Dalian 116025,China;Key Laboratory of Liaoning Province for Data Analytics and Decision-Making Optimization,Dalian 116025,China)

机构地区：[1]东北财经大学管理科学与工程学院,辽宁大连116025 [2]辽宁省大数据管理与优化决策重点实验室,辽宁大连116025

出　　处：《系统工程学报》2024年第5期724-734,共11页Journal of Systems Engineering

基　　金：国家自然科学基金资助项目(71831003,72071034);兴辽英才基金资助项目(XLYC2203029);辽宁省教育厅资助项目(JYTMS20230660);大连市科技人才创新支持计划资助项目(2022RG17).

摘　　要：新兴技术(大数据/人工智能/移动互联网等)的发展和本地生活服务O2O(Online to Offline)商业模式兴起,催生了即时配送新兴物流形态,而外卖配送平台线上强履约要求成为即时配送业务痛点之一.考虑了实时外卖订单和动态变化的骑手等因素,将问题建模为带取送约束和时间约束的实时车辆调度优化问题.基于滚动时域机制将连续时间的动态问题划分为一系列离散静态子问题,设计了邻域搜索启发式算法进行求解.最后,基于大连市某外卖平台的订单业务数据对算法进行了验证,与已有文献中的方法相比,算法能有效降低平均配送时间及超时订单数量,在大规模问题场景下求解算法对平台履约影响更大,高效的调度优化算法有利于外卖平台降本增效.With the development of emerging technologies(such as big data,AI,mobile Internet)and the rise of local-life O2O business model,there has been an increase in instant delivery service.The requirement for strong online on-time delivery performance has become a pain point of take-away platforms.Considering factors such as online orders and dynamic riders,the meal delivery routing problem is modeled as a dynamic real-time scheduling problem with pickup-delivery and time-window constraints.Based on the rolling hori-zon scheme,the dynamic optimization problem is divided into a series of discrete static subproblems,and a heuristic method based on neighborhood search is designed to solve the problem.Finally,the algorithm is verified based on the real-life data of a take-away platform in Dalian.Compared to the published methods,our proposed algorithm effectively reduces the average delivery time of orders and decreases the number of overdue orders.Especially in large-scale problem scenarios,the solution algorithm has a greater impact on the on-time performance.Therefore a high-efficiency algorithm contributes to reducing cost as well as increasing efficiency for the delivery platform.

关 键 词：外卖平台 在线订单分配 骑手调度优化 

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]