【摘要】在山区或岛屿突发灾害期间，无人机递送是一种很有前途的高效方法。基于此，文中研究了一种具有时间窗的多无人机应急物资配送的路径问题以及如何部署无人机的充电站，并提出了一种包括两阶段的联合策略：第一阶段，利用聚类策略对配送区域的需求者进行划分，根据最大飞行距离和无人机交付的最大安全飞行距离这两个关键概念来构建仓库和充电站之间的飞行航段；第二阶段，以无人机总配送距离最小为目标，提出了基于模拟退火结合变邻域搜索算法来解决无人机的路径规划。为了验证所提算法的有效性，基于Solomon数据集设计了一组新的算法并进行分析，然后将该算法与遗传算法、模拟退火算法和变邻域搜索算法进行了比较。实验分析表明，文中所用的算法可以获得明显的改进优势。

　　【关键词】路径优化；无人机；时间约束；充电站布局；应急管理

　　近年来，世界范围内的自然灾害频频发生[1]，对于偏远的山区或者岛屿，在发生自然灾害后，许多被困人员需要食物、水或药品等急救物资。这些急救物资成为救助灾民的关键因素，而不及时的物资配送可能会导致人员伤亡。因此，灾害发生后，能够快速安全地送达应急物资对于减少灾害带来的人员伤亡是非常重要的。

　　目前，无人机（unmanned aerial vehicle,UAV）在应急领域的物资配送、野外搜救、监测等[2]越来越受到学术界和业界的关注，以期能以适中成本按需、安全快速地提供配送服务。考虑到灾后的山区或岛屿的实际情况，救援队会面临较复杂的地形和较恶劣的环境，比如部分灾区交通道路严重破损，在地面车辆和步行救援人员无法将物资送达时，无人机将发挥重要作用。

　　许多学者对无人机灾后应急配送的问题展开了研究。Long等[3]提出了一种动态卡车-无人机协作策略，以实现高效和弹性的城市应急响应；Shi等[4]提出了基于无人机-直升机-卡车协同运输的紧急物料调度优化决策，并开发了两阶段启发式算法来进行求解；Wang等[5]基于无人机紧急配送的拥堵和优先级的问题，提出采用模糊理论来应对优先排队策略下模糊的无人机续航力和需求到达率，并运用多目标优化方法来平衡总成本、系统效率和公平的响应时间；Dukkanci等[6]提出了在不确定性下使用无人机救援的灾后交付问题，并利用情景分解算法进行求解；张祥银等[7]研究了应急场景下的多无人机协同任务分配问题，考虑被困人员所需援助类型的不同，建立了组合优化模型，并提出一种自适应遗传学习粒子群算法进行求解。

