面向区域搜索的车载多无人机协同任务规划方法

doi:10.12305/j.issn.1001-506X.2026.01.14

摘要/Abstract

摘要：

为更好地完成大面积区域的全覆盖扫描，提出一种多车多无人机协同区域搜索模式。构建考虑卡车行驶路程限制与无人机总量限制的多车多无人机协同区域搜索模型，设计一种融合退火机制、禁忌策略与自适应大邻域搜索的三阶段优化算法（a three stage optimization algorithm integrating annealing mechanism, tabu strategy, and adaptive large neighborhood search, ALNSAWPT），通过区域划分、车辆路径规划、无人机路径规划来求解该问题。在第一阶段，设计基于网格的区域划分方法将大面积区域划分为多个搜索任务。在第二阶段，将搜索任务分配给卡车并生成卡车的路径规划方案。由此，原问题简化为多组单车多无人机协同区域搜索问题。在第三阶段，为每个卡车上的无人机分派搜索任务并生成搜索路径规划方案。实验结果表明， ALNSAWPT明显优于其他5种对比算法，且多车多无人机协同区域搜索模式的效率明显优于单车多无人机区域搜索模式，证明了所提算法的有效性。

关键词: 大面积区域搜索, 多卡车多无人机协同, 三阶段优化算法, 任务规划方法

Abstract:

To better achieve full coverage scanning of large-area, a multi-truck and multi-drone collaborative area search mode is proposed. A multi-truck and multi-drone collaborative area search model is constructed considering the distance limit of truck travel and the total number limit of drones. A three-stage optimization algorithm integrating annealing mechanism, tabu strategy, and adaptive large neighborhood search (ALNSAWPT) is designed to solve the problem through area partitioning, truck path planning, and drone path planning. In the first stage, a grid based area partitioning method is designed to divide a large-area into multiple search tasks. In the second stage, the search task is assigned to the truck and a path planning scheme for the truck is generated. Thus, the original problem is simplified as a collaborative area search problem involving multiple groups of multi-truck and multi-drone. In the third stage, search tasks are assigned to each drone on the truck and generate a search path planning scheme. The experimental results show that ALNSAWPT is significantly better than the other four compared algorithms, and the efficiency of the multi-truck and multi-drone collaborative area search mode is significantly better than that of the single-truck and multi-drone area search mode, proving the effectiveness of the proposed algorithm.

Key words: large-scale area search, collaborative multi-truck and multi-drone, three stage optimization algorithm, task-planning method

中图分类号:

V 19

洪芳宇, 叶青, 张利宁, 伍国华. 面向区域搜索的车载多无人机协同任务规划方法[J]. 系统工程与电子技术, 2026, 48(1): 144-156.

Fangyu HONG, Qing YE, Lining ZHANG, Guohua WU. Vehicle-based multi-UAV cooperative task planning method for area search[J]. Systems Engineering and Electronics, 2026, 48(1): 144-156.

图/表 14

图1

图2

图3

图4

图5

图6

表1

图7

图8

表2

表3

表4

图9

表5

参考文献 33

