Improved simulated annealing algorithm for UAV path planning with uncertain flight time

doi:10.23919/JSEE.2026.000010

Journal of Systems Engineering and Electronics ›› 2026, Vol. 37 ›› Issue (1): 272-286.doi: 10.23919/JSEE.2026.000010

• SYSTEMS ENGINEERING • Previous Articles Next Articles

Improved simulated annealing algorithm for UAV path planning with uncertain flight time

Xiaoduo LI¹^,²(), He LUO¹^,²^,³(), Guoqiang WANG¹^,²^,³^,*(), Youlong YIN⁴()

¹School of Management, Hefei University of Technology, Hefei 230009, China
²Key Laboratory of Process Optimization & Intelligent Decision-making, Ministry of Education, Hefei 230009, China
³Engineering Research Center for Intelligent Management of Aerospace System, Hefei 230009, China
⁴Management Center of UAV Inspection Operation, State Grid Anhui Electric Power Company Limited, Hefei 230061, China

Received:2023-09-05 Online:2026-02-18 Published:2026-03-09
Contact: Guoqiang WANG E-mail:lixiaoduo@mail.hfut.edu.cn;luohe@hfut.edu.cn;gqwang2017@hfut.edu.cn;yinyoulong@mail.hfut.edu.cn
About author:
LI Xiaoduo was born in 1996. She received her B.S. degree from Hefei University of Technology in 2018. She is currently pursuing her Ph.D. degree in the School of Management, Hefei University of Technology. Her research interests include multi-unmanned aerial vehicle path planning and robust optimization. E-mail: lixiaoduo@mail.hfut.edu.cn

LUO He was born in 1982. He received his B.S. and Ph.D. degrees from Hefei University of Technology, in 2004 and 2009, respectively. He is currently a professor in Hefei University of Technology. His research interests include intelligent decision making, multi-agent system and the applications of unmanned aerial vehicle. E-mail: luohe@hfut.edu.cn

WANG Guoqiang was born in 1982. He received his B.S. and M.S. degrees from University of Science and Technology of China, in 2004 and 2007, respectively, and Ph.D. degree from Hefei University of Technology, in 2016. He is currently an associate professor in Hefei University of Technology. His research interest includes management and intelligent decision making of unmanned aerial vehicle formation. E-mail: gqwang2017@hfut.edu.cn

YIN Youlong was born in 1989. He received his B.S. degree from Luoyang Institute of Science and Technology in 2012. He received his M.S. degree from China Three Gorges University, in 2015. His research interest includes power data analysis and task assignment of multi-unmanned aerial vehcile. E-mail: yinyoulong@mail.hfut.edu.cn
Supported by:
This work was supported by the National Natural Science Foundation of China (72571094; 72271076; 71871079).

Abstract

Abstract:

Efficient multiple unmanned aerial vehicles (UAVs) path planning is crucial for improving mission completion efficiency in UAV operations. However, during the actual flight of UAVs, the flight time between nodes is always influenced by external factors, making the original path planning solution ineffective. In this paper, the multi-depot multi-UAV path planning problem with uncertain flight time is modeled as a robust optimization model with a budget uncertainty set. Then, the robust optimization model is transformed into a mixed integer linear programming model by the strong duality theorem, which makes the problem easy to solve. To effectively solve large-scale instances, a simulated annealing algorithm with a robust feasibility check (SA-RFC) is developed. The numerical experiment shows that the SA-RFC can find high-quality solutions within a few seconds. Moreover, the effect of the task location distribution, depot counts, and variations in robustness parameters on the robust optimization solution is analyzed by using Monte Carlo experiments. The results demonstrate that the proposed robust model can effectively reduce the risk of the UAV failing to return to the depot without significantly compromising the profit.

Key words: unmanned aerial vehicle (UAV) path planning, uncertain flight time, robust optimization, simulated annealing

Xiaoduo LI, He LUO, Guoqiang WANG, Youlong YIN. Improved simulated annealing algorithm for UAV path planning with uncertain flight time[J]. Journal of Systems Engineering and Electronics, 2026, 37(1): 272-286.

Figures/Tables 10

Fig 1

Table 1

Table 2

Table 3

Table 4

Table 5

Fig 2

Fig 3

