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

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

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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

Competing Interests

The authors declare that they have no competing interests.

RIGHTS & PERMISSIONS

2023 Higher Education Press