无人机骑手联合外卖配送路径优化问题研究

doi:10.3778/j.issn.1002-8331.2202-0152

摘要/Abstract

摘要： 外卖配送是外卖业务中的重要环节，而配送成本和准时送达率是决定外卖配送质量的关键因素，因而对外卖配送路径优化问题的研究尤为重要。基于无人机骑手联合外卖配送模式，引入时空距离度量方法，以最小化送餐成本为目标建立了无人机骑手联合外卖配送的路径优化模型，设计了一种两阶段启发式算法进行求解。第一阶段使用结合K-means的遗传算法对顾客聚类，形成骑手初始路径，第二阶段分别使用改进的变邻域搜索算法和A*算法优化骑手路径和无人机送餐航迹。实验结果表明，与传统骑手配送模式相比，考虑时空距离的无人机骑手联合外卖配送模式能减少送餐成本，提高准时送达率。

关键词: 外卖配送, 无人机, 时空距离, 路径优化, 变邻域搜索算法

Abstract: Take-out delivery is an important part of takeout business, and the delivery cost and on-time delivery rate are the key factors to determine the quality of take-out delivery, so the research on the optimization of take-out delivery routing is particularly important. Based on an emerging drones and riders joint take-out delivery mode, a temporal-spatial distance measurement method is introduced to establish a routing optimization model for drone rider joint take-out delivery to minimize the cost of food delivery, and a two-stage heuristic algorithm is designed to solve the problem. In the first stage, the genetic algorithm combined with K-means is used to cluster customers and form the initial path of riders. In the second stage, the improved variable neighborhood search algorithm and A* algorithm are respectively used to optimize the path of riders and the flight path of drone food delivery. Finally, a case is designed and solved. The experimental results show that, compared with the traditional rider delivery mode, the drones and riders delivery mode considering the temporal-spatial distance can reduce the cost of food delivery and improve the on-time delivery rate.

Key words: take-out delivery, drone, temporal-spatial distance, routing optimization, variable neighborhood search

赵强柱, 卢福强, 王雷震, 王素欣. 无人机骑手联合外卖配送路径优化问题研究[J]. 计算机工程与应用, 2022, 58(11): 269-278.

ZHAO Qiangzhu, LU Fuqiang, WANG Leizhen, WANG Suxin. Research on Drones and Riders Joint Take-Out Delivery Routing Problem[J]. Computer Engineering and Applications, 2022, 58(11): 269-278.

参考文献

[1] 沙小卜.高端餐饮外卖配送网络路径优化研究[D].大连：大连海事大学，2017.
SHA X B.Optimization research on upscale take-out distribution network path[D].Dalian：Dalian Maritime University，2017.
[2] COSMI M，NICOSIA G，PACIFICI A.Scheduling for last-mile meal-delivery processes[J].IFAC PapersOnLine，2019，52（13）：35-49.
[3] 王帅，赵来军，胡青蜜.随机旅行时间的外卖O2O配送车辆路径问题[J].物流科技，2017，40（1）：93-101.
WANG S，ZHAO L J，HU Q M.Vehicle routing problem with O2O takeout delivery based on stochastic travel times[J].Logistics SciTech，2017，40（1）：93-101.
[4] 吕慧，郑雪，郭利.外卖“骑手”的安全风险分析及对策建议[J].现代职业安全，2021（10）：72-74.
LV H，ZHENG X，GUO L.Safety risk analysis and counter measures of takeaway “riders”[J].Modern Occupational Safety，2021（10）：72-74.
[5] 龚心怡，苏燕欣，滕明宏，等.当前外卖配送模式中的问题及对策分析[J].中国商论，2019（3）：32-33.
GONG X Y，SU Y X，TENG M H，et al.Analysis of problems and countermeasures in current takeout distribution mode[J].China Business & Trade，2019（3）：32-33.
[6] 搜狐网.饿了么外卖无人机正式投入商用[EB/OL].（2018-05-29）[2021-12-23].https：//www.sohu.com/a/233349014_
116132.html.
Soho.Ele.me food delivery drones have been put into commerical use[EB/OL].（2018-05-29）[2021-12-23].https：//www.sohu.com/a/233349014_116132.html.
[7] 翟劲松，台玉红.基于时间窗约束下的外卖配送路径优[J].物流科技，2018，41（3）：15-18.
ZHAI J S，TAI Y H.Delivery routing optimization based on time window constraint[J].Logistics SciTech，2018，41（3）：15-18.
[8] LIAO W Z，ZHANG L Y，WEI Z Z.Multi-objective green meal delivery routing problem based on a two-stage solution strategy[J].Journal of Cleaner Prodution，2020，258（3）：172-179.
[9] NACCACHE S，JEAN C，LEANDRO C.The multi-pickup and delivery problem with time windows[J].European Journal of Operational Research，2018，269（1）：353-362.
[10] ULMER M W，THOMAS B W，CAMPBELL A M，et al.The restaurant meal delivery problem：dynamic pickup and delivery with deadlines and random ready times[J].Transportation Science，2021，55（1）：75-100.
[11] 陈萍，李航.基于时间满意度的O2O外卖配送路径优化问题研究[J].中国管理科学，2016，24（S1）：170-176.
CHEN P，LI H.Optimization model and algorithm based on time satisfaction for O2O food delivery[J].Chinese Journal of Management Science，2016，24（S1）：170-176.
[12] 李桃迎，吕晓宁，李峰，等.考虑动态需求的外卖配送路径优化模型及算法[J].控制与决策，2019，34（2）：406-413.
LI T Y，LV X N，LI F，et al.Routing optimization model and algorithm for takeout distribution with multiple fuzzy variables under dynamics demand[J].Control and Decsion，2019，34（2）：406-413.
[13] 张力娅，张锦，肖斌.考虑顾客优先级的多目标O2O外卖即时配送路径优化研究[J].工业工程与管理，2021，26（2）：196-204.
ZHANG L Y，ZHANG J，XIAO B.Multi-objective O2O take-out instant delivery routing optimization consiering cutomer priority[J].Industrial Engineering and Management，2021，26（2）：196-204.
[14] QI M Y，LIN W H，LI N，et al.A spatiotemporal partitioning approach for large-scale vehicle routing problems with time windows[J].Transportation Research Part E，2011，48（1）：248-257.
[15] 戚铭尧，张金金，任丽.基于时空聚类的带时间窗车辆路径规划算法[J].计算机科学，2014，41（3）：218-222.
QI M Y，ZHANG J J，REN L.Vehicle routing algorithm based on spatiotemporal clustering[J].Computer Science，2014，41（3）：218-222.