Fig 4

Fig 5

References 36

1	WU Y, LOW K H, PANG B Z, et al Swarm-based 4D path planning for drone operations in urban environments. IEEE Trans. on Vehicular Technology, 2021, 70 (8): 7464- 7479. doi: 10.1109/TVT.2021.3093318
2	ZHANG Z J, ZHENG L N, ZHOU Y X, et al A novel finite-time-gain-adjustment controller design method for UAVs tracking time-varying targets. IEEE Trans. on Intelligent Transportation Systems, 2022, 23 (8): 12531- 12543. doi: 10.1109/TITS.2021.3115153
3	PHAM D A, HAN S H Design of combined neural network and fuzzy logic controller for marine rescue drone trajectory-tracking. Journal of Marine Science and Engineering, 2022, 10 (11): 1716. doi: 10.3390/jmse10111716
4	WENG Y Y, WU R Y, ZHENG Y J Cooperative truck-drone delivery path optimization under urban traffic restriction. Drones, 2023, 7 (1): 59. doi: 10.3390/drones7010059
5	GUAN Q S, ZHANG X Q, XIE M H, et al Large-scale power inspection: a deep reinforcement learning approach. Frontiers in Energy Research, 2023, 10, 1054859. doi: 10.3389/fenrg.2022.1054859
6	PUENTE-CASTRO A, RIVERO D, PAZOS A, et al A review of artificial intelligence applied to path planning in UAV swarms. Neural Computing and Applications, 2022, 34 (1): 153- 170. doi: 10.1007/s00521-021-06569-4
7	ISRAR A, ALI Z A, ALKHAMMASH E H, et al Optimization methods applied to motion planning of unmanned aerial vehicles: a review. Drones, 2022, 6 (5): 126. doi: 10.3390/drones6050126
8	AIT S A, SOUKANE A, MERAIHI Y, et al UAV path planning using optimization approaches: a survey. Archives of Computational Methods in Engineering, 2022, 29 (6): 4233- 4284. doi: 10.1007/s11831-022-09742-7
9	YAHIA H S, MOHAMMED A S Path planning optimization in unmanned aerial vehicles using meta-heuristic algorithms: a systematic review. Environmental Monitoring and Assessment, 2023, 195 (1): 30. doi: 10.1007/s10661-022-10590-y
10	SORBELLI F B, CORO F, DAS S K, et al Energy-constrained delivery of goods with drones under varying wind conditions. IEEE Trans. on Intelligent Transportation Systems, 2021, 22 (9): 6048- 6060. doi: 10.1109/TITS.2020.3044420
11	YANG X, CHEN J Y, DANG Y J, et al Fast depth prediction and obstacle avoidance on a monocular drone using probabilistic convolutional neural network. IEEE Trans. on Intelligent Transportation Systems, 2021, 22 (1): 156- 167. doi: 10.1109/TITS.2019.2955598
12	HWANG M H, CHA H R, JUNG S Y Practical endurance estimation for minimizing energy consumption of multirotor unmanned aerial vehicles. Energies, 2018, 11 (9): 2221. doi: 10.3390/en11092221
13	LU Y C, YANG J, YANG C A humanitarian vehicle routing problem synchronized with drones in time-varying weather conditions. Computers & Industrial Engineering, 2023, 184, 109563. doi: 10.1016/j.cie.2023.109563
14	BELGE E, ALTAN A, HACIOGLU R Metaheuristic optimization-based path planning and tracking of quadcopter for payload hold-release mission. Electronics, 2022, 11 (8): 1208. doi: 10.3390/electronics11081208
15	YE X Y, SONG F J, ZHANG Z Y, et al A review of small UAV navigation system based on multisource sensor fusion. IEEE Sensors Journal, 2023, 23 (17): 18926- 18948. doi: 10.1109/JSEN.2023.3292427
16	YAN X C, FU T T, LIN H M, et al UAV detection and tracking in urban environments using passive sensors: a survey. Applied Sciences, 2023, 13 (20): 11320. doi: 10.3390/app132011320
17	LUO H, LIANG Z Z, ZHU M N, et al Integrated optimization of unmanned aerial vehicle task allocation and path planning under steady wind. Plos One, 2018, 13 (3): e0194690. doi: 10.1371/journal.pone.0194690
18	SOUTO A, ALFAIA R, CARDOSO E, et al UAV path planning optimization strategy: considerations of urban morphology, microclimate, and energy efficiency using Q-learning algorithm. Drones, 2023, 7 (2): 123. doi: 10.3390/drones7020123
19	WANG J H, RAMIREZ A, XU Y Nonlinear direct data-driven control for UAV formation flight system. Journal of Systems Engineering and Electronics, 2023, 34 (6): 1409- 1418. doi: 10.23919/JSEE.2023.000140
20	KIM S, KWAK J H, OH B, et al An optimal routing algorithm for unmanned aerial vehicles. Sensors, 2021, 21 (4): 1219. doi: 10.3390/s21041219
21	LI X H, LI P F, ZHAO Y, et al A hybrid large neighborhood search algorithm for solving the multi depot UAV swarm routing problem. IEEE Access, 2021, 9, 104115- 104126. doi: 10.1109/ACCESS.2021.3098863
22	GUERRIERO F, SURACE R, LOSCRI V, et al A multi-objective approach for unmanned aerial vehicle routing problem with soft time windows constraints. Applied Mathematical Modelling, 2014, 38 (3): 839- 852. doi: 10.1016/j.apm.2013.07.002
23	DORLING K, HEINRICHS J, MESSIER G G, et al Vehicle routing problems for drone delivery. IEEE Trans. on Systems, Man, and Cybernetics: Systems, 2017, 47 (1): 70- 85. doi: 10.1109/TSMC.2016.2582745
24	KIM S J, LIM G J, CHO J Drone flight scheduling under uncertainty on battery duration and air temperature. Computers & Industrial Engineering, 2018, 117, 291- 302. doi: 10.1016/j.cie.2018.02.005
25	SONG Y J, ULMER M W, THOMAS B W, et al Building trust in home services—stochastic team-orienteering with consistency constraints. Transportation Science, 2020, 54 (3): 823- 838. doi: 10.1287/trsc.2019.0927
26	JIN H, THOMAS B W Team orienteering with uncertain rewards and service times with an application to phlebotomist intrahospital routing. Networks, 2019, 73 (4): 453- 465. doi: 10.1002/net.21875
27	VARAKANTHAM P, KUMAR A, LAU H C, et al Risk-sensitive stochastic orienteering problems for trip optimization in urban environments. ACM Transactions on Intelligent Systems and Technology, 2018, 9 (3): 24. doi: 10.1145/3080575
28	BALCIK B, YANIKOGLU I A robust optimization approach for humanitarian needs assessment planning under travel time uncertainty. European Journal of Operational Research, 2020, 282 (1): 40- 57. doi: 10.1016/j.ejor.2019.09.008
29	CHEN L, GENDREAU M, HA M H, et al A robust optimization approach for the road network daily maintenance routing problem with uncertain service time. Transportation Research Part E: Logistics and Transportation Review, 2016, 85, 40- 51. doi: 10.1016/j.tre.2015.11.006
30	ZHANG Y, BALDACCI R, SIM M, et al Routing optimization with time windows under uncertainty. Mathematical Programming, 2019, 175, 263- 305. doi: 10.1007/s10107-018-1243-y
31	GOH J, SIM M Robust optimization made easy with ROME. Operations Research, 2011, 59 (4): 973- 985. doi: 10.1287/opre.1110.0944
32	BERTSIMAS D, SIM M The price of robustness. Operations Research, 2004, 52 (1): 35- 53. doi: 10.1287/opre.1030.0065
33	SOYSTER A L Technical note—convex programming with set-inclusive constraints and applications to inexact linear programming. Operations Research, 1973, 21 (5): 1154- 1157. doi: 10.1287/opre.21.5.1154
34	KIRKPATRICK S, GELATT C D, VECCHI M P Optimization by simulated annealing. Science, 1983, 220 (4598): 671- 680. doi: 10.1126/science.220.4598.671
35	SOLOMON M M Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 1987, 35 (2): 254- 265. doi: 10.1287/opre.35.2.254
36	NADERI B, GHOMI S M T F, AMINNAYERI M A high performing metaheuristic for job shop scheduling with sequence-dependent setup times. Applied Soft Computing, 2010, 10 (3): 703- 710. doi: 10.1016/j.asoc.2009.08.039

