基于自适应大邻域搜索的多场景多卫星任务规划方法

doi:10.16182/j.issn1004731x.joss.25-0095

系统仿真学报 ›› 2025, Vol. 37 ›› Issue (7): 1836-1847.doi: 10.16182/j.issn1004731x.joss.25-0095

• 特约论文 • 上一篇

基于自适应大邻域搜索的多场景多卫星任务规划方法

李庥甜¹, 王凌², 陈英武¹, 邢立宁³, 陈盈果¹

^1.国防科技大学系统工程学院，湖南长沙 410073
^2.清华大学自动化系，北京 100084
^3.江苏理工学院智能控制与制造系统研究院，江苏常州 213001

收稿日期:2025-02-10 修回日期:2025-04-13 出版日期:2025-07-18 发布日期:2025-07-30
通讯作者: 邢立宁
第一作者简介:李庥甜(1999-)，女，硕士生，研究方向为人工智能。
基金资助:
国家自然科学基金(U23B2039)

Multi-scenario Multi-satellite Mission Planning Method Based on Adaptive Large Neighborhood Search

Li Xiutian¹, Wang Ling², Chen Yingwu¹, Xing Lining³, Chen Yingguo¹

^1.College of Systems Engineering, National University of Defense Technology, Changsha 410073, China
^2.Department of Automation, Tsinghua University, Beijing 100084, China
^3.Research Institute of Intelligent Control and Manufacturing System, Jiangsu University of Technology, Changzhou 213001, China

Received:2025-02-10 Revised:2025-04-13 Online:2025-07-18 Published:2025-07-30
Contact: Xing Lining

摘要/Abstract

摘要：

为进一步提高遥感卫星的任务执行效率，针对多场景多卫星任务规划问题的约束复杂性、规模动态性及资源异构性挑战，提出了一种融合自适应大邻域搜索与约束规划-布尔可满足性问题（constraint programming-boolean satisfiability problem，CP-SAT）求解监视器的集成优化框架。建立了统一的多目标混合整数规划模型，耦合点目标与区域任务的异构约束；设计了时域滚动机制动态分解问题规模，并基于优先级筛选策略提升自适应大邻域搜索的搜索效率；通过CP-SAT监视器实时验证解可行性。结果表明：相比于遗传算法、粒子群优化及深度Q网络，所提方法在300个测试场景中任务完成率提升15%~28%，运行耗时降低30%~50%，且负载均衡度优化20%以上。

关键词: 卫星任务筹划, 多类型场景, 自适应大邻域搜索, 混合整数规划, 动态优先级筛选

Abstract:

To further improve the execution efficiency of remote sensing satellites, an integrated optimization framework combining adaptive large neighborhood search (ALNS) and a constraint programming-boolean satisfiability problem (CP-SAT) solver monitor was proposed, addressing the challenges of complex constraints, dynamic scale, and resource heterogeneity in multi-scenario multi-satellite mission planning. A unified multi-objective mixed-integer programming model was established, coupling heterogeneous constraints of point targets and area tasks. A time-domain rolling mechanism dynamically decomposed the problem scale, and a priority screening strategy enhanced the search efficiency of ALNS. Solution feasibility was verified in real time through the CP-SAT monitor. Results show that compared with genetic algorithm, particle swarm optimization, and deep Q-network, the proposed method achieves a 15%~28% improvement in task completion rate, 30%~50% reduction in computation time, and over 20% optimization in load balancing in 300 test scenarios.

Key words: satellite mission planning, multi-scenario, adaptive large neighborhood search, mixed-integer programming, dynamic priority screening

中图分类号:

TP391.9

李庥甜,王凌,陈英武等 . 基于自适应大邻域搜索的多场景多卫星任务规划方法[J]. 系统仿真学报, 2025, 37(7): 1836-1847.

Li Xiutian,Wang Ling,Chen Yingwu,et al . Multi-scenario Multi-satellite Mission Planning Method Based on Adaptive Large Neighborhood Search[J]. Journal of System Simulation, 2025, 37(7): 1836-1847.

图/表 12

图1

图 2

图 3

图 4

图 5

表 1

表 2

表 3

图6

图7

表4

表 5

不同权重组合下的性能对比

权重组合 $(ω 1, ω 2, ω 3)$	任务完成率/%	负载均衡度/%	综合得分
(0.8, 0.1, 0.1)	95.2	72.5	8 700
(0.6, 0.3, 0.1)	94.5	90.8	9 200
(0.5, 0.3, 0.2)	91.8	92.5	8 900
(0.7, 0.2, 0.1)	94.1	85.3	9 000
(0.4, 0.4, 0.2)	88.8	94.8	8 300

