Multi-stage forest UAV route design based on multi-strategy GA

doi:10.23919/JSEE.2026.000119

Abstract

Abstract:

Forest fires are characterized by their abrupt onset and highly destructive nature, resulting in significant annual property losses. Hence, regular surveillance is imperative for forest fire prevention and mitigation. The fundamental challenge in patrolling is akin to the problem of helicopter route planning. Conventional unmanned aerial vehicle (UAV) path planning commonly entails single-trip missions. Considering the extensive and complex forest environments, we advocate a multi-stage UAV reconnaissance strategy to address the daily inspection route planning conundrum. This approach facilitates UAVs to conduct round-trip flights between designated surveillance points and the base station at diverse time intervals, effectively satisfying the requirements for multi-tiered, hierarchical reconnaissance. Furthermore, we develop an advanced multi-strategy genetic algorithm (MSGA) to optimize the multi-stage reconnaissance model. Experimental outcomes underscore the superior performance of the enhanced MSGA, achieving a reduction of nearly 20% in total flight path length relative to the traditional genetic algorithm. This methodology significantly enhances the efficacy of daily forest patrols.

Key words: unmanned aerial vehicle (UAV), path planning, forest scouting, genetic algorithm, optimization strategy

Wangying XU, Naiming XIE. Multi-stage forest UAV route design based on multi-strategy GA[J]. Journal of Systems Engineering and Electronics, 2026, 37(3): 964-973.

Figures/Tables 19

Fig 1

Table 1

Table 2

Fig 2

Fig 3

Fig 4

Fig 5

Fig 6

Table 3

Fig 7

Table 4

Fig 8

Fig 9

Table 5

Fig 10

Fig 11

Table 6

Fig 12

Table 7

References 32

