Hybrid genetic simulated annealing algorithm for agile Earth observation satellite scheduling considering cloud cover distribution

doi:10.23919/JSEE.2025.000177

Journal of Systems Engineering and Electronics ›› 2025, Vol. 36 ›› Issue (6): 1595-1612.doi: 10.23919/JSEE.2025.000177

• SYSTEMS ENGINEERING • Previous Articles

Hybrid genetic simulated annealing algorithm for agile Earth observation satellite scheduling considering cloud cover distribution

Haiquan SUN¹^,²(), Zhilong WANG¹^,²(), Xiaoxuan HU¹^,²(), Wei XIA¹^,²^,*()

¹ School of Management, Hefei University of Technology, Hefei 230009, China
² Key Laboratory of Process Optimization and Intelligent Decision-making, Ministry of Education, Hefei 230009, China

Received:2023-12-06 Online:2025-12-18 Published:2026-01-07
Contact: Wei XIA E-mail:sunhaiquan@hfut.edu.cn;wangzhilong@mail.hfut.edu.cn;xiaoxuanhu@hfut.edu.cn;xiawei@hfut.edu.cn
About author:
SUN Haiquan was born in 1993. He received his Ph.D. degree from Hefei University of Technology in 2022. He is a lecturer in Hefei University of Technology. His research interests are satellite resource optimization scheduling and intelligent task planning. E-mail: sunhaiquan@hfut.edu.cn

WANG Zhilong was born in 1993. He received his B.S. degree from Hefei University of Technology in 2017. He is currently working for his Ph.D. degree in management science and engineering at Hefei University of Technology. His research interest is satellite intelligent scheduling. E-mail: wangzhilong@mail.hfut.edu.cn

HU Xiaoxuan was born in 1978. He received his B.S. degree and Ph.D. degree from Hefei University of Technology in 1999 and 2007, respectively. He is a professor at Hefei University of Technology. His research interests include satellite scheduling and UAV planning E-mail: xiaoxuanhu@hfut.edu.cn

XIA Wei was born in 1983. He received his Ph.D. degree from Hefei University of Technology in 2014. Currently he is working in University of Technology as an assistant professor. His research interests include satellite intelligent scheduling and controlling. E-mail: xiawei@hfut.edu.cn
Supported by:
This work was supported by the National Natural Science Foundation of China (72071064; 72271074; 72001004) and the Anhui Provincial Natural Science Foundation (2408085QG221).

Abstract

Abstract:

Agile earth observation satellites (AEOSs) represent a new generation of satellites with three degrees of freedom (pitch, roll, and yaw); they possess a long visible time window (VTW) for ground targets and support imaging at any moment within the VTW. However, different observation times demonstrate different cloud cover distributions, which exhibit different effects on the AEOS observation. Previous studies ignored pitch angles, discretized VTWs, or fixed cloud cover for every VTW, which led to the loss of intermediate observation states, thus these studies are not suitable for AEOS scheduling considering cloud cover distribution. In this study, a relationship formula between the cloud cover and observation time is proposed to calculate the cloud cover for every observation time, and a relationship formula between the observation time and pitch angle is designed to calculate the pitch angle for every observation time in the VTW. A refined model including the pitch angle, roll angle, and cloud cover distribution is established, which can make the scheme closer to the actual application of AEOSs. A hybrid genetic simulated annealing (HGSA) algorithm for AEOS scheduling is proposed, which integrates the advantages of genetic and simulated annealing algorithms and can effectively avoid falling into a local optimal solution. The experiments are conducted to compare the proposed algorithm with the traditional algorithms, the results verify that the proposed model and algorithm are efficient and effective for AEOS scheduling considering cloud cover distribution.

Key words: agile Earth observation satellite, cloud cover distribution, hybrid genetic simulated annealing algorithm

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.

Figures/Tables 23

Fig 1

Fig 2

Table 1

Table of symbols"