1	FAN M F, LIU H, WU G H, et al. Multi-UAV reconnaissance mission planning via deep reinforcement learning with simulated annealing[J]. Swarm and Evolutionary Computation, 2025, 93, 101858. doi: 10.1016/j.swevo.2025.101858
2	ZHANG X, ZENG S. The drone-assisted simultaneous pickup and delivery problem with time windows[J]. Computers & Operations Research, 2025, 178, 106996.
3	JIN Z Y, NG K K H, ZHANG C L, et al. A risk-averse distributionally robust optimisation approach for drone-supported relief facility location problem[J]. Transportation Research Part E-Logistics and Transportation Review, 2024, 186, 103538. doi: 10.1016/j.tre.2024.103538
4	HOANG V D, EBEID E S M. Manipulating magnetic field of the magnetic gripper with charging feature for drones on energized power lines[J]. IEEE Trans. on Industrial Electronics, 2024, 71 (11): 14691- 14700. doi: 10.1109/TIE.2024.3363774
5	LIU C F, WICKRAMASINGHE N D, SURAWEERA H A, et al. URLLC-aware proactive UAV placement in internet of vehicles[J]. IEEE Trans. on Intelligent Transportation Systems, 2024, 25 (8): 10446- 10451. doi: 10.1109/TITS.2024.3352971
6	FENG L C, KATUPITIYA J. UAV-based persistent full area coverage with dynamic priorities[J]. Robotics and Autonomous Systems, 2022, 157, 104244. doi: 10.1016/j.robot.2022.104244
7	XIAO Y G, YANG H, LIU H, et al. AAV 3-D path planning based on MOEA/D with adaptive areal weight adjustment[J]. IEEE Trans. on Aerospace and Electronic Systems, 2025, 61 (1): 753- 769. doi: 10.1109/TAES.2024.3449795
8	XU B J, ZHAO K X, LUO Q Z, et al. A GV-drone arc routing approach for urban traffic patrol by coordinating a ground vehicle and multiple drones[J]. Swarm and Evolutionary Computation, 2023, 77, 101246. doi: 10.1016/j.swevo.2023.101246
9	XIA Y S, CHEN C, LIU Y, et al. Two-layer path planning for multi-area coverage by a cooperative ground vehicle and drone system[J]. Expert Systems with Applications, 2023, 217, 119604. doi: 10.1016/j.eswa.2023.119604
10	田双喜, 陈洪辉, 徐彬杰, 等. 车辆支持的多无人机多区域覆盖路径规划算法[J]. 国防科技大学学报, 2024, 46 (6): 227- 234. doi: 10.11887/j.cn.202406025
	TIAN S X, CHEN H H, XU B J. Coverage path planning algorithm for multi-area by truck-supported multi-UAV[J]. Journal of National University of Defense Technology, 2024, 46 (6): 227- 234. doi: 10.11887/j.cn.202406025
11	MURRAY C C, RAJ R. The multiple flying sidekicks traveling salesman problem: parcel delivery with multiple drones[J]. Transportation Research Part C: Emerging Technologies, 2020, 110, 368- 398. doi: 10.1016/j.trc.2019.11.003
12	WU G H, MAO N, LUO Q Z, et al. Collaborative truck-drone routing for contactless parcel delivery during the epidemic[J]. IEEE Trans. on Intelligent Transportation Systems, 2022, 23 (12): 25077- 25091. doi: 10.1109/TITS.2022.3181282
13	HAM A M. Integrated scheduling of m-truck, m-drone, and m-depot constrained by time-window, drop-pickup, and m-visit using constraint programming[J]. Transportation Research Part C: Emerging Technologies, 2018, 91, 1- 14. doi: 10.1016/j.trc.2018.03.025
14	YANPIRAT N, SILVA D F, SMITH A E. Sustainable last mile parcel delivery and return service using drones[J]. Engineering Applications of Artificial Intelligence, 2023, 124, 106631. doi: 10.1016/j.engappai.2023.106631
15	夏雨奇, 黄炎焱, 陈恰. 基于深度Q网络的无人车侦察路径规划[J]. 系统工程与电子技术, 2024, 46 (9): 3070- 3081.
	XIA Y Q, HUANG Y Y, CHEN Q. Path planning for unmanned vehicle reconnaissance based on deep Q-network[J]. Systems Engineering and Electronics, 2024, 46 (9): 3070- 3081.