　　还有学者考虑利用充电站对无人机进行续航。其中，Ghelichi等[8]为了将医疗物品运送到难以到达的地方，提出了一种新的时隙公式，即对一组无人机的行程进行调度和排序，以服务于多个需求位置，并找到充电站的最优位置，从而使总完成时间最小化；Hong等[9]提出了一个基于无人机配送服务规划的限程充电站覆盖模型，用于优化充电站的位置，以最大化使用给定数量的无人机充电站可以满足的客户需求；Huang、Savkin[10]研究了在需求区域内部署多个充电站以覆盖客户的问题，提出了以三角形模式部署充电站，使用调整程序递归地移除一些覆盖不到或覆盖较少客户的充电站，并重新定位剩余的充电站的建议；Ribeiro等[11根据在灾后场景中使用无人机进行搜索和在救援任务中考虑无人机和充电站的同步使用，开发了一种混合整数线性规划模型，并提出了一种结合遗传算法的构造-调整启发式方法进行求解。

　　从以上相关文献中可以看出，在应急救援中，研究无人机不同的充电策略以及配送路径规划对提高物资配送效率是一个重要的研究课题，但相关方面的研究仍处于起步阶段，多数学者仅考虑到总的配送时间或者最小配送距离，未考虑到实际环境中应急灾区的区域条件，需要对不同区域布局设立无人机充电站，同时根据物资需求紧急程度不同，即时间窗的要求来进行快速应急配送。为此，本文研究了具有时间窗口和充电站的多无人机应急配送问题，即先在考虑充电站布局时使用一种聚类策略，将应急灾区划分为小区域，然后基于上述约束，在不同区域内和区域间优化无人机路径。

　　1问题描述及符号说明

　　1.1问题描述

　　假设无人机应急配送网络由应急配送基地、需求点和充电站组成，如图1所示。多架无人机从配送基地出发，对区域内的需求点进行物资配送，完成物资配送后返回基地。同时，假设（1）基地内的应急物资必须大于需求点的总需求；（2）各点需求必须得到满足，且每个需求点的需求量不超过无人机最大载重；（3）无人机能耗率与距离成线性关系，无人机在送货过程中的速度恒定，充电站充电时间忽略不计；（4）所有无人机都是同质的，具有航程和容量限制；（5）每条路线最多可访问一次;（6）无人机每段行程的总货运需求不得超过其载货能力；（7）每个需求点只能被同一架无人机服务一次；（8）每个需求点的服务时间忽略不计，无人机到达需求点即送完货；（9）从配送基地或者充电站出发时，无人机的荷电状态到达最大值。

　　考虑到发生紧急状况后待救援点信息可以通过遥感等技术手段获得，假设受灾点的地理位置、应急物资需求量以及物资需求时间窗均已知，且节点之间的路径已知。

　［参考文献］

　　［1］Global Disaster Data Platform[EB/OL].2024-03-28.

　　［2］Chowdhury S,EmeloguA,Marufuzzaman M,et al.Drones for disaster response and relief operations:A continuous approximation model[J].International Journal of Production Economics,2017,188:167-184.

　　［3］Long Y,Xu G,Zhao J,et al.Dynamic truck–UAV collaboration and integrated route planning for resilient urban emergency response[J].IEEE Transactions on Engineering Management,2024,71:9826-9838.

　　［4］Shi Y,Yang J,Han Q,et al.Optimal decision-making of post-disaster emergency material scheduling based on helicopter-truck-drone collaboration[J].Omega,2024,127:103104.

　　［5］Wang X,Zhao J,Cheng C,et al.A multi-objective fuzzy facility location problem with congestion and priority for drone-based emergency deliveries[J].Computers&Industrial Engineering,2023,179:109167.

　　［6］Dukkanci O,Koberstein A,Kara B Y.Drones for relief logistics under uncertainty after an earthquake[J].European Journal of Operational Research,2023,310(1):117-132.

　　［7］张祥银，夏爽，张天.基于自适应遗传学习粒子群算法的多无人机协同任务分配[J].控制与决策，2023，38（11）：3103-3111.

　　［8］Ghelichi Z,Gentili M,Mirchandani P B.Logistics for a fleet of drones for medical item delivery:A case study for Louisville,KY[J].Computers&Operations Research,2021,135:105443.

　　［9］Hong I,Kuby M,Murray A T.A range-restricted recharging station coverage model for drone delivery service planning[J].Transportation Research Part C:Emerging Technologies,2018,90:198-212.

　　［10］Huang H,Savkin A V.A method of optimized deployment of charging stations for drone delivery[J].IEEE Transactions on Transportation Electrification,2020,6(2):510-518.

　　［11］Ribeiro R G,Cota L P,Euzebio T A M,et al.Unmanned-aerial-vehicle routing problem with mobile charging stations for assisting search and rescue missions in postdisaster scenarios[J].IEEE Transactions on Systems,Man,and Cybernetics:Systems,2022,52(11):6682-6696.

　　［12］Meng S,Guo X,LI D.The multi-visit drone routing problem for pickup and delivery services[J].Transportation Research Part E:Logistics and Transportation Review,2023,169:102990.

　　［13］Hazama Y,Iima H,Karuno Y,et al.Genetic algorithm for scheduling of parcel delivery by drones[J].Journal of Advanced Mechanical Design,Systems,and Manufacturing,2021,15(6):JAMDSM0069.

　　［14］Es Yurek E.Impact of drone battery recharging policy on overall carbon emissions:The traveling salesman problem with drone[J].Drones,2024,8(3):108.

　　［15］El-adle A M,Ghoniem A,Haouari M.A variable neighborhood search for parcel delivery by vehicle with drone cycles[J].Computers&Operations Research,2023,159:106319.

　　［16］Solomon M M.Algorithms for the vehicle routing and scheduling problems with time window constraints[J].Operations Research,INFORMS,1987,35(2):254–265.

       ［17］杨双鹏，郭秀萍，高娇娇.无接触式“卡车+无人机”联合配送问题研究[J].工业工程与管理，2022，27（01）：184-194.

　　［18］Arafat M Y,Moh S.JRCS:Joint Routing and Charging Strategy for Logistics Drones[J].IEEE Internet of Things Journal,2022,9(21):21751-21764.