基于ESWO的敏捷对地观测卫星任务调度算法

doi:10.7527/S1000-6893.2023.29370

电子电气工程与控制

本期目录 | 过刊浏览 | 高级检索

前一篇 | 后一篇

基于ESWO的敏捷对地观测卫星任务调度算法

李海¹, 李勇军¹(), 刘元皓¹, 赵卫虎², 李信¹, 赵尚弘¹

^1.空军工程大学信息与导航学院，西安 710077
^2.国防科技大学信息通信学院，武汉 430000

收稿日期:2023-07-27 修回日期:2023-09-04 接受日期:2023-09-26 出版日期:2024-05-25 发布日期:2023-10-24
通讯作者: 李勇军 E-mail:tz_228@163.com
基金资助:
国家自然科学基金(61701522)

ESWO⁃based task⁃scheduling algorithm for agile earth observation satellites

Hai LI¹, Yongjun LI¹(), Yuanhao LIU¹, Weihu ZHAO², Xin LI¹, Shanghong ZHAO¹

^1.College of Information and Navigation，Air Force Engineering University，Xi’an 710077，China
^2.College of Information and Communication，National University of Defense Technology，Wuhan 430000，China

Received:2023-07-27 Revised:2023-09-04 Accepted:2023-09-26 Online:2024-05-25 Published:2023-10-24
Contact: Yongjun LI E-mail:tz_228@163.com
Supported by:
National Natural Science Foundation of China(61701522)

摘要/Abstract

摘要：

具备灵活姿态机动能力的敏捷对地观测卫星（简称为敏捷卫星）极大地提高了对地观测能力，但大幅增长的可见时间窗口数量和长度给敏捷卫星观测调度问题的求解带来了巨大的挑战，同时敏捷卫星特有的时间依赖转换时间使观测调度问题进一步复杂化，因此，敏捷卫星观测调度问题受到了广泛的关注。针对敏捷卫星任务调度问题，以观测收益最大化为目标，建立了考虑时间依赖转换时间特性的混合整数非线性规划数学模型，基于具有大邻域导向搜索能力的演化吱呀轮优化（ESWO）算法框架提出一种启发式敏捷卫星任务调度算法（ESASS）。该算法结合敏捷卫星观测调度问题的特征，设计了ESWO算法的5个核心操作算子即分析器、选择操作、变异操作、优先级排序器和构造器，并且借鉴模拟退火算法的思想设计了一个自适应更新策略来提高算法的求解速度和性能。为了验证ESASS算法的有效性，将该算法与自适应大邻域搜索（ALNS）算法、启发式插入算法和基于遗传算法（GA）的观测调度算法进行仿真比较。仿真实验结果表明，与现有算法相比，提出的ESASS算法用较短的计算运行时间可获得在观测收益和观测任务数量方面性能最好的调度方案，ESASS算法适用于求解具有时间依赖转换时间特性的敏捷卫星观测调度问题。

关键词: 敏捷卫星, 观测调度, 时间依赖转换时间, ESWO, 自适应更新策略

Abstract:

Agile Earth Observation Satellites （AEOSs）（abbreviated as agile satellite） with flexible attitude maneuvering capability greatly improve the Earth observation capability. However， the rapid increase in the number and length of visible time windows brings great challenges to agile satellite observation scheduling， and the specific time-dependent transition time of the agile satellites further complicates the observation scheduling problem. Therefore， the agile satellites observation scheduling problem has received extensive attention. To address the problem of observation scheduling of agile satellites， a mixed-integer nonlinear programming mathematical model aiming at maximizing observation profits is established with a consideration of the time-dependent transition time. Then， based on the framework of Evolutionary Squeaky Wheel Optimization （ESWO） algorithm with large neighborhood-oriented search capability， a heuristic agile satellites task-scheduling algorithm（ESASS） is proposed. In the proposed algorithm， five core operators of the ESWO algorithm are designed： analyzer， selection operation， mutation operation， priority sorter and constructor， according to the characteristics of AEOS observation scheduling problem. Then， an adaptive update strategy is designed based on the idea of simulated annealing algorithm to improve the solution speed and performance. A comparison of the proposed algorithm with the Adaptive Large Neighborhood Search （ALNS） algorithm， the classic heuristic insertion algorithm and the Genetic Algorithm （GA）-based observation scheduling algorithm verifies the effectiveness of the proposed algorithm. The experimental results show that the proposed ESASS algorithm can achieve greater benefits and number of observation tasks with shorter CPU runtime， and is applicable to the AEOSs observation scheduling problem with time-dependent transition time characteristics.