Parameter	Value
T0	15
nT	100
λ	0.97
N−nimpr	20

Instance	$ \varphi =0 $				$ \varphi =10\mathrm{\% } $				$ \varphi =50\mathrm{\% } $
Instance	ROME	RC-CPLEX	SA-RFC	Gap	ROME	RC-CPLEX	SA-RFC	Gap	ROME	RC-CPLEX	SA-RFC	Gap
R-2-15-1	59.0006	59.0006	59.0006	0.00	61.3254	61.3254	61.3254	0.00	62.6794	62.6794	62.6794	0.00
R-2-20-1	63.7762	63.7762	63.7762	0.00	75.2014	75.2014	75.2540	0.07	83.5619	83.5619	83.8877	0.39
R-2-25-1	78.1304	78.1304	78.1304	0.00	82.0403	82.0403	82.5817	0.66	88.2933	−	89.7324	1.63
R-2-30-1	83.0857	83.0857	83.0857	0.00	85.3192	−	86.3515	1.21	−	−	90.1031	−
R-2-35-1	−	−	86.2970	−	−	−	90.3183	−	−	−	96.4907	−
R-2-40-1	−	−	92.8795	−	−	−	96.3261	−	−	−	103.2248	−
R-2-50-1	−	−	104.1970	−	−	−	110.9828	−	−	−	121.2883	−
R-3-15-1	59.7820	59.7820	59.7820	0.00	63.1939	63.1939	63.1939	0.00	65.3982	65.3982	65.3982	0.00
R-3-20-1	67.9876	67.9876	68.0419	0.08	78.8762	78.8762	79.1207	0.31	82.8753	82.8753	85.2538	2.87
R-3-25-1	80.8760	80.8760	81.1590	0.35	86.2934	−	87.9847	1.96	−	−	89.2935	−
R-3-30-1	−	−	85.1085	−	−	−	90.1870	−	−	−	91.5738	−
R-3-35-1	−	−	88.6029	−	−	−	96.3459	−	−	−	99.9167	−
R-3-40-1	−	−	93.7814	−	−	−	101.1472	−	−	−	104.2594	−
R-3-50-1	−	−	104.8870	−	−	−	111.6053	−	−	−	122.8891	−
R-4-15-1	58.3974	58.3974	58.3974	0.00	62.0345	62.0345	62.0345	0.00	63.0953	63.0953	63.0953	0.00
R-4-20-1	62.7345	62.7345	62.7784	0.07	71.0433	71.0433	72.3413	0.88	83.3033	83.3033	85.8190	3.02
R-4-25-1	73.2349	−	73.6450	0.56	77.8723	−	79.6400	2.27	−	−	90.9934	−
R-4-30-1	−	−	85.2098	−	−	−	85.8093	−	−	−	90.9154	−
R-4-35-1	−	−	83.3944	−	−	−	97.0092	−	−	−	104.5692	−
R-4-40-1	−	−	94.7430	−	−	−	103.4823	−	−	−	116.3126	−
R-4-50-1	−	−	105.424	−	−	−	112.0536	−	−	−	123.8419	−