16	DUKKANCI O, CAMPBELL J F, KARA B Y. Facility location decisions for drone delivery: a literature review[J]. European Journal of Operational Research, 2024, 316 (2): 397- 418. doi: 10.1016/j.ejor.2023.10.036
17	ZHOU H, QIN H, CHENG C, et al. An exact algorithm for the two-echelon vehicle routing problem with drones[J]. Transportation Research Part B-Methodological, 2023, 168, 124- 150. doi: 10.1016/j.trb.2023.01.002
18	LIU Y C. Routing battery-constrained delivery drones in a depot network: a business model and its optimization-simulation assessment[J]. Transportation Research Part C-Emerging Technologies, 2023, 152, 104147. doi: 10.1016/j.trc.2023.104147
19	XIA Y, ZENG W J, ZHANG C R, et al. A branch-and-price-and-cut algorithm for the vehicle routing problem with load-dependent drones[J]. Transportation Research Part B-Methodological, 2023, 171, 80- 110. doi: 10.1016/j.trb.2023.03.003
20	HONG F Y, WU G H, LUO Q Z, et al. Logistics in the sky: a two-phase optimization approach for the drone package pickup and delivery system[J]. IEEE Trans. on Intelligent Transportation Systems, 2023, 24 (9): 9175- 9190. doi: 10.1109/TITS.2023.3271430
21	MENG S S, CHEN Y R, LI D. The multi-visit drone-assisted pickup and delivery problem with time windows[J]. European Journal of Operational Research, 2024, 314 (2): 685- 702. doi: 10.1016/j.ejor.2023.10.021
22	范厚明, 甘兰, 张跃光, 等. 有禁飞区的时间依赖型车辆与无人机协同配送路径优化[J]. 控制理论与应用, 2024, 41 (2): 321- 330. doi: 10.7641/CTA.2022.20249
	FAN H M, GAN L, ZHANG Y G, et al. Time-dependent vehicle routing problem with drones considering no-fly zones[J]. Control Theory & Applications, 2024, 41 (2): 321- 330. doi: 10.7641/CTA.2022.20249
23	MENG S S, GUO X P, LI D, et al. The multi-visit drone routing problem for pickup and delivery services[J]. Transportation Research Part E-Logistics and Transportation Review, 2023, 169, 102990. doi: 10.1016/j.tre.2022.102990
24	薛镇涛, 陈建, 张自超, 等. 基于复杂地块凸划分优化的多无人机覆盖路径规划[J]. 航空学报, 2022, 43 (12)
	XUE Z T, CHEN J, ZHANG Z C, et al. Multi-UAV coverage path planning based on optimization of convex division of complex plots[J]. Acta Aeronautics et Astronautica Sinica, 2022, 43 (12)
25	CHEN G Z, SHEN Y, ZHANG Y X, et al. 2D multi-area coverage path planning using L-SHADE in simulated ocean survey[J]. Applied Soft Computing, 2021, 112, 107754. doi: 10.1016/j.asoc.2021.107754
26	CABREIRA T M, DI-FRANCO C, FERREIRA P R, et al. Energy-aware spiral coverage path planning for UAV photogrammetric applications[J]. IEEE Robotics and Automation Letters, 2018, 3 (4): 3662- 3668. doi: 10.1109/LRA.2018.2854967
27	夏阳升, 石建迈, 陈超, 等. 车机协同多区域覆盖侦察路径规划方法[J]. 指挥与控制学报, 2020, 6 (4): 372- 380.
	XIA Y S, SHI J M, CHEN C, et al. Path planning method for multi-area reconnaissance by cooperated ground vehicle and drone[J]. Journal of Command and Control, 2020, 6 (4): 372- 380.
28	KITJACHAROENCHAI P, MIN B C, LEE S. Two echelon vehicle routing problem with drones in last mile delivery[J]. International Journal of Production Economics, 2020, 225, 107598. doi: 10.1016/j.ijpe.2019.107598
29	ROPERO F, MUÑOZ P, R-MORENO M D. TERRA: a path planning algorithm for cooperative UGV-UAV exploration[J]. Engineering Applications of Artificial Intelligence, 2019, 78, 260- 272. doi: 10.1016/j.engappai.2018.11.008
30	ATENCIA C R, DEL-SER J, CAMACHO D. Weighted strategies to guide a multi-objective evolutionary algorithm for multi-UAV mission planning[J]. Swarm and Evolutionary Computation, 2019, 44, 480- 495. doi: 10.1016/j.swevo.2018.06.005
31	LUO Q Z, WU G H, JI B, et al. Hybrid multi-objective optimization approach with Pareto local search for collaborative truck-drone routing problems considering flexible time windows[J]. IEEE Trans. on Intelligent Transportation Systems, 2022, 23 (8): 13011- 13025. doi: 10.1109/TITS.2021.3119080
32	ROPKE S, PISINGER D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows[J]. Transportation Science, 2006, 40 (4): 455- 472. doi: 10.1287/trsc.1050.0135
33	SOARES L C R, CARVALHO M A M. Biased random-key genetic algorithm for the job sequencing and tool switching problem with non-identical parallel machines[J]. Computers & Operations Research, 2024, 163, 106509.

