基于集群的卡车与无人机联合配送调度研究

doi:10.3778/j.issn.1002-8331.2109-0449

摘要/Abstract

摘要： 基于集群提出卡车与无人机联合配送新模式，来解决农村地区送货上门难的问题。考虑无人机载重和续航能力，以总运营成本最小为目标建立带时间窗的混合整数规划模型，并提出两阶段算法，通过改进后的K-means算法求出卡车停靠点，采用遗传模拟退火算法优化卡车与无人机联合配送路线。将其与传统K-means算法加CPLEX结果对比，可证明算法和模型的可行性与有效性。案例分析选取江苏某农村地区来进行末端物流配送的应用研究，结果表明卡车与无人机联合配送模式与纯卡车运输模式相比可有效减少总运营成本。研究成果可为农村地区末端配送中无人机的应用提供新思路和参考价值。

关键词: 卡车与无人机联合配送, 集群, 农村物流, 两阶段算法

Abstract: Based on the cluster, a new model of truck and drone joint distribution is proposed to solve the problem of difficult door-to-door delivery in rural areas. Considering the load and endurance of the drones, a mixed integer programming model with time windows is established to minimize the total operating cost, and a two-stage algorithm is proposed. First, the truck stops are calculated through the improved K-means algorithm, and then genetic simulated annealing algorithm is adopted to optimize the joint distribution route of trucks and drones. Comparing with the traditional K-means algorithm plus CPLEX results, it can prove the feasibility and effectiveness of the algorithm and model. The case study selects a rural area in Jiangsu for the application research of terminal logistics distribution. The results show that the joint delivery model of truck and drone can effectively reduce the total operating cost compared with the pure truck transportation model. The research results can provide new ideas and reference value for the application of drones in terminal distribution in rural areas.

Key words: truck and drone joint delivery, cluster, rural logistics, two-stage algorithm

曹英英, 陈淮莉. 基于集群的卡车与无人机联合配送调度研究[J]. 计算机工程与应用, 2022, 58(11): 287-294.

CAO Yingying, CHEN Huaili. Research on Truck and Drone Joint Distribution Scheduling Based on Cluster[J]. Computer Engineering and Applications, 2022, 58(11): 287-294.

参考文献

[1] 中国产业信息网.2020年中国农村电商发展现状分析：农村网络零售额为1.79万亿元[EB/OL].[2021-02-19].https：//www.chyxx.com/industry/202102/931636.html.
China Industry Information Network.Analysis of the status quo of China’s rural e-commerce development in 2020：rural online retail sales of 1.79 trillion yuan[EB/OL].[2021-02-19].https：//www.chyxx.com/industry/202102/931636.html.
[2] 苗娜娜.我国农村物流末端配送的机遇、挑战及优化[J].农业经济，2020（2）：140-141.
MIAO N N.Opportunities，challenges and optimization of my country’s rural logistics terminal distribution[J].Agricultural Economy，2020（2）：140-141.
[3] SCHNEIDER D.Air traffic control for delivery drones[J].IEEE Spectrum，2017，54（1）：32-33.
[4] 陈明舟.无人机物流配送服务动向[J].物流工程与管理，2020，42（10）：90-92.
CHEN M Z.Trends in logistics delivery services using UAV[J].Logistics Engineering and Management，2020，42（10）：90-92.
[5] HONG I，KUBY M，MURRAY A T.A range-restricted recharging station coverage model for drone delivery service planning[J].Transportation Research，2018，90（5）：198-212.
[6] KIM S，MOON I.Traveling salesman problem with a drone station[J].IEEE Transactions on Systems Man Cybernetics-Systems，2019，49（1）：42-52.
[7] 李绍斌，姜大立，方海洋，等.基于车载模式的战场物资多无人机联合配送任务分配研究[J].军事运筹与系统工程，2020，34（3）：19-25.
LI S B，JIANG D L，FANG H Y，et al.Research on the task allocation of battlefield material multi-UAV joint distribution based on vehicle-mounted mode[J].Military Operations Research and Systems Engineering，2020，34（3）：19-25.
[8] 周爱莲，蒋利，侯夏杰.应急物流中无人机配送线路优化[J].长沙理工大学学报（自然科学版），2020，17（2）：54-60.
ZHOU A L，JIANG L，HOU X J.Optimization of UAV distribution routes in emergency logistics[J].Journal of Changsha University of Science and Technology（Natural Science Edition），2020，17（2）：54-60.
[9] 彭勇，黎元钧.考虑疫情影响的“卡车-无人机”协同配送路径优化[J].中国公路学报，2020，33（11）：1-18.
PENG Y，LI Y J.Optimization of “truck-drone” collaborative distribution route considering the impact of epidemic situation[J].Journal of Highway and Transport，2020，33（11）：1-18.
[10] MURRAY C C，CHU A G.The flying sidekick traveling salesman problem：optimization of drone-assisted parcel delivery[J].Transportation Research Part C，2015，54：86-109.
[11] AGATZ N，BOUMAN P，SCHMIDT M.Optimization approaches for the traveling salesman problem with drone[J].Transportation Science，2018，52（4）：965-981.
[12] HA Q M，DEVILLE Y，PHAM Q D，et al.On the min-cost traveling salesman problem with drone[J].Transportation Research，2018，86：597-621.
[13] FERRANDEZ S M，HARBISON T，WEBER T，et al.Optimization of a truck-drone in tandem delivery network using K-means and genetic algorithm[J].Journal of Industrial Engineering and Management，2016，9（2）：374-388.
[14] WANG X，POIKONEN S，GOLDEN B.The vehicle routing problem with drones：several worst-case results[J].Optimization Letters，2017，11（4）：679-697.
[15] KITJACHAROENCHAI P，MIN B C，LEE S.Two echelon vehicle routing problem with drones in last mile delivery[J].International Journal of Production Economics，2020，225（12）：1-14.
[16] CHANG Y S，LEE H J.Optimal delivery routing with wider drone-delivery areas along a shorter truck-route[J].Expert Systems with Applications，2018，104：307-317.
[17] SALAMA M，SRINIVAS S.Joint optimization of customer location clustering and drone-based routing for last-mile deliveries[J].Transportation Research Part C Journal，2020，114（7）：620-642.