Systems Engineering Theory and Application |
|
|
|
General modeling and optimization technique for real-world earth observation satellite scheduling |
Feng YAO1, Yonghao DU1(), Lei LI1, Lining XING2, Yingguo CHEN1 |
1. College of Systems Engineering, National University of Defense Technology, Changsha 410073, China 2. School of Electronic Engineering, Xidian University, Xi’an 710075, China |
|
|
Abstract Over the last two decades, many modeling and optimization techniques have been developed for earth observation satellite (EOS) scheduling problems, but few of them show good generality to be engineered in real-world applications. This study proposes a general modeling and optimization technique for common and real-world EOS scheduling cases; it includes a decoupled framework, a general modeling method, and an easy-to-use algorithm library. In this technique, a framework that decouples the modeling, constraints, and optimization of EOS scheduling problems is built. With this framework, the EOS scheduling problems are appropriately modeled in a general manner, where the executable opportunity, another format of the well-known visible time window per EOS operation, is viewed as a selectable resource to be optimized. On this basis, 10 types of optimization algorithms, such as Tabu search and genetic algorithm, and a parallel competitive memetic algorithm, are developed. For simplified EOS scheduling problems, the proposed technique shows better performance in applicability and effectiveness than the state-of-the-art algorithms. In addition, a complicatedly constrained real-world benchmark exampled by a four-EOS Chinese commercial constellation is provided, and the technique is qualified and outperforms the in-use scheduling system by more than 50%.
|
Keywords
earth observation satellite
scheduling
general technique
optimization algorithm
commercial constellation
real-world
benchmark
|
Corresponding Author(s):
Yonghao DU
|
Just Accepted Date: 04 July 2023
Online First Date: 09 August 2023
Issue Date: 07 December 2023
|
|
1 |
Air Force Office of Scientific Research (2003). Exploiting elementary landscapes for search (AFSCN scheduling problems)
|
2 |
X G Chu, Y N Chen, Y J Tan, (2017). An anytime branch and bound algorithm for agile earth observation satellite onboard scheduling. Advances in Space Research, 60( 9): 2077–2090
https://doi.org/10.1016/j.asr.2017.07.026
|
3 |
J F Cordeau, G Laporte, (2005). Maximizing the value of an earth observation satellite orbit. Journal of the Operational Research Society, 56( 8): 962–968
https://doi.org/10.1057/palgrave.jors.2601926
|
4 |
Y H Du, L Wang, L N Xing, J G Yan, M S Cai, (2021). Data-driven heuristic assisted memetic algorithm for efficient inter-satellite link scheduling in the BeiDou navigation satellite system. IEEE/CAA Journal of Automatica Sinica, 8( 11): 1800–1816
https://doi.org/10.1109/JAS.2021.1004174
|
5 |
Y H Du, T Wang, B Xin, L Wang, Y G Chen, L N Xing, (2020). A data-driven parallel scheduling approach for multiple agile earth observation satellites. IEEE Transactions on Evolutionary Computation, 24( 4): 679–693
https://doi.org/10.1109/TEVC.2019.2934148
|
6 |
Y H Du, L N Xing, Y G Chen, (2022). Satellite scheduling engine: The intelligent solver for future multi-satellite management. Frontiers of Engineering Management, 9( 4): 683–688
https://doi.org/10.1007/s42524-022-0222-4
|
7 |
L He, X L Liu, G Laporte, Y W Chen, Y G Chen, (2018). An improved adaptive large neighborhood search algorithm for multiple agile satellites scheduling. Computers & Operations Research, 100: 12–25
https://doi.org/10.1016/j.cor.2018.06.020
|
8 |
Y M He, L N Xing, Y W Chen, W Pedrycz, L Wang, G Wu, (2022). A generic Markov decision process model and reinforcement learning method for scheduling agile earth observation satellites. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 52( 3): 1463–1474
https://doi.org/10.1109/TSMC.2020.3020732
|
9 |
J Jang, J Choi, H J Bae, I C Choi, (2013). Image collection planning for Korea Multi-Purpose SATellite-2. European Journal of Operational Research, 230( 1): 190–199
https://doi.org/10.1016/j.ejor.2013.04.009
|
10 |
M LemaîtreG VerfaillieF (2000) Jouhaud. How to manage the new generation of agile earth observation satellites. In: Proceedings of the 6th International SpaceOps Symposium. Toulouse: AIAA, 1–8
|
11 |
X L Liu, G Laporte, Y W Chen, R J He, (2017). An adaptive large neighborhood search metaheuristic for agile satellite scheduling with time-dependent transition time. Computers & Operations Research, 86: 41–53
https://doi.org/10.1016/j.cor.2017.04.006
|
12 |
K P Luo, H H Wang, Y J Li, Q Li, (2017). High-performance technique for satellite range scheduling. Computers & Operations Research, 85: 12–21
https://doi.org/10.1016/j.cor.2017.03.012
|
13 |
S H Mok, S Jo, H Bang, H Leeghim, (2019). Heuristic-based mission planning for an agile earth observation satellite. International Journal of Aeronautical and Space Sciences, 20( 3): 781–791
https://doi.org/10.1007/s42405-018-0105-4
|
14 |
P Moscato (1989). On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms. Caltech Con-Current Computation Program 158-79. Pasadena, CA: California Institute of Technology
|
15 |
S Nag, A S Li, J H Merrick, (2018). Scheduling algorithms for rapid imaging using agile Cubesat constellations. Advances in Space Research, 61( 3): 891–913
https://doi.org/10.1016/j.asr.2017.11.010
|
16 |
G S Peng, R Dewil, C Verbeeck, A Gunawan, L N Xing, P Vansteenwegen, (2019). Agile earth observation satellite scheduling: An orienteering problem with time-dependent profits and travel times. Computers & Operations Research, 111: 84–98
https://doi.org/10.1016/j.cor.2019.05.030
|
17 |
G S Peng, G P Song, L N Xing, A Gunawan, P Vansteenwegen, (2020). An exact algorithm for agile earth observation satellite scheduling with time-dependent profits. Computers & Operations Research, 120: 104946
https://doi.org/10.1016/j.cor.2020.104946
|
18 |
C G Valicka, D Garcia, A Staid, J P Watson, G Hackebeil, S Rathinam, L Ntaimo, (2019). Mixed-integer programming models for optimal constellation scheduling given cloud cover uncertainty. European Journal of Operational Research, 275( 2): 431–445
https://doi.org/10.1016/j.ejor.2018.11.043
|
19 |
J J Wang, E Demeulemeester, X J Hu, G H Wu, (2020). Expectation and SAA models and algorithms for scheduling of multiple earth observation satellites under the impact of clouds. IEEE Systems Journal, 14( 4): 5451–5462
https://doi.org/10.1109/JSYST.2019.2961236
|
20 |
G Wu, J Liu, M Ma, D S Qiu, (2013). A two-phase scheduling method with the consideration of task clustering for earth observing satellites. Computers & Operations Research, 40( 7): 1884–1894
https://doi.org/10.1016/j.cor.2013.02.009
|
21 |
Y Y Xiao, S Y Zhang, P Yang, M You, J Y Huang, (2019). A two-stage flow-shop scheme for the multi-satellite observation and data-downlink scheduling problem considering weather uncertainties. Reliability Engineering & System Safety, 188: 263–275
https://doi.org/10.1016/j.ress.2019.03.016
|
22 |
C F Yang, (2021). Innovation and development of BeiDou Navigation Satellite System (BDS) project management mode. Frontiers of Engineering Management, 8( 2): 312–320
https://doi.org/10.1007/s42524-021-0155-3
|
23 |
W M Zhu, X X Hu, W Xia, P Jin, (2019). A two-phase genetic annealing method for integrated earth observation satellite scheduling problems. Soft Computing, 23( 1): 181–196
https://doi.org/10.1007/s00500-017-2889-8
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|