面向灾情侦察的有优先级多无人机协同调度优化

doi:10.16265/j.cnki.issn1003-3033.2024.11.0732

摘要/Abstract

摘要：

为提高灾情侦察效率,针对灾害应急响应中无人机(UAV)侦察调度问题,提出一种考虑优先级的灾情侦察多UAV协同调度优化模型。首先采用混合整数非线性规划描述模型,开发一种改进的禁忌搜索算法,并通过引入特定的邻域算子和修复算子,提升算法的搜索能力和解的质量;然后设计2组算例验证模型和算法,算例组1源于2021年郑州洪灾的实际情境,算例组2为不同规模的模拟算例。结果表明:模型和算法得到有效验证,敏感性分析能够探讨飞行速度、UAV数量、型号以及续航能力对侦察能力的影响;增加UAV数量和优化型号能显著提高侦察效率;资源有限时,应优先选择侦察能力强的UAV;资源充足时,飞行速度则更为关键。

关键词: 灾情侦察, 无人机(UAV), 调度优化, 禁忌搜索算法, 侦察优先级

Abstract:

To improve the efficiency of disaster reconnaissance, a prioritized multi-UAV cooperative scheduling optimization model was proposed for the UAV reconnaissance scheduling problem in disaster emergency responses. An improved tabu search algorithm was proposed by using a mixed integer nonlinear programming model. Moreover, specific neighborhood operators and repair operators were used to enhance the algorithm's search capability and solution quality. Two cases were designed to validate the model and algorithm performance. The first case was based on the actual scenario of the Zhengzhou flood in 2021, and the second case simulated examples of different scales. The results indicated that the model and algorithm were effectively validated. The effects of flight speed, UAV quantity, model, and endurance on reconnaissance capabilities were investigated through sensitivity analyses. The reconnaissance efficiency can be significantly improved by increasing the number of UAV models and optimizing them. UAVs with strong reconnaissance capabilities should be given priority when resources are limited. However, flight speed is more critical when resources are sufficient.

Key words: disaster reconnaissance, unmanned aerial vehicle (UAV), scheduling optimization, tabu search algorithm, reconnaissance prioritization

中图分类号:

X915.5

龚英, 刘晓聪, 周愉峰, 杨维. 面向灾情侦察的有优先级多无人机协同调度优化[J]. 中国安全科学学报, 2024, 34(11): 202-212.

GONG Ying, LIU Xiaocong, ZHOU Yufeng, YANG Wei. Prioritized multi-UAV collaborative scheduling optimization for disaster reconnaissance[J]. China Safety Science Journal, 2024, 34(11): 202-212.

图/表 15

图1

图2

图3

表1

表2

表3

图4

表4

最优运算结果

UAV数量/架	最优目标值/h	时间/ s	路径
5	0.632 0	29.65	$f 1$ : [4,23,19,20,3,22,21,17,2] $f 2$ : [1,8,9,10,1,6,7,1] $f 3$ : [1,12,16,27,25,24,4] $f 4$ : [4,18,14,15,11,13,2] $f 5$ : [5,28,26,30,29,5]

表4

图5

表5

表6

表7

表8

表9

表10

参考文献 20

[1]	应急管理部. 2022全国自然灾害评估报告[R], 2023.
[2]	冉桂吉. 无人机辅助侦察技术在危险化学品泄漏事故应急指挥中的应用[J]. 中国人民警察大学学报, 2023, 39(6):71-76.
	RAN Guiji. Application of drone-assisted reconnaissance technology in emergency command of hazardous chemical leakage accidents[J]. Journal of China People's Police University, 2023, 39(6):71-76.
[3]	许可, 高宏宇, 雷鸣, 等. 基于改进拍卖算法灾后救援多无人机任务分配[J]. 沈阳理工大学学报, 2024, 43(2):29-37,44.
	XU Ke, GAO Hongyu, LEI Ming, et al. Multi-UAV task allocation for post-disaster rescue based on improved auction algorithm[J]. Journal of Shenyang University of Technology, 2024, 43(2):29-37,44.