Symbol	Definition
$ S{\text{ = \{ }}{s_1},\cdots ,{s_j},\cdots ,{s_{{\text{\|}}S{\text{\|}}}}{\text{\} }} $	$ S $ is AEOS set; $ \|S\| $ is its AEOS number; $ {s_j} $ is the jth satellite in $ S $.
$ G{\text{ = \{ }}{g_1},\cdots ,{g_k},\cdots ,{g_{{\text{\|}}G{\text{\|}}}}{\text{\} }} $	$ G $ is ground station set; $ \|G\| $ is its ground station number; $ {g_k} $ is the kth ground station in $ G $.
$ T = \{ {t_1},\cdots ,{t_i},\cdots .,{t_{\|T\|}}\} $	$ T $ is task set; $ \|T\| $ is its task number.
$ {t_i} = ({\mathrm{t}}{v_i},{d_i}) $	$ {t_i} $ is the ith task in $ T $; $ {{\mathrm{tv}}_i} $ and $ {d_i} $ denote the task profit and task observation duration time, respectively.
$ \text{GW}{_k} = \{ \text{GW}_{k1},\cdots ,\text{GW}_{kj},\cdots ,\text{GW}_{k\|S\|}\} $	VTWs of $ {g_k} $.
$ \text{GW}_{kj} = \{ {\mathrm{GW}}_{kj}^1,\cdots ,{\mathrm{GW}}_{kj}^b,\cdots ,{\mathrm{GW}}_{kj}^{\|\text{GW}_{kj}\|}\} $	$ \text{GW}_{kj} $ is VTW set between $ {g_k} $ and $ {s_j} $; $ \|\text{GW}_{kj}\| $ is its VTW number.
$ {\mathrm{GW}}_{kj}^b = (\text{vs}_{kj}^b,\text{ve}_{kj}^b) $	$ {\mathrm{GW}}_{kj}^b $ is the bth VTW between $ {g_k} $ and $ {s_j} $; $ \text{vs}_{kj}^b $ and$ \text{ve}_{kj}^b $ are the earliest and lastest visible times of $ {\mathrm{GW}}_{kj}^b $, respectively.
$ \text{TW}{_i} = \{ \text{TW}{_{i1}},\cdots ,\text{TW}{_{ij}},\cdots ,\text{TW}{_{i{\text{\|}}S{\text{\|}}}}\} $	VTWs of $ {t_i} $.
$ \text{TW}{_{ij}} = \{ \text{TW}_{ij}^1,\cdots ,\text{TW}_{ij}^a,\cdots ,\text{TW}_{ij}^{{\text{\|}}\text{TW}{_{ij}}{\text{\|}}}\} $	$ \text{TW}{_{ij}} $ is VTW set between $ {t_i} $ and $ {s_j} $; $ \|\text{TW}{_{ij}}\| $ is its VTW number.
$ \text{TW}_{ij}^a = (\text{vs}_{ij}^a,\text{ve}_{ij}^a,\bar P_{ij}^a,\underline{P} _{ij}^a,R_{ij}^a) $	$ \text{TW}_{ij}^a $ is the ath VTW between $ {t_i} $ and $ {s_j} $; $ \text{vs}_{ij}^a $, $ \text{ve}_{ij}^a $, $ \bar P_{ij}^a $, $ \underline{P} _{ij}^a $ and $ R_{ij}^a $ are the earliest visible time, latest visible time, maximum pitch angle, minimum pitch angle and ideal roll angle of $ \text{TW}_{ij}^a $, respectively. The ideal roll angle is the angle at which the centerline of the observation band passes through the task.
$ {{\mathrm{pv}}_j} $	Pitch velocity of $ {s_j} $.
$ {{\mathrm{rv}}_j} $	Roll velocity of $ {s_j} $.
$ {b_j} $	Sensor startup time of $ {s_j} $.
$ {e_j} $	Sensor shutdown time of $ {s_j} $.
$ {{\mathrm{as}}_j} $	Sensor attitude stabilization time of $ {s_j} $.
$ {M_j} $	Maximum storage capacity of $ {s_j} $.
$ {\alpha _j} $	Storage capacity required per unit time observation of $ {s_j} $.
$ {\mathrm{OW}} $	OTW set of all tasks.
$ {\mathrm{OW}}_{ij}^a{\text{ = (}}{\mathrm{os}}_{ij}^a{\text{,}}{\mathrm{oe}}_{ij}^a{\text{,}}p_{ij}^a{\text{,}}r_{ij}^a{\text{)}} $	$ {\mathrm{OW}}_{ij}^a $ is the scheduled OTW in $ {\mathrm{TW}}_{ij}^a $; $ {\mathrm{os}}_{ij}^a $, $ {\mathrm{oe}}_{ij}^a $, $ p_{ij}^a $, and $ r_{ij}^a $ denote the observation start time, observation end time, observation pitch angle and observation roll angle of $ {\mathrm{OW}}_{ij}^a $, respectively.
$ {L_j} $	The maximum cloud cover level that $ {s_j} $ can effectively observe tasks.

