农村地区卡车与无人机协同配送路径优化

doi:10.3778/j.issn.1002-8331.2204-0226

摘要/Abstract

摘要： 针对农村地区末端配送道路通行条件差、网点覆盖率低等现状及乡村聚落集群分布的特点，提出基于集群的卡车和无人机路径问题。考虑卡车与无人机协同方式、无人机多包裹配送等约束，以最小化综合配送成本为目标建立混合整数规划模型，并提出了一个两阶段混合蚁群算法对卡车路径和无人机路径进行联合优化以实现问题求解：第一阶段设计基于2-opt局部搜索策略的改进自适应蚁群算法求解卡车路径，第二阶段借助就近聚类机制和蚁群算法求解无人机路径，综合两阶段求出卡车和无人机路径的综合方案。通过算例实验验证所建模型的可行性和设计算法的有效性，为实现农村地区末端物流配送降本增效提供决策参考和依据。

关键词: 卡车与无人机协同配送, 车辆路径问题, 蚁群算法, 局部搜索

Abstract: Owing to the current situations of terminal distribution such as poor traffic conditions and low network coverage in rural areas, and the characteristics of cluster distribution in rural settlements, cluster-based truck and drone routing problem is proposed. Considering the cooperative mode between truck and drone as well as multipackage distribution of drone, a mixed integer programming model is established to minimize the comprehensive distribution cost, and a two-stage hybrid ant colony algorithm is proposed to jointly optimize the truck route and drone route. In the first stage, an improved adaptive ant colony algorithm based on 2-opt local search strategy is designed to calculate the truck path. In the second stage, the nearest clustering mechanism and ant colony algorithm are used to calculate the drone path, and the integrated solution of the truck and drone paths is obtained by combining the two stages. Finally, the feasibility of the built model and the effectiveness of the designed algorithm are verified by numerical examples. The proposed approach also provides decision-making reference and basis regarding cost reduction and efficiency increase of terminal logistics distribution in rural areas.

Key words: truck and drone collaborative distribution, vehicle routing problem, ant colony algorithm, local search

蒋丽, 王洪艳, 梁昌勇, 董骏峰. 农村地区卡车与无人机协同配送路径优化[J]. 计算机工程与应用, 2023, 59(14): 306-314.

JIANG Li, WANG Hongyan, LIANG Changyong, DONG Junfeng. Optimization of Truck and Drone Collaborative Distribution Route in Rural Areas[J]. Computer Engineering and Applications, 2023, 59(14): 306-314.

参考文献