[4]	梁佳琪, 宋爱国. 基于北斗导航的突发灾害侦察机器人群组编队设计[J]. 信息技术与信息化, 2014(5):32-33,35.
	LIANG Jiaqi, SONG Aiguo. Design of sudden disaster reconnaissance robot swarm formation based on Beidou navigation[J]. Information Technology and Informatization, 2014(5):32-33,35.
[5]	DA Hu, TIEN Yee. Integrated framework for bridge crack detection and semantic bim model generation using drone-captured imagery and deep learning techniques[M]. Arlington: ASCE Inspire, 2023: 167-175.
[6]	KASHYAP A, GHOSE D, MENON P P, et al. UAV aided dynamic routing of resources in a flood scenario[C]. 2019 International Conference on Unmanned Aircraft Systems (ICUAS). IEEE, 2019: 328-335.
[7]	CHANG K J, TSENG C W, TSENG C M, et al. Application of unmanned aerial vehicle (UAV)-acquired topography for quantifying typhoon-driven landslide volume and its potential topographic impact on rivers in mountainous catchments[J]. Applied Sciences, 2020, 10(17): DOI:10.3390/app10176102.
[8]	YEŞILLER N, HANSON J, WARTMAN J, et al. Disaster reconnaissance framework for sustainable post-disaster materials management[J]. Waste Management, 2023, 169: 392-398. doi: 10.1016/j.wasman.2023.07.010 pmid: 37544208
[9]	JEDDI A B, SHAFIEEZADEH A, NATEGHI R. PDP-CNN: a deep learning model for post-hurricane reconnaissance of electricity infrastructure on resource-constrained embedded systems at the edge[J]. IEEE Transactions on Instrumentation and Measurement, 2023, 72:1-9.
[10]	章可怡, 石咏, 郭海湘, 等. 基于卡车-无人机协同的山区自然灾害应急物资调度优化决策研究[J/OL]. 中国管理科学: 1-14.[2024-03-11].https://doi.org/10.16381/j.cnki.issn1003-207x.2023.1278.
	ZHANG Keyi, SHI Yong, GUO Haixiang, et al. Optimized decision-making research on dispatching emergency supplies for natural disasters in mountainous areas based on truck-unmanned aircraft collaboration[J/OL]. China Management Science: 1-14.[2024-03-11].https://doi.org/10.16381/j.cnki.issn1003-207x.2023.1278.
[11]	李国强. 无人机航测技术在地质灾害应急测绘中的应用[J]. 石材, 2024(3):141-143.
	LI Guoqiang. Application of drone aerial survey technology in geologic disaster emergency mapping[J]. Stone, 2024(3):141-143.
[12]	张海生. 无人机贴近摄影测量技术在贵州山区滑坡监测中的应用[J]. 工程技术研究, 2024, 9(2):208-210.
	ZHANG Haisheng. Application of UAV proximity photogrammetry technology in landslide monitoring in Guizhou mountainous areas[J]. Engineering Technology Research, 2024, 9(2):208-210.
[13]	AVANZATO R, BERITELLI F. A smart UAV-femtocell data sensing system for post-earthquake localization of people[J]. IEEE Access, 2020, 8:30 262-30 270.
[14]	ALSAMHI S H, SHVETSOVA V, KUMAR S, et al. UAV computing-assisted search and rescue mission framework for disaster and harsh environment mitigation[J]. Drones, 2022, 6(7):DOI:10.3390/drones6070154.
[15]	WAN Pengfu, XU Gangyan, CHEN Jiawei, et al. Deep reinforcement learning enabled multi-UAV scheduling for disaster data collection with time-varying value[J]. IEEE Transactions on Intelligent Transportation Systems, 2024, 25(7):6 691-6 702.
[16]	MOSHREF-JAVADI M, HEMMATI A, WINKENBACH M. A truck and drones model for last-mile delivery: a mathematical model and heuristic approach[J]. Applied Mathematical Modelling, 2020, 80: 290-318.
[17]	刘长石, 吴张, 周愉峰, 等. 疫区应急物资供应的卡车-无人机动态协同配送路径优化[J]. 系统科学与数学, 2022, 42(11): 3 027-3 043.
	LIU Changshi, WU Zhang, ZHOU Yufeng, et al. Truck-unmanned aircraft dynamic cooperative distribution path optimization for emergency supplies in epidemic areas[J]. System Science and Mathematics, 2022, 42(11): 3 027-3 043.