Table 1

Fig 3

Fig 4

Fig 5

Fig 6

Fig 7

Fig 8

Fig 9

Fig 10

Fig 11

Table 2

Table 3

Table 4

Table 5

Table 6

Fig 12

Fig 13

Table 7

Fig 14

Fig 15

Fig 16

References 32

1	LI G L, XING L N, CHEN Y W A hybrid online scheduling mechanism with revision and progressive techniques for autonomous Earth observation satellite. Acta Astronautica, 2017, 140, 308- 321. doi: 10.1016/j.actaastro.2017.08.011
2	BERGER J, LO N, BARKAOUI M QUEST – a new quadratic decision model for the multi-satellite scheduling problem. Computers & Operations Research, 2019, 115 (7): 104822.
3	PENG G S, SONG G P, XING L N, et al An exact algorithm for agile earth observation satellite scheduling with time-dependent profits. Computers and Operations Research, 2020, 120, 104946. doi: 10.1016/j.cor.2020.104946
4	WANG X W, WU G H, XING L N, et al Agile earth observation satellite scheduling over 20 years: formulations, methods, and future directions. IEEE Systems Journal, 2020, 15 (3): 3881- 3892.
5	XU R, CHEN H P, LIANG X L, et al Priority-based constructive algorithms for scheduling agile earth observation satellites with total priority maximization. Expert Systems with Applications, 2016, 51, 195- 206.
6	LIU S, CHEN Y W, XING L N, et al Time-dependent autonomous task planning of agile imaging satellites. Journal of Intelligent & Fuzzy Systems, 2016, 31 (3): 1365- 1375.
7	CHO D H, KIM J H, CHOI H L, et al Optimization-based scheduling method for agile earth-observing satellite constellation. Journal of Aerospace Computing, Information, and Communication, 2018, 15 (11): 611- 626.
8	HE L, LIU X L, LAPORTE G, et al An improved adaptive large neighborhood search algorithm for multiple agile satellites scheduling. Computers & Operations Research, 2018, 100, 12- 25.
9	HE L, LIU X L, CHEN Y W, et al Hierarchical scheduling for real-time agile satellite task scheduling in a dynamic environment. Advances in Space Research, 2019, 63, 897- 912. doi: 10.1016/j.asr.2018.10.007
10	WANG X W, CHEN Z, HAN C Scheduling for single agile satellite, redundant targets problem using complex networks theory. Chaos, Solitons and Fractals, 2016, 83, 125- 132. doi: 10.1016/j.chaos.2015.12.003
11	GABREL V, MOULET A, MURAT C, et al A new single model and derived algorithms for the satellite shot planning problem using graph theory concepts. Annals of Operations Research, 1997, 69, 115- 134.
12	LEMAITRE M, VERFAILLIE G, JOUHAUD F, et al Selecting and scheduling observations of agile satellites. Aerospace Science and Technology, 2022, 6 (5): 367- 381.
13	TANGPATTANAKUL P, JOZEFOWIEZ N, LOPEZ P A multi-objective local search heuristic for scheduling earth observations taken by an agile satellite. European Journal of Operational Research, 2015, 245, 542- 554. doi: 10.1016/j.ejor.2015.03.011
14	MOK S H, JO S, BANG H C, et al Heuristic-based mission planning for an agile earth observation satellite. International Journal of Aeronautical and Space Sciences, 2019, 20, 781- 791. doi: 10.1007/s42405-018-0105-4
15	HE Y M, CHEN Y W, LU J M, et al Scheduling multiple agile earth observation satellites with an edge computing framework and a constructive heuristic algorithm. Journal of Systems Architecture, 2019, 95, 55- 66. doi: 10.1016/j.sysarc.2019.03.005
16	ZHAO L, WANG S, HAO Y, et al Energy-dependent mission planning for agile earth observation satellite. Journal of Aerospace Engineering, 2019, 32 (1): 4018118. doi: 10.1061/(ASCE)AS.1943-5525.0000949
17	WANG S, ZHAO L, CHENG J H, et al Task scheduling and attitude planning for agile earth observation satellite with intensive tasks. Aerospace Science and Technology, 2019, 90, 23- 33. doi: 10.1016/j.ast.2019.04.007
18	ZHANG J W, XING L N An improved genetic algorithm for the integrated satellite imaging and data transmission scheduling problem. Computers & Operations Research, 2022, 139, 105626.
19	LIU X, LAPORTE G, CHEN Y W, et al An adaptive large neighborhood search metaheuristic for agile satellite scheduling with time-dependent transition time. Computers & Operations Research, 2017, 86, 41- 53.
20	BIANCHESSI N, CORDEAU J F, DESROSIERS J, et al A heuristic for the multi-satellite, multi-orbit and multi-user management of Earth observation satellites. European Journal of Operational Research, 2007, 177 (2): 750- 762. doi: 10.1016/j.ejor.2005.12.026
21	HABET D, VASQUEZ M, VIMONT Y Bounding the optimum for the problem of scheduling the photographs of an agile earth observing satellite. Computational Optimization and Applications, 2010, 47 (2): 307- 333. doi: 10.1007/s10589-008-9220-7
22	CUI K K, XIANG J H, ZHANG Y L Mission planning optimization of video satellite for ground multi-object staring imaging. Advances in Space Research, 2018, 61 (6): 1476- 1489. doi: 10.1016/j.asr.2017.10.056
23	ZHOU Z B, CHEN E, WU F, et al Multi-satellite scheduling problem with marginal decreasing imaging duration: an improved adaptive ant colony algorithm. Computers & Industrial Engineering, 2023, 176, 108890.
24	WANG X W, SONG G P, LEUS R, et al, Robust earth observation satellite scheduling with uncertainty of cloud coverage. IEEE Trans. on Aerospace and Electronic Systems, 2019, 56(3): 2450−2461.
25	LIN W C, LIAO D Y, LIU C Y, et al Daily imaging scheduling of an Earth observation satellite. IEEE Trans. on Systems Man & Cybernetics Part A: Systems & Humans, 2005, 35 (2): 213- 223.
26	WANG J J, DEMEULEMEESTER E, QIU D S A pure proactive scheduling algorithm for multiple earth observation satellites under uncertainties of clouds. Computers & Operations Research, 2016, 74, 1- 13.
27	WANG J J, DEMEULEMEESTER E, HU X J, et al Exact and heuristic scheduling algorithms for multiple earth observation satellites under uncertainties of clouds. IEEE Systems Journal, 2018, 13 (3): 3556- 3567.
28	SUN H Q, XIA W, WANG Z L, et al Agile earth observation satellite scheduling algorithm for emergency tasks based on multiple strategies. Journal of Systems Science and Systems Engineering, 2021, 30 (5): 626- 646. doi: 10.1007/s11518-021-5506-4
29	SUN H Multi-objective optimization for hydraulic hybrid vehicle based on adaptive simulated annealing genetic algorithm. Engineering Applications of Artificial Intelligence, 2010, 23, 27- 33. doi: 10.1016/j.engappai.2009.09.005
30	LEUNG T W, CHAN C K, TROUTT M D Application of a mixed simulated annealing-genetic algorithm heuristic for the two-dimensional orthogonal packing problem. European Journal of Operational Research, 2003, 145, 530- 542. doi: 10.1016/S0377-2217(02)00218-7
31	BOULEIMEN K, LECOCQ H A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version. European Journal of Operational Research, 2003, 149 (2): 268- 281. doi: 10.1016/S0377-2217(02)00761-0
32	YU V F, REDI A, HIDAYAT Y A, et al A simulated annealing heuristic for the hybrid vehicle routing problem. Applied Soft Computing, 2017, 53, 119- 132. doi: 10.1016/j.asoc.2016.12.027

