考虑起降安全的无人机血液运输路径规划

doi:10.3778/j.issn.1002-8331.2211-0296

摘要/Abstract

摘要： 针对使用无人机进行血液运输的路径规划问题，以无人机运输总距离最小为目标，建立多约束无人机血液运输路径规划模型。考虑无人机起降平台数量受限情况下的无人机连续起降安全时间间隔，设计无人机起飞顺序调度策略，以减少无人机完成运输的总耗时，并提出一种基于帝国改革的帝国竞争算法求解该问题。该算法引入正弦扰动策略、增加帝国改革阶段来提高算法的搜索精度，使用与解质量相关的接受准则以保持种群的多样性。利用基准算例和无人机运输血液实例进行验证，结果表明，所提算法可为无人机血液运输任务提供满足各项约束，且没有无人机起降冲突的运输方案；无人机起飞顺序调度策略，可有效减少无人机实际完成任务的总耗时。

关键词: 无人机, 血液运输, 路径规划, 调度策略

Abstract: To solve the problem of path planning in blood transportation by unmanned aerial vehicles (UAVs), a path planning model for blood transportation by UAVs is established with the goal of minimizing total transportation distance of UAVs. Considering the safe time interval of continuous take-off and landing of UAVs under the condition that the number of UAVs take-off and landing platforms is limited, a scheduling strategy of UAVs take-off sequence is designed to reduce the total time consumption for UAVs to complete transportation. And an imperialist competitive algorithm based on the imperialist reform is proposed. A sinusoidal disturbance strategy and an imperialist reform are introduced to improve the search accuracy of the algorithm. The acceptance criteria related to solution quality is designed to increase the diversity of the population. The benchmark example and the UAVs transporting blood example are used for verification. The results show that the proposed algorithm can provide transport tasks for the blood transportation by UAVs that meets various constraints and without UAVs take-off and landing conflicts. In addition, using the scheduling strategy of UAVs take-off sequence can reduce the total time spent by UAVs to actually complete the tasks effectively.

Key words: unmanned aerial vehicles, blood transportation, path planning, scheduling strategy

徐伟华, 张根瑞, 邱龙龙, 赵彩梅, 熊坚. 考虑起降安全的无人机血液运输路径规划[J]. 计算机工程与应用, 2024, 60(6): 339-348.

XU Weihua, ZHANG Genrui, QIU Longlong, ZHAO Caimei, XIONG Jian. Path Planning for Blood Transportation by Unmanned Aerial Vehicles with Safety of Taking-Off and Landing[J]. Computer Engineering and Applications, 2024, 60(6): 339-348.

参考文献