Instance	$ \varphi =0 $				$ \varphi =10\mathrm{\% } $				$ \varphi =50\mathrm{\% } $
Instance	ROME	RC-CPLEX	SA-RFC	Gap	ROME	RC-CPLEX	SA-RFC	Gap	ROME	RC-CPLEX	SA-RFC	Gap
R-2-15-1	316.85	512.85	12.30	96.11	1037.45	1012.71	12.69	98.74	2237.49	2512.85	13.16	99.41
R-2-20-1	1009.36	1413.99	15.49	98.46	2436.63	2713.06	14.84	99.39	2936.76	3213.99	15.87	99.45
R-2-25-1	2847.09	2583.59	18.72	99.27	2988.40	3457.82	18.99	99.36	3588.92	−	19.83	99.44
R-2-30-1	3418.51	3571.39	19.21	99.43	3592.05	−	18.97	99.47	−	−	20.42	−
R-2-35-1	−	−	19.64	−	−	−	19.30	−	−	−	21.45	−
R-2-40-1	−	−	20.37	−	−	−	21.03	−	−	−	23.78	−
R-2-50-1	−	−	22.94	−	−	−	23.98	−	−	−	25.83	−
R-3-15-1	680.19	985.05	12.89	98.10	1398.52	1400.83	12.99	99.07	2698.03	2990.97	14.32	99.46
R-3-20-1	2398.75	2723.87	16.94	99.29	2904.09	3122.31	15.21	99.47	3200.32	3423.98	16.35	99.48
R-3-25-1	3390.87	3473.84	19.73	99.41	3297.16	−	18.72	99.43	−	−	22.98	−
R-3-30-1	−	−	20.42	−	−	−	20.20	−	−	−	23.28	−
R-3-35-1	−	−	20.60	−	−	−	21.99	−	−	−	25.14	−
R-3-40-1	−	−	21.12	−	−	−	22.23	−	−	−	25.73	−
R-3-50-1	−	−	23.64	−	−	−	25.57	−	−	−	28.36	−
R-4-15-1	873.77	1083.21	12.43	98.57	1593.53	1998.52	13.97	99.12	2934.97	3098.94	15.34	99.47
R-4-20-1	2885.83	3286.11	17.72	99.38	3015.83	3209.88	16.33	99.45	3509.93	3598.23	16.98	99.51
R-4-25-1	3499.57	−	20.33	99.41	3509.03	−	18.93	99.46	−	−	23.54	−
R-4-30-1	−	−	20.86	−	−	−	21.94	−	−	−	25.67	−
R-4-35-1	−	−	21.70	−	−	−	22.42	−	−	−	27.55	−
R-4-40-1	−	−	22.42	−	−	−	24.96	−	−	−	28.19	−
R-4-50-1	−	−	24.81	−	−	−	26.80	−	−	−	30.49	−