AEOS name	Startup time/s	Shutdown time/s	Attitude stabilization time/s	Roll velocity/ (°/s)	Pitch velocity/ (°/s)	Storage capacity/s	Orbit period/ min	Orbit height/km
AEOS1	2	2	2	5	5	200	97.5	628
AEOS2	2	2	2	5	5	200	97.3	622
AEOS3	2	2	2	5	5	200	97.5	613
AEOS4	2	2	2	5	5	200	94.9	511
AEOS5	2	2	2	5	5	200	94.4	488

Ground station name	Longitude/(°)	Latitude/(°)	Altitude/(°)
BEIJING	116.60	39.04	0
CHANGSHA	113.04	28.25	0
JIAMUSI	130.37	46.82	0
TAIYUAN	112.30	37.54	0

Parameter	Range	Value 1	Value 2	Value 3	Value 4	Value 5
${N_p}$	20−100	20	40	60	80	100
${P_c}$	0.75−0.95	0.75	0.80	0.85	0.90	0.95
${P_c}$	0.05−0.25	0.05	0.10	0.15	0.20	0.25
${T_0}$	10²−10⁶	10²	10³	10⁴	10⁵	10⁶
$\lambda $	0.75−0.95	0.75	0.80	0.85	0.90	0.95

${N_p}$	${P_c}$	${P_m}$	${T_0}$	$\lambda $
20	0.75	0.05	10²	0.75
20	0.80	0.10	10³	0.80
20	0.85	0.15	10⁴	0.85
20	0.90	0.20	10⁵	0.90
20	0.95	0.25	10⁶	0.95
40	0.75	0.10	10⁴	0.90
40	0.80	0.15	10⁵	0.95
40	0.85	0.20	10⁶	0.75
40	0.90	0.25	10²	0.80
40	0.95	0.05	10³	0.85
60	0.75	0.15	10⁶	0.80
60	0.80	0.20	10²	0.85
60	0.85	0.25	10³	0.90
60	0.90	0.05	10⁴	0.95
60	0.95	0.10	10⁵	0.75
80	0.75	0.20	10³	0.95
80	0.80	0.25	10⁴	0.75
80	0.85	0.05	10⁵	0.80
80	0.90	0.10	10⁶	0.85
80	0.95	0.15	10²	0.90
100	0.75	0.25	10⁵	0.85
100	0.80	0.05	10⁶	0.90
100	0.85	0.10	10²	0.95
100	0.90	0.15	10³	0.75
100	0.95	0.20	10⁴	0.80