[1] 赵强柱, 卢福强, 王雷震, 等.无人机骑手联合外卖配送路径优化问题研究[J].计算机工程与应用, 2022, 58(11): 269-278.
ZHAO Q Z, LU F Q, WANG L Z, et al. Research on drones and riders joint take-out delivery routing problem[J]. Computer Engineering and Applications, 2022, 58(11): 269-278.
[2] 杨欣, 袁自然, 叶寅, 等.基于无人机高光谱遥感的冬小麦全氮含量反演[J].光谱学与光谱分析, 2022, 42(10): 3269-3274.
YANG X, YUAN Z R, YE Y, et al. Winter wheat total nitrogen content estimation based on UAV hyperspectral remote sensing[J]. Spectroscopy and Spectral Analysis, 2022, 42(10): 3269-3274.
[3] 潘楠, 陈启用, 刘海石, 等.复杂工业品仓储环境无人机盘库任务规划[J].计算机集成制造系统, 2021, 27(10): 2940-2949.
PAN N, CHEN Q Y, LIU H S, et al. Task planning of UAV stocktaking tray in complex industrial storage environment[J]. Computer Integrated Manufacturing Systems, 2021, 27(10): 2940-2949.
[4] ROSSER JR J C, VIGNESH V, TERWILLIGER B A, et al. Surgical and medical applications of drones: a comprehensive review[J]. Journal of the Society of Laparoendoscopic Surgeons, 2018, 22(3): e2018.00018.
[5] AMUKELE T K, SOKOLL L J, PEPPER D, et al. Can unmanned aerial systems (drones) be used for the routine transport of chemistry, hematology, and coagulation laboratory specimens?[J]. PloS One, 2015, 10(7): e0134020.
[6] AMUKELE T, NESS P M, TOBIAN A A R, et al. Drone transportation of blood products[J]. Transfusion, 2017, 57(3): 582-588.
[7] LING G, DRAGHIC N. Aerial drones for blood delivery[J]. Transfusion, 2019, 59(S2): 1608-1611.
[8] NISINGIZWE M P, NDISHIMYE P, SWAIBU K, et al. Effect of unmanned aerial vehicle (drone) delivery on blood product delivery time and wastage in Rwanda: a retrospective, cross-sectional study and time series analysis[J]. The Lancet Global Health, 2022, 10(4): 564-569.
[9] 王慧明, 黄永晖, 范雨哲, 等.无人机血液配送系统规划[J].物流技术, 2019, 38(6): 130-134.
WANG H M, HUANG Y H, FAN Y Z, et al. Planning of blood drone distribution system[J]. Logistics Technology, 2019, 38(6): 130-134.
[10] 李强, 葛芳民, 唐沪强, 等.城市急救用血无人机配送系统的建设与初步应用[J].中华急诊医学杂志, 2021, 30(8): 1026-1032.
LI Q, GE F M, TANG H Q, et, al. A primary study on construction of urban unmanned aerial vehicle emergency blood distribution system[J]. Chinese Journal of Emergency Medicine, 2021, 30(8): 1026-1032.
[11] 郑茵红, 李阿中, 黄娟, 等.无人机在应急血液配送中的初步应用[J].中国输血杂志, 2021, 34(11): 1263-1265.
ZHENG Y H, LI A Z, HUANG J, et al. Preliminary application of drones in emergency blood delivery[J]. Chinese Journal of Blood Transfusion, 2021, 34(11): 1263-1265.
[12] DANTZIG G B, RAMSER J H. The truck dispatching problem[J]. Management Science, 1959, 6(1): 80-91.
[13] WEN T X, ZHANG Z N, WONG K K L. Multi-objective algorithm for blood supply via unmanned aerial vehicles to the wounded in an emergency situation[J]. PloS One, 2016, 11(5): e0155176.
[14] AL-RABIAAH S, HOSNY M, ALMUHAIDEB S. A greedy heuristic based on optimizing battery consumption and routing distance for transporting blood using unmanned aerial vehicles[J]. Electronics, 2022, 11(20): 3399.
[15] OZKAN O. Multi-objective optimization of transporting blood products by routing UAVs: the case of Istanbul[J]. International Transactions in Operational Research, 2023, 30(1): 302-307.
[16] 张九龙, 王晓峰, 芦磊, 等.若干新型智能优化算法对比分析研究[J].计算机科学与探索, 2022, 16(1): 88-105.
ZHANG J L, WANG X F, LU L, et al. Analysis and research of several new intelligent optimization algorithms[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(1): 88-105.
[17] ATASHPAZ-GARGARI E, LUCAS C. Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition[C]//Proceedings of IEEE Congress on Evolutionary Computation. Piscataway, NJ: IEEE Press, 2007: 4661-4667.
[18] 蔡延光, 王世豪, 戚远航, 等.帝国竞争算法求解CVRP[J].计算机应用研究, 2021, 38(3): 782-786.
CAI Y G, WANG S H, QI Y H, et al. Imperialist competitive algorithm for solving CVRP[J]. Application Research of Computers, 2021, 38(3): 782-786.
[19] 徐晨. 基于改进帝国竞争算法的电动汽车物流配送路径规划[D]. 大连: 大连海事大学, 2021.
XU C. Path planning of electric vehicle logistics distribution based on improved imperialist competition algorithm[D]. Dalian: Dalian Maritime University, 2021.
[20] 尹姝呓, 毛剑琳, 李斌.基于改进帝国竞争算法的AUV三维路径规划[J].电子测量技术, 2022, 45(10): 74-81.
YIN S Y, MAO J L, LI B. AUV three-dimensional path planning based on the improved imperial competition algorithm[J]. Electronic Measurement Technology, 2022, 45(10): 74-81.
[21] 徐伟华, 张根瑞, 魏传祥, 等.基于自适应继承策略的帝国竞争算法求解旅行商问题[J].计算机应用研究, 2021, 38(11): 3349-3353.
XU W H, ZHANG G R, WEI C X, et al. Imperialist competitive algorithm based on adaptive inheritance strategy to solve traveling salesman problem[J]. Application Research of Computers, 2021, 38(11): 3349-3353.
[22] AUGERAT P, NADDEF D, BELENGUER J M, et al. Computational results with a branch and cut code for the capacitated vehicle routing problem: INPG-RR-949-M[R]. France: N P, 1995.
[23] 尚正阳, 顾寄南, 王建平.求解带能力约束车辆路径优化问题的改进模拟退火算法[J].计算机集成制造系统, 2021, 27(8): 2260-2269.
SHANG Z Y, GU J N, WANG J P, et al. Improved simulated annealing algorithm for capacitated vehicle routing problem[J]. Computer Integrated Manufacturing Systems, 2021, 27(8): 2260-2269.
[24] GAO Y L, WU H G, WANG W T. A hybrid ant colony optimization with fireworks algorithm to solve capacitated vehicle routing problem[J]. Applied Intelligence, 2023, 53:7326-7342.