表 5

参考文献 21

[1]	Lu Zezhong, Shen Xin, Li Deren, et al. Integrated Imaging Mission Planning Modeling Method for Multi-type Targets for Super-agile Earth Observation Satellite[J]. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 2022, 15: 4156-4169.
[2]	Chang Zhongxiang, Zhou Zhongbao, Xing Lining, et al. Integrated Scheduling Problem for Earth Observation Satellites Based on Three Modeling Frameworks: An Adaptive Bi-objective Memetic Algorithm[J]. Memetic Computing, 2021, 13(2): 203-226.
[3]	Herrmann A, Schaub H. Reinforcement Learning for the Agile Earth-observing Satellite Scheduling Problem[J]. IEEE Transactions on Aerospace and Electronic Systems, 2023, 59(5): 5235-5247.
[4]	Wu Jian, Yao Feng, Song Yanjie, et al. Frequent Pattern-based Parallel Search Approach for Time-dependent Agile Earth Observation Satellite Scheduling[J]. Information Sciences, 2023, 636: 118924.
[5]	丁祎男, 雷拥军, 王淑一, 等. 面向重访周期需求的敏捷成像卫星任务规划方法[J]. 空间控制技术与应用, 2024, 50(2): 23-29.
	Ding Yinan, Lei Yongjun, Wang Shuyi, et al. Agile Imaging Satellite Task Planning Method for Revisit Time Requirements[J]. Aerospace Control and Application, 2024, 50(2): 23-29.
[6]	沈鹏, 王艳, 纪志成, 等. 超启发式DE算法求解零等待发酵工艺调度[J]. 系统仿真学报, 2020, 32(11): 2235-2243.
	Shen Peng, Wang Yan, Ji Zhicheng, et al. Hyper-heuristic DE Algorithm for Solving Zero-wait Fermentation Process Schedulinge[J]. Journal of System Simulation, 2020, 32(11): 2235-2243.
[7]	李君, 邢立宁, 彭观胜, 等. 考虑多类型时间依赖资源约束的敏捷卫星调度优化[J]. 控制理论与应用, 2024, 41(6): 1038-1046.
	Li Jun, Xing Lining, Peng Guansheng, et al. The Agile Earth Observation Satellite Scheduling with Multiple Resource Constraints[J]. Control Theory & Applications, 2024, 41(6): 1038-1046.
[8]	Zhang Guohui, Li Xinhong, Hu Gangxuan, et al. Mission Planning Issues of Imaging Satellites: Summary, Discussion, and Prospects[J]. International Journal of Aerospace Engineering, 2021, 2021(1): 7819105.
[9]	邵良杉, 王振, 李昌明. 基于模拟退火与改进粒子群的矿井通风优化算法[J]. 系统仿真学报, 2021, 33(9): 2085-2094.
	Shao Liangshan, Wang Zhen, Li Changming. Optimization Algorithm of Mine Ventilation Based on SA-IPSO[J]. Journal of System Simulation, 2021, 33(9): 2085-2094.
[10]	Li Xiuhong, Sun Chongxiang, Fan Huilong, et al. Remote-sensing Satellite Mission Scheduling Optimisation Method Under Dynamic Mission Priorities[J]. Mathematics, 2024, 12(11): 1704.
[11]	张科科, 孙煜坤, 夏磊, 等. 网络卫星在轨分布式协同任务调度方法[J]. 哈尔滨工程大学学报, 2019, 40(2): 393-399.
	Zhang Keke, Sun Yukun, Xia Lei, et al. A Method of Network Satellite On-orbit Distributed Collaborative Mission Scheduling[J]. Journal of Harbin Engineering University, 2019, 40(2): 393-399.
[12]	Song Bingyu, Chen Yingwu, Yang Qing, et al. On-board Decentralized Observation Planning for LEO Satellite Constellations[J]. Algorithms, 2023, 16(2): 114.
[13]	Song Yanjie, Wei Luona, Yang Qing, et al. RL-GA: A Reinforcement Learning-based Genetic Algorithm for Electromagnetic Detection Satellite Scheduling Problem[J]. Swarm and Evolutionary Computation, 2023, 77: 101236.
[14]	高天旸, 胡笑旋, 夏维. 基于分布式协同进化的星座自主任务规划算法[J]. 系统工程与电子技术, 2022, 44(5): 1600-1608.
	Gao Tianyang, Hu Xiaoxuan, Xia Wei. Constellation Autonomous Mission Planning Algorithm Based on Distributed Co-evolution[J]. Systems Engineering and Electronics, 2022, 44(5): 1600-1608.