G3−G4		G9−G10
Mean	S/N	Mean	S/N
0.9209	0.7154	0.8159	1.7665
0.9220	0.7047	0.8171	1.7537
0.9221	0.7040	0.8207	1.7155
0.9292	0.6376	0.8223	1.6982
0.9265	0.6624	0.8179	1.7447
0.9298	0.6319	0.8232	1.6891
0.9295	0.6342	0.8256	1.6633
0.9301	0.6283	0.8246	1.6745
0.9281	0.6477	0.8252	1.6677
0.9264	0.6631	0.8214	1.7084
0.9331	0.6010	0.8273	1.6460
0.9354	0.5799	0.8287	1.6313
0.9327	0.6047	0.8299	1.6186
0.9330	0.6021	0.8304	1.6127
0.9325	0.6061	0.8271	1.6472
0.9336	0.5963	0.8305	1.6117
0.9353	0.5800	0.8308	1.6090
0.9363	0.5714	0.8316	1.6001
0.9349	0.5839	0.8308	1.6085
0.9353	0.5808	0.8303	1.6141
0.9353	0.5800	0.8296	1.6207
0.9347	0.5857	0.8297	1.6206
0.9326	0.6051	0.8287	1.6311
0.9348	0.5847	0.8299	1.6180
0.9356	0.5778	0.8312	1.6047