Key words: agile satellite, observation scheduling, time-dependent transition time, Evolutionary Squeaky Wheel Optimization (ESWO), adaptive update strategy

中图分类号:

V474

李海, 李勇军, 刘元皓, 赵卫虎, 李信, 赵尚弘. 基于ESWO的敏捷对地观测卫星任务调度算法[J]. 航空学报, 2024, 45(10): 329370-329370.

Hai LI, Yongjun LI, Yuanhao LIU, Weihu ZHAO, Xin LI, Shanghong ZHAO. ESWO⁃based task⁃scheduling algorithm for agile earth observation satellites[J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(10): 329370-329370.

图/表 10

图 1

图 2

图 3

图 4

表 1

表 2

表 3

图5

图6

图7

参考文献 28

1	李志亮，李小将，王志恒. 敏捷卫星任务规划问题研究现状与展望［J］. 装备学院学报， 2016， 27（1）： 69-75.
	LI Z L， LI X J， WANG Z H. Current status and prospect of agile satellite mission planning［J］. Journal of Equipment Academy， 2016， 27（1）： 69-75 （in Chinese）.
2	WANG X W， WU G H， XING L N， et al. Agile earth observation satellite scheduling over 20 years： Formulations， methods， and future directions［J］. IEEE Systems Journal， 2021， 15（3）： 3881-3892.
3	谢平，杜永浩，姚锋，等. 敏捷成像卫星自主调度技术综述［J］. 宇航学报， 2019， 40（2）： 127-138.
	XIE P， DU Y H， YAO F， et al. Literature review for autonomous scheduling technology of agile earth observation satellites［J］. Journal of Astronautics， 2019， 40（2）： 127-138 （in Chinese）.
4	LEMAI^TRE M， VERFAILLIE G， JOUHAUD F， et al. Selecting and scheduling observations of agile satellites［J］. Aerospace Science and Technology， 2002， 6（5）： 367-381.
5	VASQUEZ M， HAO J K. A “logic-constrained” knapsack formulation and a tabu algorithm for the daily photograph scheduling of an earth observation satellite［J］. Computational Optimization and Applications， 2001， 20（2）： 137-157.
6	LIN W C， LIAO D Y， LIU C Y， et al. Daily imaging scheduling of an earth observation satellite［J］. IEEE Transactions on Systems， Man， and Cybernetics - Part A： Systems and Humans， 2005， 35（2）： 213-223.
7	CHU X G， CHEN Y N， TAN Y J. An anytime branch and bound algorithm for agile earth observation satellite onboard scheduling［J］. Advances in Space Research， 2017， 60（9）： 2077-2090.
8	WANG X W， CHEN Z， HAN C. Scheduling for single agile satellite， redundant targets problem using complex networks theory［J］. Chaos， Solitons & Fractals， 2016， 83： 125-132.
9	WANG X W， HAN C， ZHANG R， et al. Scheduling multiple agile earth observation satellites for oversubscribed targets using complex networks theory［J］. IEEE Access， 2019， 7： 110605-110615.
10	赵琳，王硕，郝勇，等. 基于能量最优的敏捷遥感卫星在轨任务规划［J］. 航空学报， 2017， 38（6）： 320654.
	ZHAO L， WANG S， HAO Y， et al. Energy-optimal in orbit mission planning for agile remote sensing satellites［J］. Acta Aeronautica et Astronautica Sinica， 2017， 38（6）： 320654 （in Chinese）.
11	伍国华，杜潇，王心慰，等. 考虑邻域结构动态调整的多星应急调度算法［J］. 控制与决策， 2022， 37（7）： 1685-1694.
	WU G H， DU X， WANG X W， et al. Multi-satellite emergency scheduling algorithm considering dynamic selection of neighborhood structure［J］. Control and Decision， 2022， 37（7）： 1685-1694 （in Chinese）.
12	李志亮，李小将，孙伟. 考虑成像质量的敏捷卫星任务调度模型与算法［J］. 宇航学报， 2017， 38（6）： 590-597.
	LI Z L， LI X J， SUN W. Task scheduling model and algorithm for agile satellite considering imaging quality［J］. Journal of Astronautics， 2017， 38（6）： 590-597 （in Chinese）.
13	邱涤珊，郭浩，贺川，等. 敏捷成像卫星多星密集任务调度方法［J］. 航空学报， 2013， 34（4）： 882-889.
	QIU D S， GUO H， HE C， et al. Intensive task scheduling method for multi-agile imaging satellites［J］. Acta Aeronautica et Astronautica Sinica， 2013， 34（4）： 882-889 （in Chinese）.
14	王海蛟，贺欢，杨震. 敏捷成像卫星调度的改进量子遗传算法［J］. 宇航学报， 2018， 39（11）： 1266-1274.
	WANG H J， HE H， YANG Z. Scheduling of agile satellites based on an improved quantum genetic algorithm［J］. Journal of Astronautics， 2018， 39（11）： 1266-1274 （in Chinese）.
15	LIU X L， LAPORTE G， CHEN Y W， et al. An adaptive large neighborhood search metaheuristic for agile satellite scheduling with time-dependent transition time［J］. Computers & Operations Research， 2017， 86： 41-53.
16	HE L， LIU X L， LAPORTE G， et al. An improved adaptive large neighborhood search algorithm for multiple agile satellites scheduling［J］. Computers & Operations Research， 2018， 100： 12-25.
17	WEI L N， XING L N， WAN Q， et al. A multi-objective memetic approach for time-dependent agile earth observation satellite scheduling problem［J］. Computers & Industrial Engineering， 2021， 159： 107530.
18	PENG G S， SONG G P， HE Y M， et al. Solving the agile earth observation satellite scheduling problem with time-dependent transition times［J］. IEEE Transactions on Systems， Man， and Cybernetics： Systems， 2022， 52（3）： 1614-1625.
19	AICKELIN U， BURKE E K， LI J P. An evolutionary squeaky wheel optimization approach to personnel scheduling［J］. IEEE Transactions on Evolutionary Computation， 2009， 13（2）： 433-443.
20	LI J P， PARKES A J， BURKE E K. Evolutionary squeaky wheel optimization： A new framework for analysis［J］. Evolutionary Computation， 2011， 19（3）： 405-428.
21	王东兴，宋雪雁，孙济洲. 航班着陆调度的多目标优化研究［J］. 计算机应用与软件， 2015， 32（2）： 224-227.
	WANG D X， SONG X Y， SUN J Z. On multi-objective optimisation algorithm for flight landing scheduling［J］. Computer Applications and Software， 2015， 32（2）： 224-227 （in Chinese）.
22	JOSLIN D E， CLEMENTS D P. “Squeaky wheel” optimization［C］∥ Proceedings of the Fifteenth National/Tenth Conference on Artificial Intelligence/Innovative Applications of Artificial Intelligence. New York： ACM， 1998： 340⁃346.
23	BURKE E K， HYDE M R， KENDALL G. A squeaky wheel optimisation methodology for two-dimensional strip packing［J］. Computers & Operations Research， 2011， 38（7）： 1035-1044.
24	经飞，王钧，李军，等. 基于吱呀轮优化的多卫星数传调度问题求解方法［J］. 宇航学报， 2011， 32（4）： 863-870.
	JING F， WANG J， LI J， et al. A new scheduling method for multi-satellite data transmission based on squeaky-wheel optimization［J］. Journal of Astronautics， 2011， 32（4）： 863-870 （in Chinese）.
25	UMANG N， BIERLAIRE M， VACCA I. Exact and heuristic methods to solve the berth allocation problem in bulk ports［J］. Transportation Research Part E： Logistics and Transportation Review， 2013， 54： 14-31.
26	LYU X H， NEGENBORN R R， SHI X N， et al. A collaborative berth planning approach for disruption recovery［J］. IEEE Open Journal of Intelligent Transportation Systems， 2022， 3： 153-164.
27	HOARE C A R. Quicksort［J］. The Computer Journal， 1962， 5（1）： 10-16.
28	SUN H Q， XIA W， HU X X， et al. Earth observation satellite scheduling for emergency tasks［J］. Journal of Systems Engineering and Electronics， 2019， 30（5）： 931-945.

E-mail：hkxb@buaa.edu.cn

关于我们

期刊社服务

专业学科

封面文章

友情链接

主管单位：中国科学技术协会主办单位：中国航空学会北京航空航天大学

卫星ID	半长轴/m	轨道倾角/（°）	升交点赤经/（°）	平近点角/（°）
卫星1	7 200 000	96.576	175.72	0.075 0
卫星2	7 200 000	96.576	145.72	30.075 0
卫星3	7 200 000	96.576	115.72	60.075 0
卫星4	7 200 000	96.576	85.72	90.075 0
卫星5	7 200 000	96.576	55.72	120.075 0
卫星6	7 200 000	96.576	25.72	150.075 0

卫星数量	任务负载	CPU时间/s				观测收益率/%				观测任务数量比例/%
卫星数量	任务负载	ESASS	ALNS	ISBDR	GA	ESASS	ALNS	ISBDR	GA	ESASS	ALNS	ISBDR	GA
2	轻	81.94	113.68	0.45	310.39	63.20	59.75	55.04	56.43	57.74	47.42	46.42	46.32
2	重	364.74	709.52	1.76	1 193.80	31.74	29.98	26.95	27.72	27.82	20.90	19.83	20.31
3	轻	70.98	99.17	0.38	314.46	75.90	70.11	62.55	65.88	70.57	58.12	54.97	56.25
3	重	326.15	700.86	1.80	1 198.10	43.47	41.02	36.02	37.06	37.93	29.37	27.54	27.81
4	轻	50.18	67.39	0.35	261.00	81.84	78.13	70.60	73.24	77.60	67.72	64.57	64.76
4	重	356.98	676.79	1.84	1 667.5	53.37	49.48	43.25	44.25	46.53	36.27	34.16	33.93
5	轻	35.01	56.14	0.31	335.26	87.18	82.05	75.41	78.06	82.44	72.92	69.88	70.55
5	重	317.89	533.01	1.77	1 144.00	60.46	55.50	48.88	49.79	52.85	41.44	38.94	38.70
6	轻	25.85	41.77	0.27	207.61	89.33	85.50	79.32	82.06	85.65	77.02	73.76	74.78
6	重	272.20	549.24	1.70	1 078.40	66.59	61.87	54.06	55.26	59.51	47.24	43.64	43.86

卫星数量	任务负载	CPU时间/s				观测收益率/%				观测任务数量比例/%
卫星数量	任务负载	ESASS	ALNS	ISBDR	GA	ESASS	ALNS	ISBDR	GA	ESASS	ALNS	ISBDR	GA
2	轻	28.63	78.05	0.55	386.78	98.05	95.64	93.45	94.73	97.33	92.53	91.23	91.76
2	重	1 131.70	634.22	8.91	8 317.40	85.50	82.43	77.81	78.54	82.61	71.73	70.44	70.38
3	轻	7.27	51.59	0.26	151.96	99.27	97.89	96.27	97.43	98.79	96.29	95.09	95.94
3	重	469.50	478.77	4.63	3 347.30	94.47	89.19	86.17	86.62	93.26	82.49	81.11	81.40
4	轻	2.46	28.98	0.16	93.24	99.37	98.21	96.81	97.87	99.19	97.42	96.08	97.07
4	重	155.18	482.07	2.94	1 962.60	96.87	92.41	89.47	90.56	96.11	88.00	86.10	87.11
5	轻	1.31	19.69	0.10	61.14	99.62	98.74	97.79	98.49	99.40	98.16	97.42	97.81
5	重	62.86	419.24	1.97	1 414.40	98.36	94.60	92.20	93.20	97.63	91.53	89.89	90.48
6	轻	0.87	23.00	0.08	49.74	99.51	98.93	98.12	98.62	99.39	98.57	97.95	98.15
6	重	31.25	307.28	1.35	988.04	98.66	95.73	93.69	94.61	98.24	93.63	92.14	92.73

[1]	杨迪, 李振瑜, 郭帅, 张嘉城, 罗亚中. 天基低轨海上移动目标成像搜索任务调度[J]. 航空学报, 2023, 44(15): 528752-528752.
[2]	赵琳, 王硕, 郝勇, 刘源, 柴毅. 基于地面任务-空间姿态映射的敏捷卫星任务规划[J]. 航空学报, 2018, 39(10): 322066-322066.

基于ESWO的敏捷对地观测卫星任务调度算法

ESWO⁃based task⁃scheduling algorithm for agile earth observation satellites

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 28

相关文章 2

编辑推荐

Metrics

本文评价