Location distribution	Instance	ε=0.0			ε=0.2			ε=0.4			ε=0.6
Location distribution	Instance	PoR/%	Risk/%	K	PoR/%	Risk/%	K	PoR/%	Risk/%	K	PoR/%	Risk/%	K
C	C-2-50-1	−	57.24	3	9.23	3.83	4	12.91	0	5.5	13.24	0	7
	C-2-50-2	−	38.53	3	7.35	2.11	4.2	8.91	0	4	10.91	0	4.1
	C-2-50-3	−	36.94	3	6.37	3.36	3.7	8.32	0	4	9.02	0	4
R	R-2-50-1	−	100	4	18.4	37.76	6	24.9	2.12	7	29.9	0	7.8
	R-2-50-2	−	100	4	11.86	11.07	6.2	11.49	0.5	6.4	23.06	0	7
	R-2-50-3	−	100	4	4.7	21.84	4.9	13.13	0.37	5.6	16.1	0	6.4
RC	RC-2-50-1	−	99.99	5	12.34	33.8	6	16.37	1.1	6.9	18.74	0	8.5
	RC-2-50-2	−	100	4	8.79	10.47	4.8	9.26	0.48	5.1	10.25	0	5
	RC-2-50-3	−	97.28	4	10.58	18.96	4.3	10.98	0.03	4.4	12.44	0	4.5

Numbers of depots	Instance	ε=0.0			ε=0.2			ε=0.4			ε=0.6
Numbers of depots	Instance	PoR/%	Risk/%	K	PoR/%	Risk/%	K	PoR/%	Risk/%	K	PoR/%	Risk/%	K
2	R-2-50-1	—	100	4	18.4	37.76	6	24.9	2.12	7	29.9	0	7.8
	R-2-50-2	—	100	4	11.86	11.07	6.2	11.49	0.5	6.4	23.06	0	7
	R-2-50-3	—	100	4	4.7	21.84	4.9	13.13	0.37	5.6	16.1	0	6.4
3	R-3-50-1	—	97.83	5	6.4	10.39	5.7	9.39	0.14	6.4	18.58	0	7.1
	R-3-50-2	—	99.99	4	10.34	5.22	5.8	8.9	0.01	6.2	12.44	0	6.6
	R-3-50-3	—	100	5	4.63	9.72	5.5	8.45	0	5.9	9.7	0	6