[15]	Wang Yue, Sun Gang, Wang Haotong. Multi-satellite Task Planning Based on Dynamic Collaboration with Multiple Boundary Constraints[C]//Signal and Information Processing, Networking and Computers. Singapore: Springer Nature Singapore, 2024: 42-50.
[16]	Wilken Jascha. Cost Estimation for Launch Vehicle Families Considering Uncertain Market Scenarios[J]. Acta Astronautica, 2024, 216: 15-26.
[17]	杨纪伟, 贾慧燕, 吕丽红, 等. 基于边界点的区域目标可见时段计算方法[J]. 计算机与网络, 2023, 49(9): 53-57.
	Yang Jiwei, Jia Huiyan, Lihong Lü, et al. The Calculation Method of Regional Target Visible Window Based on the Boundary Point[J]. Computer & Network, 2023, 49(9): 53-57.
[18]	Young A H, Knapp K R, Inamdar A, et al. The International Satellite Cloud Climatology Project H-Series Climate Data Record Product[J]. Earth System Science Data, 2018, 10(1): 583-593.
[19]	鲍惠芳, 方杰, 张进思, 等. 基于改进蚁群算法的低碳冷链配送路径优化[J]. 系统仿真学报, 2024, 36(1): 183-194.
	Bao Huifang, Fang Jie, Zhang Jinsi, et al. Optimization on Cold Chain Distribution Routes Considering Carbon Emissions Based on Improved Ant Colony Algorithm[J]. Journal of System Simulation, 2024, 36(1): 183-194.
[20]	Du Panpan, Li Jiandong, Bai Weigang, et al. Dual Location Area Based Distributed Location Management for Hybrid LEO/MEO Mega Satellite Networks[J]. IEEE Transactions on Vehicular Technology, 2023, 72(2): 2307-2321.
[21]	Pisinger David, Ropke Stefan. A General Heuristic for Vehicle Routing Problems[J]. Computers & Operations Research, 2007, 34(8): 2403-2435.

求解问题	点目标得分	区域目标得分	最高得分
静态问题	2 955.50	343.259	3 298.76
set300动态3阶段	2 844.92	351.947	3 196.86
set300动态12阶段	3 236.75	430.914	3 667.66

算法	任务完成率/%	运行时间/s	负载均衡度/%	实时调整次数
GA	72.3	45.2	68.5	0
PSO	78.1	32.7	72.1	0
Memetic	85.4	58.9	79.3	0
ALNS-TR	93.5	18.9	89.7	12

场景	卫星数	任务数	任务完成率/%	迭代次数	平均任务收益	运行时间/s
小规模场景	30	62	100.00	20	122.385	0.082
中等规模场景	80	250	95.62	20	975.603	1.248
大规模场景	200	620	90.18	20	3 495.081	16.743

基于自适应大邻域搜索的多场景多卫星任务规划方法

Multi-scenario Multi-satellite Mission Planning Method Based on Adaptive Large Neighborhood Search

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 21

相关文章 5

编辑推荐

Metrics

本文评价

难度	静态阶段		动态阶段追加目标		卫星数量
难度	点目标	区域目标	点目标	区域目标	光学卫星	雷达卫星
低	45	5	5	1	20	10
中	180	20	20	5	52	28
高	450	50	50	10	132	68

[1]	崔焕焕, 官礼和. 优先配送绿色VRP的混合启发式求解算法[J]. 系统仿真学报, 2025, 37(2): 413-423.
[2]	李珍萍, 施莹, 吴凌云. 多约束混流线平衡与排序优化问题研究[J]. 系统仿真学报, 2023, 35(1): 27-40.
[3]	李珍萍, 杨光, 韩倩倩. 考虑工作量均衡的成品油二次配送车辆路径问题[J]. 系统仿真学报, 2022, 34(2): 221-233.
[4]	李珍萍, 赵雨薇, 张煜炜, 邢立宁, 任腾. 共同配送选址-路径问题及大邻域搜索算法[J]. 系统仿真学报, 2021, 33(10): 2518-2531.
[5]	熊最, 王可人, 金虎, 冯辉. 一种基于干扰对齐的多跳网络吞吐量优化模型[J]. 系统仿真学报, 2015, 27(6): 1240-1246.