[18]	柴获, 何瑞春, 韩伟, 等. 带时间窗的危险货物车辆路径问题2阶段优化[J]. 中国安全科学学报, 2023, 33(12):160-166. doi: 10.16265/j.cnki.issn1003-3033.2023.12.2080
	CHAI Huo, HE Ruichun, HAN Wei, et al. Two-stage optimization for the hazardous materials vehicle routing problem with time windows[J]. China Safety Science Journal, 2023, 33(12):160-166. doi: 10.16265/j.cnki.issn1003-3033.2023.12.2080
[19]	张民波, 钟子逸, 闫瑾, 等. 考虑生物危险源扩散的疫区应急物资调配模型[J]. 中国安全科学学报, 2023, 33(11):206-213. doi: 10.16265/j.cnki.issn1003-3033.2023.11.0434
	ZHANG Minbo, ZHONG Ziyi, YAN Jin, et al. A model for emergency material allocation in epidemic areas considering the spread of biological hazards[J]. China Safety Science Journal, 2023, 33(11):206-213. doi: 10.16265/j.cnki.issn1003-3033.2023.11.0434
[20]	国务院灾害调查组. 河南郑州“7·20”特大暴雨灾害调查报告[R], 2022.

编号	坐标/km
1	(1.7,2.0)
2	(6.4,4.8)
3	(9.0,3.2)
4	(11.2,0.6)
5	(13.6,0.2)

编号	坐标/km	基础侦察时间/min		侦察优先级		被困人数		编号		坐标/km		基础侦察时间/min		侦察优先级	被困人数
6	(0.0,4.0)	2		1		6		19		(10.0,1.0)		0.5		3	7
7	(0.0,3.0)	0.5		1		11		20		(10.0,3.0)		1		2	12
8	(1.6,3.0)	2		2		7		21		(10.0,5.0)		0.5		1	5
9	(2.5,5.6)		0.5		1		12		22		(10.0,6.5)		0.5	1	7
10	(3.2,4.7)		0.5		1		11		23		(12.0,0.0)		2	3	4
11	(3.4,6.0)		2		2		11		24		(12.0,3.0)		2	1	6
12	(3.8,2.8)		0.5		3		6		25		(12.0,4.5)		2	1	5
13	(4.8,3.5)		0.5		1		4		26		(12.5,4.0)		0.5	3	6
14	(6.3,0.0)		1		2		4		27		(12.5,6.5)		2	2	14
15	(6.3,3.0)		2		2		11		28		(14.0,1.2)		0.5	3	4
16	(6.3,4.6)		0.5		2		5		29		(14.6,2.6)		0.5	1	3
17	(6.3,6.0)		2		1		6		30		(14.6,4.3)		1	2	11
18	(10.0,0.0)		0.5		2		11

类型	UAV 型号	调整因子	续航时间/ min	速度/ (km· h^-1)	更换电池时间/min	特点	数量
1	DJI phantom 4 RTK	0.8	30	50	1.0	高侦察能力	2
2	DJI AIR 3	1	45	75	2.0	高飞行能力	2
3	WK 1900 PRO	1.5	60	40	1.5	长续航能力	1

飞行速度变化值/(km·h^-1)	最优目标值/h	飞行速度变化值/(km·h^-1)	最优目标值/h
-10	0.709 4	+10	0.597 4
-5	0.683 0	+15	0.580 5
0	0.632 0	+20	0.562 4
+5	0.613 9

DJI phantom 4		DJI AIR 3		WK 1900 PRO
UAV 数量	最优目标值	UAV 数量	最优目标值	UAV 数量	最优目标值
2	1.343 1	2	1.508 2	2	2.616 4
3	0.872 7	3	0.980 1	3	1.734 9
4	0.669 5	4	0.768 7	4	1.269 5
5	0.614 8	5	0.561 4	5	1.054 0
6	0.468 6	6	0.475 1	6	0.867 2
7	0.407 6	7	0.416 2	7	0.722 0
8	0.364 6	8	0.375 4	8	0.648 6
9	0.336 6	9	0.339 0	9	0.579 4
10	0.311 7	10	0.309 4	10	0.535 9