4	R-4-50-1	—	95.98	5	5.5	2.3	5.8	7.57	0.62	6.6	8.17	0	6.8
	R-4-50-2	—	85.17	5	5.06	1.77	5.7	5.59	0	6	6.22	0	6.1
	R-4-50-3	—	91.08	5	3.28	0.65	5.5	6.63	0	5.9	7.93	0	6.3

Improved simulated annealing algorithm for UAV path planning with uncertain flight time

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 10

References 36

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	Haiquan SUN, Zhilong WANG, Xiaoxuan HU, Wei XIA. Hybrid genetic simulated annealing algorithm for agile Earth observation satellite scheduling considering cloud cover distribution [J]. Journal of Systems Engineering and Electronics, 2025, 36(6): 1595-1612.
[2]	Zeyu ZHOU, Yuhui WANG, Qingxian WU. Integrated fire/flight control of armed helicopters based on C-BFGS and distributionally robust optimization [J]. Journal of Systems Engineering and Electronics, 2024, 35(6): 1604-1620.
[3]	Bing WANG, Pengfei ZHANG, Yufeng HE, Xiaozhi WANG, Xianxia ZHANG. Scenario-oriented hybrid particle swarm optimization algorithm for robust economic dispatch of power system with wind power [J]. Journal of Systems Engineering and Electronics, 2022, 33(5): 1143-1150.
[4]	Ruiyang LI, Ming HE, Hongyue HE, Zhixue WANG, Cheng YANG. A branch and price algorithm for the robust WSOS scheduling problem [J]. Journal of Systems Engineering and Electronics, 2021, 32(3): 658-667.
[5]	Fan YUE, Shiji SONG, Peng JIA, Guangping WU, Han ZHAO. Robust single machine scheduling problem with uncertain job due dates for industrial mass production [J]. Journal of Systems Engineering and Electronics, 2020, 31(2): 350-358.
[6]	Chong Wang, Jinhui Tang, Xiaohang Cheng, Yingchen Liu, and Changchun Wang. Distributed cooperative task planning algorithm for multiple satellites in delayed communication environment [J]. Systems Engineering and Electronics, 2016, 27(3): 619-633.
[7]	Xiaolong Xu, Lingling Cao, and Xinheng Wang. Resource pre-allocation algorithms for low-energy task scheduling of cloud computing [J]. Journal of Systems Engineering and Electronics, 2016, 27(2): 457-469.
[8]	Xionghou Liu, Chao Sun, Yixin Yang, Jie Zhuo, and Yina Han. Low complexity MIMO sonar imaging using a virtual sparse linear array [J]. Journal of Systems Engineering and Electronics, 2016, 27(2): 370-378.
[9]	Weidong Jiang, Haowen Chen, and Xiang Li. Antenna geometry strategy with prior information for direction-finding MIMO radars [J]. Systems Engineering and Electronics, 2015, 26(3): 468-475.
[10]	Yifang Yang and Yuping Wang. Simulated annealing spectral clustering algorithm for image segmentation [J]. Journal of Systems Engineering and Electronics, 2014, 25(3): 514-522.
[11]	Jing Qiu, Xiaodong Tan, Guanjun Liu, and Kehong L¨u. Test selection and optimization for PHM based on failure evolution mechanism model [J]. Journal of Systems Engineering and Electronics, 2013, 24(5): 780-792.
[12]	Wenwu Chen, Zhengyu Cai, Rushan Chen, and Zhao Zhao. Optimizing polyphase sequences for orthogonal netted radar systems [J]. Journal of Systems Engineering and Electronics, 2012, 23(4): 529-535.
[13]	Tianran Zhou, Huagang Xiong, and Zhen Zhang. Hierarchical resource allocation for integrated modular avionics systems [J]. Journal of Systems Engineering and Electronics, 2011, 22(5): 780-787.
[14]	Jun Wang, Xiaoguang Gao, and Yongwen Zhu. Solving algorithm for TA optimization model based on ACO-SA [J]. Journal of Systems Engineering and Electronics, 2011, 22(4): 628-639.
[15]	Ke Wang, and Fajie Wei. Robust data envelopment analysis based MCDM with the consideration of uncertain data [J]. Journal of Systems Engineering and Electronics, 2010, 21(6): 981-989.