Hybrid genetic simulated annealing algorithm for agile Earth observation satellite scheduling considering cloud cover distribution

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 23

References 32

Related Articles 1

Recommended Articles

Metrics

Comments

Algorithm	Result	E1	E2	E3	E4	E5	E6	E7	E8	E9	E10	E11	E12
HGSA	Running time/s	18.07	28.66	39.89	57.33	76.11	98.32	21.18	35.85	52.37	71.46	102.07	135.61
	Objective function	0.9846	0.9685	0.9384	0.9331	0.9062	0.8812	0.9389	0.8779	0.8406	0.8209	0.7894	0.7579
	Number of scheduled tasks	144	187	223	266	294	319	134	165	193	226	247	266
	Profit of scheduled tasks	2230	3071	3747	4472	5013	5493	2230	2842	3430	3934	4421	4854
GA	Running time/s	18.45	26.59	38.41	49.99	66.57	80.41	20.86	33.17	51.45	67.46	89.08	112.45
	Objective function	0.9717	0.9495	0.9233	0.9139	0.8907	0.8561	0.9202	0.8574	0.8221	0.8018	0.7664	0.7381
	Number of scheduled tasks	142	183	220	257	291	307	129	158	188	219	239	257
	Profit of scheduled tasks	2202	3010	3687	4375	4924	5338	2181	2772	3360	3838	4296	4724
SA	Running time/s	20.89	29.88	41.28	60.851	81.89	102.42	25.14	36.54	57.01	85.05	119.27	161.26
	Objective function	0.9726	0.9482	0.9185	0.9132	0.888	0.8603	0.9202	0.858	0.8248	0.803	0.767	0.7364
	Number of scheduled tasks	141	182	217	257	292	315	130	159	191	221	238	259
	Profit of scheduled tasks	2204	3008	3668	4374	4914	5360	2186	2778	3366	3849	4299	4713
TS	Running time/s	15.52	25.13	33.87	46.76	68.02	85.93	19.75	33.15	47.45	60.33	79.12	109.37
	Objective function	0.9659	0.9444	0.9158	0.9101	0.8822	0.8569	0.9176	0.8546	0.8191	0.7988	0.7628	0.7348
	Number of scheduled tasks	142	182	215	256	285	310	128	157	184	216	237	253
	Profit of scheduled tasks	2186	2994	3657	4358	4882	5338	2176	2763	3348	3829	4274	4707
PN	Training time/h	11.14	16.24	22.53	30.21	39.38	50.09	11.09	16.32	22.49	30.20	39.43	50.16
	Running time/s	2.23	2.54	2.81	3.13	3.59	4.07	2.28	2.60	2.96	3.42	3.92	4.33
	Objective function	0.9646	0.9429	0.9141	0.9108	0.8814	0.8551	0.9157	0.8531	0.8180	0.7990	0.7620	0.7343
	Number of scheduled tasks	142	180	214	257	283	310	127	156	182	216	236	252
	Profit of scheduled tasks	2183	2989	3650	4362	4875	5330	2172	2759	3344	3827	4269	4701