《计算机应用》唯一官方网站 ›› 2024, Vol. 44 ›› Issue (10): 3232-3239.DOI: 10.11772/j.issn.1001-9081.2023101432
        
                    
            孙鉴1,2( ), 马宝全1, 吴隹伟1, 杨晓焕1, 武涛1, 陈攀1
), 马宝全1, 吴隹伟1, 杨晓焕1, 武涛1, 陈攀1
                  
        
        
        
        
    
收稿日期:2023-10-23
									
				
											修回日期:2023-12-19
									
				
											接受日期:2023-12-26
									
				
											发布日期:2024-10-15
									
				
											出版日期:2024-10-10
									
				
			通讯作者:
					孙鉴
							作者简介:孙鉴(1982—),男,山东烟台人,讲师,博士,CCF会员,主要研究方向:大数据存储与管理 2014132@nun.edu.cn基金资助:
        
                                                                                                                                                            Jian SUN1,2( ), Baoquan MA1, Zhuiwei WU1, Xiaohuan YANG1, Tao WU1, Pan CHEN1
), Baoquan MA1, Zhuiwei WU1, Xiaohuan YANG1, Tao WU1, Pan CHEN1
			  
			
			
			
                
        
    
Received:2023-10-23
									
				
											Revised:2023-12-19
									
				
											Accepted:2023-12-26
									
				
											Online:2024-10-15
									
				
											Published:2024-10-10
									
			Contact:
					Jian SUN   
							About author:MA Baoquan, born in 1997, M. S. candidate. His research interests include mobile edge computing, big data storage and management.Supported by:摘要:
无人机(UAV)群路径规划和任务分配是UAV群救援应用的核心,然而传统方法分开求解路径规划与任务分配,导致资源分配不均。为了解决上述问题,结合UAV群的物理属性与应用环境因素,改进蚁群算法(ACO),提出联合并行蚁群(JPACO)模型。首先,借助分级信息素增强系数机制更新信息素,以提高JPACO任务分配均衡性和能耗均衡性;其次,设计路径平衡因子和动态概率转移因子优化蚁群模型易陷入局部收敛的情况,从而提高JPACO的全局搜索能力;最后,引入集群并行处理机制,以降低JPACO运算耗时。将JPACO与自适应动态蚁群算法(ADACO)、扫描动态蚁群算法(SMACO)、贪婪策略蚁群算法(GSACO)和交叉蚁群算法(IACO)在公开数据集CVRPLIB上对比最优路径、任务分配均衡、能耗均衡和运算耗时。实验结果表明:与IACO和ADACO相比,JPACO处理小规模运算的最优路径平均值分别降低7.4%和16.3%;处理大规模运算的求解耗时与GSACO、ADACO相比降低8.2%和22.1%。以上结果验证了JPACO在处理小规模运算时能够改善最优路径,处理大规模运算时任务分配均衡、能耗均衡和运算耗时明显优于对比算法。
中图分类号:
孙鉴, 马宝全, 吴隹伟, 杨晓焕, 武涛, 陈攀. 地震场景下无人机群路径规划与任务分配均衡联合优化[J]. 计算机应用, 2024, 44(10): 3232-3239.
Jian SUN, Baoquan MA, Zhuiwei WU, Xiaohuan YANG, Tao WU, Pan CHEN. Joint optimization of UAV swarm path planning and task allocation balance in earthquake scenarios[J]. Journal of Computer Applications, 2024, 44(10): 3232-3239.
| 参数 | 描述 | 值 | 
|---|---|---|
| 无人机加速度 | ||
| 无人机最大速度 | ||
| 空气密度 | ||
| 无人机转子半径 | ||
| 剖面阻力系数 | 0.012 | |
| 无人机叶片角速度 | ||
| 感应功率增量因子 | 0.1 | |
| 无人机重量 | ||
| 转子实度 | 20 | |
| 机身等效板面积 | 0.002 m2 | |
| 机身阻力比 | 0.001 | |
| 悬停能耗 | ||
| 中型无人机能耗上限 | ||
| 中型无人机任务荷载上限 | 220 | |
| 大型无人机能耗上限 | ||
| 大型无人机任务荷载上限 | 600 | 
表1 无人机群相关参数
Tab. 1 UAV swarm related parameters
| 参数 | 描述 | 值 | 
|---|---|---|
| 无人机加速度 | ||
| 无人机最大速度 | ||
| 空气密度 | ||
| 无人机转子半径 | ||
| 剖面阻力系数 | 0.012 | |
| 无人机叶片角速度 | ||
| 感应功率增量因子 | 0.1 | |
| 无人机重量 | ||
| 转子实度 | 20 | |
| 机身等效板面积 | 0.002 m2 | |
| 机身阻力比 | 0.001 | |
| 悬停能耗 | ||
| 中型无人机能耗上限 | ||
| 中型无人机任务荷载上限 | 220 | |
| 大型无人机能耗上限 | ||
| 大型无人机任务荷载上限 | 600 | 
| 规模 | 算例 | 模型 | 求解时间 | 
|---|---|---|---|
| 小规模 | A-n34-k5 | ADACO | 6.12 | 
| SMACO | 6.03 | ||
| GSACO | 6.11 | ||
| IACO | 8.56 | ||
| JPACO | 9.29 | ||
| E-n76-k8 | ADACO | 22.60 | |
| SMACO | 20.95 | ||
| GSACO | 17.71 | ||
| IACO | 21.32 | ||
| JPACO | 32.35 | ||
| 大规模 | X-n125-k30 | ADACO | 60.03 | 
| SMACO | 51.35 | ||
| GSACO | 50.93 | ||
| IACO | 53.54 | ||
| JPACO | 46.75 | 
表2 模型求解时间 (s)
Tab. 2 Solution time of models
| 规模 | 算例 | 模型 | 求解时间 | 
|---|---|---|---|
| 小规模 | A-n34-k5 | ADACO | 6.12 | 
| SMACO | 6.03 | ||
| GSACO | 6.11 | ||
| IACO | 8.56 | ||
| JPACO | 9.29 | ||
| E-n76-k8 | ADACO | 22.60 | |
| SMACO | 20.95 | ||
| GSACO | 17.71 | ||
| IACO | 21.32 | ||
| JPACO | 32.35 | ||
| 大规模 | X-n125-k30 | ADACO | 60.03 | 
| SMACO | 51.35 | ||
| GSACO | 50.93 | ||
| IACO | 53.54 | ||
| JPACO | 46.75 | 
| 规模 | 算例 | 模型 | 路径最优值 | 路径平均值 | 
|---|---|---|---|---|
| 小规模 | A-n36-k5 | ADACO | 951.21 | 983.60 | 
| SMACO | 912.22 | 965.50 | ||
| GSACO | 939.65 | 941.30 | ||
| IACO | 873.28 | 889.32 | ||
| JPACO | 810.30 | 823.20 | ||
| E-n76-k7 | ADACO | 896.32 | 932.61 | |
| SMACO | 892.22 | 921.61 | ||
| GSACO | 819.15 | 829.43 | ||
| IACO | 854.76 | 864.16 | ||
| JPACO | 811.56 | 819.62 | ||
| 大规模 | X-n101-k25 | ADACO | 32 976.93 | 33 662.89 | 
| SMACO | 32 609.48 | 33 231.47 | ||
| GSACO | 31 721.29 | 32 119.35 | ||
| IACO | 32 769.43 | 32 980.68 | ||
| JPACO | 31 490.26 | 31 949.58 | 
表3 最优路径对比
Tab. 3 Optimal path comparison
| 规模 | 算例 | 模型 | 路径最优值 | 路径平均值 | 
|---|---|---|---|---|
| 小规模 | A-n36-k5 | ADACO | 951.21 | 983.60 | 
| SMACO | 912.22 | 965.50 | ||
| GSACO | 939.65 | 941.30 | ||
| IACO | 873.28 | 889.32 | ||
| JPACO | 810.30 | 823.20 | ||
| E-n76-k7 | ADACO | 896.32 | 932.61 | |
| SMACO | 892.22 | 921.61 | ||
| GSACO | 819.15 | 829.43 | ||
| IACO | 854.76 | 864.16 | ||
| JPACO | 811.56 | 819.62 | ||
| 大规模 | X-n101-k25 | ADACO | 32 976.93 | 33 662.89 | 
| SMACO | 32 609.48 | 33 231.47 | ||
| GSACO | 31 721.29 | 32 119.35 | ||
| IACO | 32 769.43 | 32 980.68 | ||
| JPACO | 31 490.26 | 31 949.58 | 
| 算例 | 模型 | Number | ||
|---|---|---|---|---|
| A-n36-k5 | ADACO | 1.10 | 0.30 | 2 | 
| SMACO | 0.97 | 0.20 | 2 | |
| GSACO | 0.84 | 0.34 | 1 | |
| IACO | 1.10 | 0.50 | 2 | |
| JPACO | 0.82 | 0.54 | 1 | |
| E-n76-k7 | ADACO | 1.03 | 0.34 | 1 | 
| SMACO | 0.98 | 0.45 | 3 | |
| GSACO | 0.95 | 0.41 | 2 | |
| IACO | 1.10 | 0.32 | 2 | |
| JPACO | 0.94 | 0.57 | 1 | |
| X-n106-k14 | ADACO | 9.40 | 2.10 | 8 | 
| SMACO | 9.50 | 3.20 | 8 | |
| GSACO | 9.30 | 3.50 | 7 | |
| IACO | 9.40 | 3.40 | 6 | |
| JPACO | 9.10 | 4.50 | 5 | 
表4 能耗对比
Tab. 4 Energy consumption comparison
| 算例 | 模型 | Number | ||
|---|---|---|---|---|
| A-n36-k5 | ADACO | 1.10 | 0.30 | 2 | 
| SMACO | 0.97 | 0.20 | 2 | |
| GSACO | 0.84 | 0.34 | 1 | |
| IACO | 1.10 | 0.50 | 2 | |
| JPACO | 0.82 | 0.54 | 1 | |
| E-n76-k7 | ADACO | 1.03 | 0.34 | 1 | 
| SMACO | 0.98 | 0.45 | 3 | |
| GSACO | 0.95 | 0.41 | 2 | |
| IACO | 1.10 | 0.32 | 2 | |
| JPACO | 0.94 | 0.57 | 1 | |
| X-n106-k14 | ADACO | 9.40 | 2.10 | 8 | 
| SMACO | 9.50 | 3.20 | 8 | |
| GSACO | 9.30 | 3.50 | 7 | |
| IACO | 9.40 | 3.40 | 6 | |
| JPACO | 9.10 | 4.50 | 5 | 
| 算例 | 满载 | 模型 | |||
|---|---|---|---|---|---|
| A-n32-k5 | 100 | ADACO | 98 | 33 | 30.52 | 
| SMACO | 98 | 20 | 31.02 | ||
| GSACO | 99 | 20 | 25.08 | ||
| IACO | 97 | 23 | 27.32 | ||
| JPACO | 91 | 44 | 19.23 | ||
| X-n106-k14 | 600 | ADACO | 598 | 486 | 32.96 | 
| SMACO | 594 | 522 | 23.25 | ||
| GSACO | 589 | 520 | 19.21 | ||
| IACO | 587 | 513 | 24.65 | ||
| JPACO | 579 | 532 | 15.46 | 
表5 任务分配对比
Tab. 5 Task allocation comparison
| 算例 | 满载 | 模型 | |||
|---|---|---|---|---|---|
| A-n32-k5 | 100 | ADACO | 98 | 33 | 30.52 | 
| SMACO | 98 | 20 | 31.02 | ||
| GSACO | 99 | 20 | 25.08 | ||
| IACO | 97 | 23 | 27.32 | ||
| JPACO | 91 | 44 | 19.23 | ||
| X-n106-k14 | 600 | ADACO | 598 | 486 | 32.96 | 
| SMACO | 594 | 522 | 23.25 | ||
| GSACO | 589 | 520 | 19.21 | ||
| IACO | 587 | 513 | 24.65 | ||
| JPACO | 579 | 532 | 15.46 | 
| 1 | SINGHAL G, BANSOD B, MATHEW L. Unmanned aerial vehicle classification, applications and challenges: a review[EB/OL]. [2023-10-18]. . | 
| 2 | BAJRACHARYA R, SHRESTHA R, KIM S, et al. 6G NR-U based wireless infrastructure UAV: standardization, opportunities, challenges and future scopes[J]. IEEE Access, 2022, 10: 30536-30555. | 
| 3 | 张博闻. 无人机航空遥感系统在灾害应急救援中的应用[J]. 中国高新科技, 2022(21):159-160. | 
| ZHANG B W. Application of UAV aerial remote sensing system in disaster emergency rescue[J]. China High and New Technology, 2022(21): 159-160. | |
| 4 | WU X, BAI W, XIE Y, et al. A hybrid algorithm of particle swarm optimization, Metropolis criterion and RTS smoother for path planning of UAVs[J]. Applied Soft Computing, 2018, 73: 735-747. | 
| 5 | 李姝,裘昌利,李晶. 攻防一体化无人机蜂群作战体系研究[C]// 2022年无人系统高峰论坛(USS)论文集. 西安: 空军航空大学, 2022: 7-12. | 
| LI S, QIU C L, LI J. Research on attack-defense integration of UAV swarms[C]// Proceedings of the 2022 Unmanned System Summit Forum (USS). Xi’an: Aviation University of Air Force, 2022: 7-12. | |
| 6 | WEI C, JI Z, CAI B. Particle swarm optimization for cooperative multi-robot task allocation: a multi-objective approach[J]. IEEE Robotics and Automation Letters, 2020, 5(2): 2530-2537. | 
| 7 | VIDAL T. Hybrid genetic search for the CVRP: open-source implementation and SWAP* neighborhood[J]. Computers and Operations Research, 2022, 140: No.105643. | 
| 8 | 石一鹏,刘杰,祖锦源,等. 基于混合整数线性规划模型的SPONGENT S盒紧凑约束分析[J]. 计算机应用, 2023, 43(5):1504-1510. | 
| SHI Y P, LIU J, ZU J Y, et al. Compact constraint analysis of SPONGENT S-box based on mixed integer linear programming model[J]. Journal of Computer Applications, 2023, 43(5): 1504-1510. | |
| 9 | MALVANKAR-MEHTA M S, MEHTA S S. Optimal task allocation in multi-human multi-robot interaction[J]. Optimization Letters, 2015, 9(8): 1787-1803. | 
| 10 | BAYS M J, WETTERGREN T A. Service agent-transport agent task planning incorporating robust scheduling techniques[J]. Robotics and Autonomous Systems, 2017, 89: 15-26. | 
| 11 | DAI W, LU H, XIAO J, et al. Multi-robot dynamic task allocation for exploration and destruction[J]. Journal of Intelligent and Robotic Systems, 2020, 98: 455-479. | 
| 12 | DUAN X, LIU H, TANG H, et al. A novel hybrid auction algorithm for multi-UAVs dynamic task assignment[J]. IEEE Access, 2020, 8: 86207-86222. | 
| 13 | ZHU D, LIU Y, SUB B. Task assignment and path planning of a multi-AUV system based on a Glasius bio-inspired self-organising map algorithm[J]. The Journal of Navigation, 2018, 71(2): 482-496. | 
| 14 | PHUNG M D, QUACH C H, DINH T H, et al. Enhanced discrete particle swarm optimization path planning for UAV vision-based surface inspection[J]. Automation in Construction, 2017, 81: 25-33. | 
| 15 | CHEN J, SUN D. Resource constrained multirobot task allocation based on leader-follower coalition methodology[J]. The International Journal of Robotics Research, 2011, 30(12): 1423-1434. | 
| 16 | 吴虎胜,张凤鸣,吴庐山. 一种新的群体智能算法——狼群算法[J]. 系统工程与电子技术, 2013, 35(11):2430-2438. | 
| WU H S, ZHANG F M, WU L S. New swarm intelligence algorithm — wolf pack algorithm[J]. Systems Engineering and Electronics, 2013, 35(11): 2430-2438. | |
| 17 | DORIGO M, GAMBARDELLA L M. Ant colonies for the travelling salesman problem[J]. Biosystems, 1997, 43(2): 73-81. | 
| 18 | DUAN Y Q, ZHANG Y, ZHANG B, et al. Path planning based on improved multi-objective particle swarm algorithm[C]// Proceedings of the IEEE 5th Information Technology and Mechatronics Engineering Conference. Piscataway: IEEE, 2020: 1005-1009. | 
| 19 | TIAN J, WANG Y, FAN C. Research on target assignment of multiple-UAVs based on improved hybrid genetic algorithm[C]// Proceedings of the IEEE 4th International Conference on Control Science and Systems Engineering. Piscataway: IEEE, 2018: 304-307. | 
| 20 | 夏乐. 基于贪婪策略的蚁群优化算法研究与应用[D]. 赣州:江西理工大学, 2022:19-21. | 
| XIA L. Research and application of ant colony optimization algorithm with greedy strategy[D]. Ganzhou: Jiangxi University of Science and Technology, 2022: 19-21. | |
| 21 | 张航,高岳林. 求解带容量约束车辆路径问题的改进蚁群算法[J]. 宝鸡文理学院学报(自然科学版), 2022, 42(3):18-23, 29. | 
| ZHANG H, GAO Y L. An improved ant colony optimization for capacitated vehicle routing problem[J]. Journal of Baoji University of Arts and Sciences (Natural Science Edition), 2022, 42(3): 18-23, 29. | |
| 22 | 陈颖杰,高茂庭. 基于信息素初始分配和动态更新的蚁群算法[J]. 计算机工程与应用, 2022, 58(2):95-101. | 
| CHEN Y J, GAO M T. Pheromone initialization and dynamic update based ant colony algorithm[J]. Computer Engineering and Applications, 2022, 58(2): 95-101. | |
| 23 | 王艳春,郭永峰,夏颖,等. 基于改进蚁群算法的机器人全局路径规划研究[J]. 电子科技, 2024, 37(5): 88-94. | 
| WANG Y C, GUO Y F, XIA Y, et al. Research on robot global path planning based on improved ant colony algorithm[J]. Electronic Science and Technology, 2024, 37(5): 88-94. | |
| 24 | KAKOOEI M, BALEGHI Y. Fusion of satellite, aircraft, and UAV data for automatic disaster damage assessment[J]. International Journal of Remote Sensing, 2017, 38(8/9/10): 2511-2534. | 
| 25 | LI K, CHEN X, LIU H, et al. Performance analysis of the thermal automatic tracking method based on the model of the UAV dynamic model in a thermal and cubature Kalman filter[J]. Drones, 2023, 7(2): No.102. | 
| 26 | ZHANG Y X, LI K, LIU J Y. Intelligent prediction method for updraft of UAV that is based on LSTM network[J]. IEEE Transactions on Cognitive and Developmental Systems, 2023, 15(2): 464-475. | 
| 27 | EJAZ W, AHMED A, MUSHTAQ A, et al. Energy-efficient task scheduling and physiological assessment in disaster management using UAV-assisted networks[J]. Computer Communications, 2020, 155: 150-157. | 
| 28 | MAH M C, LIM H S, TAN A W C. Secrecy improvement via joint optimization of UAV relay flight path and transmit power[J]. Vehicular Communications, 2020, 23: No.100217. | 
| 29 | SHAH Z, JAVED U, NAEEM M, et al. Mobile Edge Computing (MEC)-enabled UAV placement and computation efficiency maximization in disaster scenario[J]. IEEE Transactions on Vehicular Technology, 2023, 72(10): 13406-13416. | 
| 30 | BEZAS K, TSOUMANIS G, ANGELIS C T, et al. Coverage path planning and point-of-interest detection using autonomous drone swarms[J]. Sensors, 2022, 22(19): No.7551. | 
| 31 | DENG L, YUAN H, HUANG L, et al. Post-earthquake search via an autonomous UAV: hybrid algorithm and 3D path planning[C]// Proceedings of the 14th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery. Piscataway: IEEE, 2018: 1329-1334. | 
| 32 | AIMAIKI F A, SOUFIENE B O. Modifying Hata-Davidson propagation model for remote sensing in complex environments using a multifactional drone[J]. Sensors, 2022, 22(5): No.1786. | 
| 33 | MA Z, GONG H, WANG X. An UAV path planning method in complex mountainous area based on a new improved ant colony algorithm[C]// Proceedings of the 2019 International Conference on Artificial Intelligence and Advanced Manufacturing. Piscataway: IEEE, 2019: 125-129. | 
| 34 | GUO H, ZHOU X, WANG Y, et al. Achieve load balancing in multi-UAV edge computing IoT networks: a dynamic entry and exit mechanism[J]. IEEE Internet of Things Journal, 2022, 9(19): 18725-18736. | 
| 35 | GOUSIOS G. Big data software analytics with Apache Spark[C]// Proceedings of the ACM/IEEE 40th International Conference on Software Engineering: Companion. New York: ACM, 2018: 542-543. | 
| 36 | UCHOA E, PECIN D, PESSOA A, et al. New benchmark instances for the capacitated vehicle routing problem[J]. European Journal of Operational Research, 2017, 257(3): 845-858. | 
| [1] | 田润泽, 周宇龙, 朱洪, 薛岗. 基于局部信息的服务迁移路径选择算法[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2168-2174. | 
| [2] | 马天, 席润韬, 吕佳豪, 曾奕杰, 杨嘉怡, 张杰慧. 基于深度强化学习的移动机器人三维路径规划方法[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2055-2064. | 
| [3] | 李建强, 何舟. 面向多行程取送货车辆路径问题的混合NSGA-Ⅱ[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1187-1194. | 
| [4] | 黄海新, 于广威, 程寿山, 李春明. 基于改进灰狼优化的桥梁检测爬壁机器人全覆盖路径规划[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 966-971. | 
| [5] | 宋紫阳, 李军怀, 王怀军, 苏鑫, 于蕾. 基于路径模仿和SAC强化学习的机械臂路径规划算法[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 439-444. | 
| [6] | 邓辅秦, 官桧锋, 谭朝恩, 付兰慧, 王宏民, 林天麟, 张建民. 基于请求与应答通信机制和局部注意力机制的多机器人强化学习路径规划方法[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 432-438. | 
| [7] | 邓辅秦, 谭朝恩, 黎俊炜, 钟家铭, 付兰慧, 张建民, 王宏民, 李楠楠, 姜炳春, 林天麟. 面向大型仓储环境的基于冲突搜索算法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3854-3860. | 
| [8] | 李永迪, 李彩虹, 张耀玉, 张国胜. 基于改进SAC算法的移动机器人路径规划[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 654-660. | 
| [9] | 黄霖, 符强, 童楠. 基于自适应调整哈里斯鹰优化算法求解机器人路径规划问题[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3840-3847. | 
| [10] | 王龙宝, 栾茵琪, 徐亮, 曾昕, 张帅, 徐淑芳. 基于动态簇粒子群优化的无人机集群路径规划方法[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3816-3823. | 
| [11] | 刘晨, 陈洋, 符浩. 基于值函数迭代的持续监测无人机路径规划[J]. 《计算机应用》唯一官方网站, 2023, 43(10): 3290-3296. | 
| [12] | 范厚明, 牟爽, 岳丽君. 考虑冲突和拥堵的自动导引车调度与路径规划协同优化[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2281-2291. | 
| [13] | 韩舒宁, 徐敏, 董学士, 林青, 沈凡凡. 混合伊藤算法求解多尺度着色旅行商问题[J]. 《计算机应用》唯一官方网站, 2022, 42(3): 695-700. | 
| [14] | 陈昇, 周隽, 胡小兵, 马霁. 基于混合模拟退火算法的机场进场程序优化[J]. 《计算机应用》唯一官方网站, 2022, 42(2): 606-615. | 
| [15] | 代荣荣, 李宏慧, 付学良. 基于差分进化融合蚁群算法的数据中心流量调度机制[J]. 《计算机应用》唯一官方网站, 2022, 42(12): 3863-3869. | 
| 阅读次数 | ||||||
| 全文 |  | |||||
| 摘要 |  | |||||