1	REIS H C, TURK V Detection of forest fire using deep convolutional neural networks with transfer learning approach. Applied Soft Computing, 2023, 143, 110362. doi: 10.1016/j.asoc.2023.110362
2	YANG X B, HUA Z C, ZHANG L, et al Preferred vector machine for forest fire detection. Pattern Recognition, 2023, 143, 109722. doi: 10.1016/j.patcog.2023.109722
3	SANKEY T T, TANGO L, TATUM J, et al Forest fire, thinning, and flood in wildland-urban interface: UAV and lidar-based estimate of natural disaster impacts. Landscape Ecology, 2024, 39 (3): 58. doi: 10.1007/s10980-024-01811-5
4	SUDHAKAR S, VIJAYAKUMAR V, KUMAR C S, et al Unmanned aerial vehicle (UAV) based forest fire detection and monitoring for reducing false alarms in forest-fires. Computer Communications, 2020, 149, 1- 16. doi: 10.1016/j.comcom.2019.10.007
5	WANG H, FENG Y, HUANG X, et al. An AI-based action detection UAV system to improve firefighter safety. Proc. of the International Conference on Human-Computer Interaction, 2023: 632−641.
6	MOSHREF-JAVADI M, HEMMATI A, WINKENBACH M A truck and drones model for last-mile delivery: a mathematical model and heuristic approach. Applied Mathematical Modelling, 2019, 80, 256- 267. doi: 10.1016/j.apm.2019.11.020
7	CHEN R, CHEN J, XU Q Y Joint channel access and power control optimization in large-scale UAV networks: a hierarchical mean field game approach. IEEE Trans. on Vehicular Technology, 2023, 72 (2): 1982- 1996. doi: 10.1109/TVT.2022.3210287
8	GUO Y C, LIU X X, LIU X H, et al FC-RRT*: an improved path planning algorithm for UAV in 3D complex environment. ISPRS International Journal of Geo-Information, 2022, 11, 524- 533.
9	LIU L X, WANG X, YANG X, et al Path planning techniques for mobile robots: review and prospect. Expert Systems with Applications, 2023, 227, 120254. doi: 10.1016/j.eswa.2023.120254
10	ZHANG W, WANG N X, WU W H A hybrid path planning algorithm considering AUV dynamic constraints based on improved A* algorithm and APF algorithm. Ocean Engineering, 2023, 285, 115333. doi: 10.1016/j.oceaneng.2023.115333
11	FAN D K, SHI P. Improvement of Dijkstra’s algorithm and its application in route planning. Proc. of the 7th International Conference on Fuzzy Systems and Knowledge Discovery, 2010: 1901−1904.
12	KHAKZAD N A methodology based on Dijkstra’s algorithm and mathematical programming for optimal evacuation in process plants in the event of major tank fires. Reliability Engineering & System Safety, 2023, 236, 109291. doi: 10.1016/j.ress.2023.109291
13	KNUTH D E A Generalization of Dijkstra’s Algorithm. Information Processing Letters, 1977, 6, 1- 5. doi: 10.1016/0020-0190(77)90002-3
14	PRASAD N L, RAMKUMAR B 3-D deployment and trajectory planning for relay based uav assisted cooperative communication for emergency scenarios using Dijkstra’s algorithm. IEEE Trans. on Vehicular Technology, 2022, 72 (4): 5049- 5063.
15	VADAKKEPAT P, TAN K C, WANG M L. Evolutionary artificial potential fields and their application in real time robot path planning. Proc. of the Congress on Evolutionary Computation, 2000: 256−263.
16	CHANG H, CHEN Y C, ZHANG B C, et al Multi-UAV mobile edge computing and path planning platform based on reinforcement learning. IEEE Trans. on Emerging Topics in Computational Intelligence, 2021, 6 (3): 489- 498.
17	CHEN Y B, LUO G C, MEI Y S, et al UAV path planning using artificial potential field method updated by optimal control theory. International Journal of Systems Science, 2016, 47 (6): 1407- 1420. doi: 10.1080/00207721.2014.929191
18	SHI J M, ZHANG J M, LEI H T, et al Joint mission and route planning of unmanned air vehicles via a learning-based heuristic. Journal of Systems Engineering and Electronics, 2023, 34 (1): 81- 98. doi: 10.23919/JSEE.2023.000005
19	NGUYEN H D, YOSHIHARA I, YAMAMORI K, et al Implementation of an effective hybrid GA for large-scale traveling salesman problems. IEEE Trans. on Systems, Man, and Cybernetics, Part B (Cybernetics), 2007, 37 (1): 92- 99. doi: 10.1109/TSMCB.2006.880136
20	ZHENG J Z, ZHONG J L, CHEN M L, et al A reinforced hybrid genetic algorithm for the traveling salesman problem. Computers & Operations Research, 2023, 157, 106249. doi: 10.1016/j.cor.2023.106249
21	CHOONG S S, WONG L P, LIM C P An artificial bee colony algorithm with a Modified Choice Function for the traveling salesman problem. Swarm and Evolutionary Computation, 2019, 44, 622- 635. doi: 10.1016/j.swevo.2018.08.004
22	SAHIN M Solving TSP by using combinatorial Bees algorithm with nearest neighbor method. Neural Computing and Applications, 2023, 35 (2): 1863- 1879. doi: 10.1007/s00521-022-07816-y
23	LI J X, YANG X R, YANG Y J, et al Cooperative mapping task assignment of heterogeneous multi-UAV using an improved genetic algorithm. Knowledge-Based Systems, 2024, 296, 111830. doi: 10.1016/j.knosys.2024.111830
24	YU X B, JIANG N J, WANG X M, et al A hybrid algorithm based on grey wolf optimizer and differential evolution for UAV path planning. Expert Systems with Applications, 2023, 215, 119327. doi: 10.1016/j.eswa.2022.119327
25	ZOU K L, WANG F, ZHANG F, et al Precision route planning method based on UAV remote sensing and genetic algorithm for weeding machine. Applied Intelligence, 2023, (53): 11203- 11213. doi: 10.1007/s10489-022-03965-8
26	ZHAO Z Y, ZHOU M C, LIU S X Iterated greedy algorithms for flow-shop scheduling problems: a tutorial. IEEE Trans. on Automation Science and Engineering, 2021, 19 (3): 1941- 1959.
27	DIMIC G, SIDIROPOULOS N D On downlink beamforming with greedy user selection: performance analysis and a simple new algorithm. IEEE Trans. on Signal processing, 2005, 53 (10): 3857- 3868. doi: 10.1109/TSP.2005.855401
28	LIU H J, LEE A, LEE W S, et al DAACO: adaptive dynamic quantity of ant ACO algorithm to solve the traveling salesman problem. Complex & Intelligent Systems, 2023, 9 (4): 4317- 4330. doi: 10.1007/s40747-022-00949-6
29	GHALI M, ELGHALI S, AIFAOUI N Genetic algorithm optimization based on manufacturing prediction for an efficient tolerance allocation approach. Journal of Intelligent Manufacturing, 2024, 35 (4): 1649- 1670. doi: 10.1007/s10845-023-02132-1
30	TANG L N, SHAO G F Drone remote sensing for forestry research and practices. Journal of Forestry Research, 2015, 26, 791- 797. doi: 10.1007/s11676-015-0088-y
31	FURCHì A, LIPPI M, CARPIO R F, et al Route optimization in precision agriculture settings: a multi-steiner TSP formulation. IEEE Trans. on Automation Science and Engineering, 2022, 9 (6): 643. doi: 10.1109/tase.2022.3204584
32	LIU J H, LAMPINEN J A fuzzy adaptive differential evolution algorithm. Soft Computing, 2005, 9, 448- 462. doi: 10.1007/s00500-004-0363-x

