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%.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Air Force Office of Scientific Research (2003). Exploiting elementary landscapes for search (AFSCN scheduling problems)
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
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
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
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
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
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
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
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
Lemaître M, Verfaillie G, Jouhaud F (2000). How to manage the new generation of agile earth observation satellites. In: Proceedings of the 6th International SpaceOps Symposium. Toulouse: AIAA, 1–8
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
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
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
Moscato P (1989). On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms. Caltech ConCurrent Computation Program 158–79. Pasadena, CA: California Institute of Technology
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
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
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
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
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
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
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
Yang C F (2021). Innovation and development of BeiDou Navigation Satellite System (BDS) project management mode. Frontiers of Engineering Management, 8(2): 312–320
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
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Competing Interests The authors declare that they have no competing interests.
Additional information
This work was supported by the National Natural Science Foundation of China (Grant No. 72201272), the Technical Field Foundation in 173 Program of National Defense Technology (Grant No. 2021-JCJQ-JJ-0049), and the Science Foundation of National University of Defense Technology (Grant No. ZK22-48).
Rights and permissions
About this article
Cite this article
Yao, F., Du, Y., Li, L. et al. General modeling and optimization technique for real-world earth observation satellite scheduling. Front. Eng. Manag. 10, 695–709 (2023). https://doi.org/10.1007/s42524-023-0263-3
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s42524-023-0263-3