General modeling and optimization technique for real-world earth observation satellite scheduling

Feng YAO, Yonghao DU, Lei LI, Lining XING, Yingguo CHEN

PDF(5774 KB)
PDF(5774 KB)
Front. Eng ›› 2023, Vol. 10 ›› Issue (4) : 695-709. DOI: 10.1007/s42524-023-0263-3
RESEARCH ARTICLE

General modeling and optimization technique for real-world earth observation satellite scheduling

Author information +
History +

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%.

Graphical abstract

Keywords

earth observation satellite / scheduling / general technique / optimization algorithm / commercial constellation / real-world / benchmark

Cite this article

Download citation ▾
Feng YAO, Yonghao DU, Lei LI, Lining XING, Yingguo CHEN. General modeling and optimization technique for real-world earth observation satellite scheduling. Front. Eng, 2023, 10(4): 695‒709 https://doi.org/10.1007/s42524-023-0263-3

References

[1]
Air Force Office of Scientific Research (2003). Exploiting elementary landscapes for search (AFSCN scheduling problems)
[2]
Chu, X G Chen, Y N Tan, Y J (2017). An anytime branch and bound algorithm for agile earth observation satellite onboard scheduling. Advances in Space Research, 60( 9): 2077–2090
CrossRef Google scholar
[3]
Cordeau, J F Laporte, G (2005). Maximizing the value of an earth observation satellite orbit. Journal of the Operational Research Society, 56( 8): 962–968
CrossRef Google scholar
[4]
Du, Y H Wang, L Xing, L N Yan, J G Cai, M S (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
CrossRef Google scholar
[5]
Du, Y H Wang, T Xin, B Wang, L Chen, Y G Xing, L N (2020). A data-driven parallel scheduling approach for multiple agile earth observation satellites. IEEE Transactions on Evolutionary Computation, 24( 4): 679–693
CrossRef Google scholar
[6]
Du, Y H Xing, L N Chen, Y G (2022). Satellite scheduling engine: The intelligent solver for future multi-satellite management. Frontiers of Engineering Management, 9( 4): 683–688
CrossRef Google scholar
[7]
He, L Liu, X L Laporte, G Chen, Y W Chen, Y G (2018). An improved adaptive large neighborhood search algorithm for multiple agile satellites scheduling. Computers & Operations Research, 100: 12–25
CrossRef Google scholar
[8]
He, Y M Xing, L N Chen, Y W Pedrycz, W Wang, L Wu, G (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
CrossRef Google scholar
[9]
Jang, J Choi, J Bae, H J Choi, I C (2013). Image collection planning for Korea Multi-Purpose SATellite-2. European Journal of Operational Research, 230( 1): 190–199
CrossRef Google scholar
[10]
LemaîtreMVerfaillieGJouhaudF (2000). How to manage the new generation of agile earth observation satellites. In: Proceedings of the 6th International SpaceOps Symposium. Toulouse: AIAA, 1–8
[11]
Liu, X L Laporte, G Chen, Y W He, R J (2017). An adaptive large neighborhood search metaheuristic for agile satellite scheduling with time-dependent transition time. Computers & Operations Research, 86: 41–53
CrossRef Google scholar
[12]
Luo, K P Wang, H H Li, Y J Li, Q (2017). High-performance technique for satellite range scheduling. Computers & Operations Research, 85: 12–21
CrossRef Google scholar
[13]
Mok, S H Jo, S Bang, H Leeghim, H (2019). Heuristic-based mission planning for an agile earth observation satellite. International Journal of Aeronautical and Space Sciences, 20( 3): 781–791
CrossRef Google scholar
[14]
MoscatoP (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]
Nag, S Li, A S Merrick, J H (2018). Scheduling algorithms for rapid imaging using agile Cubesat constellations. Advances in Space Research, 61( 3): 891–913
CrossRef Google scholar
[16]
Peng, G S Dewil, R Verbeeck, C Gunawan, A Xing, L N Vansteenwegen, P (2019). Agile earth observation satellite scheduling: An orienteering problem with time-dependent profits and travel times. Computers & Operations Research, 111: 84–98
CrossRef Google scholar
[17]
Peng, G S Song, G P Xing, L N Gunawan, A Vansteenwegen, P (2020). An exact algorithm for agile earth observation satellite scheduling with time-dependent profits. Computers & Operations Research, 120: 104946
CrossRef Google scholar
[18]
Valicka, C G Garcia, D Staid, A Watson, J P Hackebeil, G Rathinam, S Ntaimo, L (2019). Mixed-integer programming models for optimal constellation scheduling given cloud cover uncertainty. European Journal of Operational Research, 275( 2): 431–445
CrossRef Google scholar
[19]
Wang, J J Demeulemeester, E Hu, X J Wu, G H (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
CrossRef Google scholar
[20]
Wu, G Liu, J Ma, M Qiu, D S (2013). A two-phase scheduling method with the consideration of task clustering for earth observing satellites. Computers & Operations Research, 40( 7): 1884–1894
CrossRef Google scholar
[21]
Xiao, Y Y Zhang, S Y Yang, P You, M Huang, J Y (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
CrossRef Google scholar
[22]
Yang, C F (2021). Innovation and development of BeiDou Navigation Satellite System (BDS) project management mode. Frontiers of Engineering Management, 8( 2): 312–320
CrossRef Google scholar
[23]
Zhu, W M Hu, X X Xia, W Jin, P (2019). A two-phase genetic annealing method for integrated earth observation satellite scheduling problems. Soft Computing, 23( 1): 181–196
CrossRef Google scholar

Competing Interests

The authors declare that they have no competing interests.

RIGHTS & PERMISSIONS

2023 Higher Education Press
AI Summary AI Mindmap
PDF(5774 KB)

Accesses

Citations

Detail

Sections
Recommended

/