考虑取送交叉和多种扰动因素的外卖配送路径优化研究  

Research on Real-time Route Optimization of Takeaway Delivery Considering Pickup and Delivery Cross and Multiple Disturbance Factors

作　　者：熊浩[1] 郭昊颖 鄢慧丽[2] 陈锦怡 XIONG Hao;GUO Haoying;YAN Huili;CHEN Jinyi(Management School,Hainan University,Haikou 570228,China;Tourism School,Hainan University,Haikou 570228,China)

机构地区：[1]海南大学管理学院,海南海口570228 [2]海南大学旅游学院,海南海口570228

出　　处：《湖南大学学报（自然科学版）》2022年第10期92-102,共11页Journal of Hunan University:Natural Sciences

基　　金：国家自然科学基金资助项目(71761009,72061010);海南省哲学社会科学规划课题[HNSK(YB)19-06,HNSK(YB)19-11];海南省自然科学高层次人才项目(722RC646,2019RC037);海南省教育厅重点项目(Hnky2020ZD-6,Hnky2019ZD-10);海南省研究生创新科研课题(Qhys2021-110,Hys2020-47)。

摘　　要：互联网经济下外卖已成为大众化的消费方式.但目前外卖配送路径优化模型和算法中未考虑骑手的目标以及面临的扰动因素,使骑手困在系统里.另外,现有多数研究中将外卖配送路径优化看作静态问题,将取餐节点和送餐节点依据订单号成对插入,进而生成骑手的配送路径.但外卖配送路径优化属于动态实时优化,且取送交叉是外卖配送的基本模式,即骑手可以先去多个节点取餐再去送餐.因此,该文对考虑取送交叉和多种扰动因素的外卖配送路径实时优化问题进行深入研究.首先,在目标函数中增加了骑手空驶成本和骑手等待成本两个目标,建立了外卖配送路径优化模型;其次,针对取送交叉的配送方式和中途接单、临时交通管制、商家出餐时间异常和顾客取餐时间异常四种扰动因素,设计了改进的自适应大邻域搜索算法,实现了高效的骑手配送路径优化;最后,借鉴饿了么平台的比赛数据生成仿真算例,验证了模型和算法在取送交叉和多种扰动因素下的有效性.In the Internet economy,the takeaway has become a popular way of consumption.However,the current takeaway route optimization model and algorithm do not consider the rider’s goal and the disturbance factors they faced,which makes the rider trapped in the system.Most studies optimize the takeaway route as a static problem,generating routes by pairwise insertion of pickup and delivery nodes.However,the takeaway route optimization is dynamic and real-time,and the cross of pickup and delivery is the staple mode of delivery,which means that riders can go to multiple nodes to pick up before delivery.Therefore,this paper studies the delivery route optimization under the cross of pickup and delivery and various interference factors.Firstly,the empty cost of riders and the cost of riders waiting are added to the target function,and an optimization model for takeaway delivery routes is established.Secondly,four interference factors are considered,including mid-way orders,traffic control,the abnormal delivery time of merchants,and the abnormal time of customer pickup.An improved adaptive large neighborhood search algorithm is designed to achieve efficient route optimization.Finally,a simulation example is generated based on the Ele.me platform to verify the effectiveness of the model and algorithm.

关 键 词：外卖配送 车辆路径优化 扰动管理 取送交叉 自适应大邻域搜索算法 

分 类 号：C931[经济管理—管理学] U116.2[交通运输工程]