Parameter	Description
$ {A}_{i} $	The $ i $th low-level inspections
$ {B}_{j} $	The $ j $th high-level inspections
$ \xi $	Number of $ {x}_{i} $ if $ {x}_{i}=1 $
$ \eta $	Number of $ {x}_{i} $ if $ {x}_{i}=0 $
$ \boldsymbol{P} $	Binary vectors for flight groups
$ M $	Number of high-level inspections
$ N $	Number of low-level inspections
$ {d}_{{{A}_{m}},{{A}_{n}}} $	The distance between $ {A}_{m} $ and $ {A}_{n} $
$ {d}_{{{A}_{m}},{{B}_{n}}} $	The distance between $ {A}_{m} $ and $ {B}_{n} $
$ {x}_{m,n,k} $	1, the UAV passes through $ {A}_{m} $ and $ {A}_{n} $ during the $ k $th round of inspection; 0, else
$ {y}_{i,j,k} $	1, the UAV passes through $ {A}_{i} $ and $ {B}_{j} $ during the $ k $th round of inspection; 0, else

Experiment	Number of high-level inspection points	Number of low-level inspection points	Inspection space
Case 1	4	13	10 km×10 km
Case 2	6	30	50 km×50 km
Case 3	10	50	50 km×50 km

Experiment	Algorithm	First flight distance	Second flight distance	Total distance
Case 1	Traditional GA	62.0397	72.5365	134.5762
Case 1	MSGA	67.4135	50.8968	118.3103
Case 2	Traditional GA	258.0911	209.1171	467.2082
Case 2	MSGA	220.5568	190.3639	410.9207
Case 3	Traditional GA	346.8231	480.9245	827.7476
Case 3	MSGA	252.2787	394.7021	646.9808

Algorithm	First flight distance	Second flight distance	Total distance
Traditional GA	362.6364	445.1062	807.7426
Mutation improvement	338.5164	361.1602	699.6766
Multi-crossover	480.9235	329.8601	810.7836
MSGA	252.2787	394.7021	646.9808

Algorithm	First flight distance	Second flight distance	Total distance
P-ALNS	292.53	458.10	750.63
IGA	295.64	404.92	700.56
HGWODE	316.65	447.08	763.73
IMO-GA	364.62	431.11	795.73
GA	346.82	480.92	827.74
MSGA	252.28	394.70	646.98