[1] 黎红梅，周冲.全面推进乡村振兴背景下农村高效物流体系构建分析[J].理论探讨，2021（3）：139-144.
LI H M，ZHOU C.Analysis on the construction of efficient rural logistics system under the background of comprehensively promoting rural revitalization[J].Theoreti-
cal Investigation，2021（3）：139-144.
[2] 任璇，黄辉，于少伟，等.车辆与无人机组合配送研究综述[J].控制与决策，2021，36（10）：2313-2327.
REN X，HUANG H，YU S W，et al.Review on vehicle-UAV combined delivery problem[J].Control and Decision，2021，36（10）：2313-2327.
[3] 林驿，吕靖，蒋永雷.考虑交通时变特性的城乡快递无人机配送优化研究[J].计算机应用研究，2020，37（10）：2984-2989.
LIN Y，LV J，JIANG Y L.Research on optimization of drone delivery based on urban-rural transportation considering time-varying characteristics of traffic[J].Application Research of Computers，2020，37（10）：2984-2989.
[4] MACRINA G，PUGLIESE L D P，GUERRIERO F，et al.Drone-aided routing：a literature review[J].Transportation Research Part C：Emerging Technologies，2020，120：102762.
[5] 李妍峰，李佳，向婷.需求可拆分的无人机与卡车协同路径优化问题[J].工业工程，2022，25（1）：54-63.
LI Y F，LI J，XIANG T.Split-delivery vehicle routing problem with drone[J].Industrial Engineering Journal，2022，25（1）：54-63.
[6] 周扬，黄晗，刘彦随.中国村庄空间分布规律及其影响因素[J].地理学报，2020，75（10）：2206-2223.
ZHOU Y，HUANG H，LIU Y S.The spatial distribution characteristics and influencing factors of Chinese villages[J].Acta Geographica Sinica，2020，75（10）：2206-2223.
[7] 刘军杰，郄瑞卿，刘大平，等.基于GIS的乡村聚落空间分布特征与优化模式研究——以吉林省农安县为例[J].土壤通报，2020，51（4）：816-823.
LIU J J，QIE R Q，LIU D P，et al.Spatial distribution characteristics and optimization model of rural settlements based on GlS-a case study of Nong’an，Jilin Province[J].Chinese Journal of Soil Science，2020，51（4）：816-823.
[8] MURRAY C C，CHU A G.The flying sidekick traveling salesman problem：optimization of drone-assisted parcel delivery[J].Transportation Research Part C：Emerging Technologies，2015，54：86-109.
[9] AGATZ N，BOUMAN P，SCHMIDT M.Optimization approaches for the traveling salesman problem with drone[J].Transportation Science，2018，52（4）：965-981.
[10] MOSHREF-JAVADI M，LEE S，WINKENBACH M.Design and evaluation of a multi-trip delivery model with truck and drones[J].Transportation Research Part E：Logistics and Transportation Review，2020，136：101887.
[11] SALAMA M，SRINIVAS S.Joint optimization of customer location clustering and drone-based routing for last-mile deliveries[J].Transportation Research Part C：Emerging Technologies，2020，114：620-642.
[12] KIM S，MOON I.Traveling salesman problem with a drone station[J].IEEE Transactions on Systems，Man，and Cybernetics：Systems，2018，49（1）：42-52.
[13] 王新，王征，徐伟.面向多个无人机站点的车辆与无人机联合配送路径问题研究[J].运筹与管理，2021，30（5）：31-37.
WANG X，WANG Z，XU W.Vehicle and drone joint distribution routing problem with multiple drone hubs[J].Operations Research and Management Science，2021，30（5）：31-37.
[14] 胡觉亮，杨航，张田会，等.无人机与卡车协同配送优化研究[J].浙江理工大学学报（社会科学版），2020，44（5）：489-497.
HU J L，YANG H，ZHANG T H，et al.Research on cooperative distribution optimization of UAVs and trucks[J].Journal of Zhejiang Sci-Tech University（Social Sciences Edition），2020，44（5）：489-497.
[15] 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.
[16] GU Q，FAN T，PAN F，et al.A vehicle-UAV operation scheme for instant delivery[J].Computers & Industrial Engineering，2020，149（4）：106809.
[17] 曹英英，陈淮莉.基于集群的卡车与无人机联合配送调度研究[J].计算机工程与应用，2022，58（11）：287-294.
CAO Y Y，CHEN H L.Research on truck and drone joint distribution scheduling based on cluster[J].Computer Engineering and Applications，2022，58（11）：287-294.
[18] 段海滨，王道波，朱家强，等.蚁群算法理论及应用研究的进展[J].控制与决策，2004（12）：1321-1326.
DUAN H B，WANG D B，ZHU J Q，et al.Development on ant colony algorithm theory and its application[J].Control and Decision，2004（12）：1321-1326.
[19] DORIGO M，GAMBARDELLA L M.Ant colony system：a cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computation，1997，1（1）：53-66.
[20] CALVETE H I，GALé C，IRANZO J A.An efficient evolutionary algorithm for the ring star problem[J].European Journal of Operational Research，2013，231（1）：22-33.
[21] 尹晓峰，刘春煌.基于MATLAB的混合型蚁群算法求解旅行商问题[J].铁路计算机应用，2005（9）：4-7.
YIN X F，LIU C H.Hybrid approach based on ant colony system for solving traveling salesman problem[J].Railway Computer Application，2005（9）：4-7.
[22] 王颖，谢剑英.一种自适应蚁群算法及其仿真研究[J].系统仿真学报，2002（1）：31-33.
WANG Y，XIE J Y.An adaptive ant colony optimization algorithm and simulation[J].Journal of System Simulation，2002（1）：31-33.