参数	设定值
无人机续航时间$ {T}_{{\mathrm{max}}} $/min	50
无人机扫描宽度$ DW $/m	100
最大网格搜索面积/km²	4
覆盖重叠率/%	20
无人机飞行速度$ {v}_{D} $/（km/h）	80
卡车行驶速度$ {v}_{G} $/（km/h）	40
机动航程$ {l}_{D} $/km	6
初始温度$ {T}_{s} $/℃	1000
终止温度$ {T}_{e} $/℃	10
降温速度$ {\mathrm{cr }}$/℃	0.97
等温过程最大迭代次数$ {h}_{{\mathrm{max}}} $	10
最大迭代次数$ {I}_{{\mathrm{max}}} $	100000
禁忌表长度$ {L}_{{\mathrm{max}}} $	50

算例	ISGDS	ALNSAWP	ALNSWPT	ALNS	BRKGA	ALNSAWT
算例1	3043	2952	2795	2948	2928	2932
算例2	4199	4003	3780	4056	3951	3977
算例3	5792	5484	5216	5616	5592	5512
算例4	7372	7018	6582	7149	7089	6984
算例5	9626	9279	8586	9378	9407	9126

多车多无人机情形	算例1	算例2	算例3	算例4	算例5
1车4无人机	12568	16909	22148	28506	34908
1车5无人机	11096	15097	19949	24680	31276
1车6无人机	10757	13876	18507	23710	28988
1车7无人机	10143	13107	17404	21556	27538
2车4无人机	6008	8204	11432	14523	18360
2车5无人机	5532	7562	9630	12340	15535
2车6无人机	5062	6504	9564	11205	14632
2车7无人机	4985	6236	8624	10550	13520
2车8无人机	4733	5984	8372	9398	12368
2车9无人机	4580	5831	8219	9245	12215
2车10无人机	4474	5725	8113	9139	12109
3车6无人机	3560	4625	6192	7904	9664
3车7无人机	3385	4369	5806	7180	9182
3车8无人机	3018	4004	5439	6815	8816
3车9无人机	2795	3780	5216	6582	8586
3车10无人机	2668	3654	5090	6552	8460

多车多无人机情形	算例1	算例2	算例3	算例4	算例5	平均提升度
2车4无人机	8.32	6.22	6.70	10.90	9.70	8.37
2车5无人机	8.12	8.14	6.20	6.90	12.30	8.33
2车6无人机	6.90	9.30	9.10	9.50	13.60	9.68
2车7无人机	10.08	9.62	8.90	10.10	11.20	9.98
2车8无人机	10.39	11.69	13.50	7.40	8.90	10.38
2车9无人机	6.94	10.72	11.30	11.80	10.10	10.17
2车10无人机	7.58	10.03	12.80	12.60	7.80	10.16
3车6无人机	8.08	9.76	5.90	8.70	7.60	8.01
3车7无人机	6.55	11.01	9.60	7.80	10.50	9.09
3车8无人机	9.62	10.48	7.80	15.30	14.50	11.54
3车9无人机	7.02	7.56	14.10	14.20	15.40	11.66
3车10无人机	8.59	11.48	10.20	13.50	6.90	10.13
平均提升度	8.17	9.98	9.95	10.71	10.80	9.92

算例	无人机数量	2辆卡车相比1辆卡车效率提升/%	3辆卡车相比2辆卡车效率提升/%
算例1	4	52.20	—
	5	50.14	—
	6	52.94	29.67
	7	50.85	32.10
算例2	4	51.48	—
	5	49.91	—
	6	53.13	28.89
	7	52.42	29.94
算例3	4	48.38	—
	5	51.73	—
	6	48.32	35.26
	7	50.45	32.68
算例4	4	49.05	—
	5	50.00	—
	6	52.74	29.46
	7	51.06	31.94
算例5	4	47.40	—
	5	50.33	—
	6	49.52	33.95
	7	50.90	32.09
均值		50.65	31.60