新兴技术(大数据/人工智能/移动互联网等)的发展和本地生活服务O2O(Online to Offline)商业模式兴起,催生了即时配送新兴物流形态,而外卖配送平台线上强履约要求成为即时配送业务痛点之一.考虑了实时外卖订单和动态变化的骑手等因素,将问题建模为带取送约束和时间约束的实时车辆调度优化问题.基于滚动时域机制将连续时间的动态问题划分为一系列离散静态子问题,设计了邻域搜索启发式算法进行求解.最后,基于大连市某外卖平台的订单业务数据对算法进行了验证,与已有文献中的方法相比,算法能有效降低平均配送时间及超时订单数量,在大规模问题场景下求解算法对平台履约影响更大,高效的调度优化算法有利于外卖平台降本增效.
Abstract
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.
关键词
外卖平台/在线订单分配/骑手调度优化
Key words
take-away platform/online order assignment/scheduling optimization of riders
维普
万方数据