A hybrid learning-assisted multi-parallel algorithm for a large-scale satellite-ground networking optimization problem

Abstract

The rapid expansion of satellite Internet deployments, driven by the rise of Space-Ground Integration Network (SGIN) construction, has led to a significant increase in satellite numbers. To address the challenge of efficient networking between large-scale satellites and limited ground station resources, this paper presents a hybrid learning-assisted multi-parallel algorithm (HLMP). The HLMP features a multi-parallel solving and deconflicting framework, a learning-assisted metaheuristic (LM) algorithm combining reinforcement learning (RL) and Tabu simulated annealing (TSA), and a linear programming (LP) exact-solving algorithm. The framework first divides the problem into parallel sub-problems based on the time domain, then applies LM and LP to solve each sub-problem in parallel. LM uses LP-generated scheduling results to improve its own accuracy. The deconflicting strategy integrates and refines the planning results from all sub-problems, ensuring an optimized outcome. HLMP advances beyond traditional task-driven satellite scheduling methods by offering a novel approach for optimizing large-scale satellite-ground networks under the new macro paradigm of “maximizing linkage to the greatest extent feasible.” Experimental cases involving up to 1,000 satellites and 100 ground stations highlight HLMP’s efficiency. Comparative experiments with other metaheuristic algorithms and the CPLEX solver further demonstrate HLMP’s ability to generate high-quality solutions more quickly.

Graphical abstract

Keywords

satellite–ground networking / multi-parallel framework / metaheuristics / reinforcement learning / linear programming

References

[1] Barbulescu L, Watson J P, Whitley L D, Howe A E, (2004). Scheduling space–ground communications for the air force satellite control network. Journal of Scheduling, 7( 1): 7–34

[2] Chen M, Du Y, Tang K, Xing L, Chen Y, Chen Y, (2024). Learning to construct a solution for the agile satellite scheduling problem with time-dependent transition times. IEEE Transactions on Systems, Man, and Cybernetics. Systems, 54( 10): 5949–5963

[3] del Portillo I, Cameron B G, Crawley E F, (2019). A technical comparison of three low earth orbit satellite constellation systems to provide global broadband. Acta Astronautica, 159: 123–135

[4] Doltsinis S, Ferreira P, Lohse N, (2014). An MDP model-based reinforcement learning approach for production station ramp-up optimization: Q-learning analysis. IEEE Transactions on Systems, Man, and Cybernetics. Systems, 44( 9): 1125–1138

[5] Dorigo M, Birattari M, Stutzle T, (2006). Ant colony optimization. IEEE Computational Intelligence Magazine, 1( 4): 28–39

[6] Du Y, Wang L, Xing L, Yan J, Cai M, (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

[7] Du Y, Wang T, Xin B, Wang L, Chen Y, Xing L, (2020). A data-driven parallel scheduling approach for multiple agile earth observation satellites. IEEE Transactions on Evolutionary Computation, 24( 4): 679–693

[8] Du Y, Xing L, Chen Y, (2022). Satellite scheduling engine: The intelligent solver for future multi-satellite management. Frontiers of Engineering Management, 9( 4): 683–688

[9] Du Y, Xing L, Zhang J, Chen Y, He Y, (2019). MOEA based memetic algorithms for multi-objective satellite range scheduling problem. Swarm and Evolutionary Computation, 50: 100576

[10] Glover F, (1986). Future paths for integer programming and links to artificial intelligence. Computers & Operations Research, 13( 5): 533–549

[11] He H, Zhou D, Sheng M, Li J, (2023). Hierarchical cross-domain satellite resource management: An intelligent collaboration perspective. IEEE Transactions on Communications, 71( 4): 2201–2215

[12] HollandJ H (1992). Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT press

[13] Hooker J N, (2015). Toward unification of exact and heuristic optimization methods. International Transactions in Operational Research, 22( 1): 19–48

[14] Kirkpatrick S, Gelatt Jr C D, Vecchi M P, (1983). Optimization by simulated annealing. Science, 220( 4598): 671–680

[15] Kodheli O, Lagunas E, Maturo N, Sharma S K, Shankar B, Montoya J F M, Duncan J C M, Spano D, Chatzinotas S, Kisseleff S, Querol J, Lei L, Vu T X, Goussetis G, (2021). Satellite communications in the new space era: A survey and future challenges. IEEE Communications Surveys and Tutorials, 23( 1): 70–109

[16] Li R, Gong W, Lu C, Wang L, (2023). A learning-based memetic algorithm for energy-efficient flexible job-shop scheduling with type-2 fuzzy processing time. IEEE Transactions on Evolutionary Computation, 27( 3): 610–620

[17] Li S, Gong W, Wang L, Gu Q, (2024). Evolutionary multitasking via reinforcement learning. IEEE Transactions on Emerging Topics in Computational Intelligence, 8( 1): 762–775

[18] Lin X, Chen Y, Xue J, Zhang B, Chen Y, Chen C, (2024a). Parallel machine scheduling with job family, release time, and mold availability constraints: model and two solution approaches. Memetic Computing, 16( 3): 355–371

[19] Lin X, Chen Y, Xue J, Zhang B, He L, Chen Y, (2024b). Large-volume LEO satellite imaging data networked transmission scheduling problem: Model and algorithm. Expert Systems with Applications, 249: 123649

[20] Liu X, Laporte G, Chen Y, He R, (2017). An adaptive large neighborhood search metaheuristic for agile satellite scheduling with time-dependent transition time. Computers & Operations Research, 86: 41–53

[21] Liu Y, Zhang S, Hu H, (2022). A simulated annealing algorithm with tabu list for the multi-satellite downlink schedule problem considering waiting time. Aerospace, 9( 5): 235

[22] Liu Z, Feng Z, Ren Z, (2019). Route-reduction-based dynamic programming for large-scale satellite range scheduling problem. Engineering Optimization, 51( 11): 1944–1964

[23] Luo K, Wang H, Li Y, Li Q, (2017). High-performance technique for satellite range scheduling. Computers & Operations Research, 85: 12–21

[24] Marinelli F, Nocella S, Rossi F, Smriglio S, (2011). A Lagrangian heuristic for satellite range scheduling with resource constraints. Computers & Operations Research, 38( 11): 1572–1583

[25] Moon J, (2021). Generalized risk-sensitive optimal control and Hamilton–Jacobi–Bellman equation. IEEE Transactions on Automatic Control, 66( 5): 2319–2325

[26] PuchingerJRaidlG R (2005). Combining metaheuristics and exact algorithms in combinatorial optimization: A survey and classification. In: International Work-Conference on the Interplay between Natural and Artificial Computation. Berlin, Heidelberg: Springer Berlin Heidelberg, 41–53

[27] Ren L, Ning X, Wang Z, (2022). A competitive Markov decision process model and a recursive reinforcement-learning algorithm for fairness scheduling of agile satellites. Computers & Industrial Engineering, 169: 108242

[28] Shiue Y R, Lee K C, Su C T, (2018). Real-time scheduling for a smart factory using a reinforcement learning approach. Computers & Industrial Engineering, 125: 604–614

[29] Song Y, Ou J, Wu J, Wu Y, Xing L, Chen Y, (2023a). A cluster-based genetic optimization method for satellite range scheduling system. Swarm and Evolutionary Computation, 79: 101316

[30] Song Y, Wei L, Yang Q, Wu J, Xing L, Chen Y, (2023b). RL-GA: A reinforcement learning-based genetic algorithm for electromagnetic detection satellite scheduling problem. Swarm and Evolutionary Computation, 77: 101236

[31] Song Y J, Zhang Z S, Song B Y, Chen Y W, (2019). Improved genetic algorithm with local search for satellite range scheduling system and its application in environmental monitoring. Sustainable Computing: Informatics and Systems, 21: 19–27

[32] Su J, Fu Y, Gao K, Dong H, Mou J, (2023). Integrated scheduling problems of open shop and vehicle routing using an ensemble of group teaching optimization and simulated annealing. Swarm and Evolutionary Computation, 83: 101373

[33] Wang J, Song G, Liang Z, Demeulemeester E, Hu X, Liu J, (2023). Unrelated parallel machine scheduling with multiple time windows: An application to earth observation satellite scheduling. Computers & Operations Research, 149: 106010

[34] Wang L, Li K, Ma Q, Lu Y, (2020). Hybrid dynamic learning mechanism for multivariate time series segmentation. Statistical Analysis and Data Mining, 13( 2): 165–177

[35] Wang L, Lu J, (2019). A memetic algorithm with competition for the capacitated green vehicle routing problem. IEEE/CAA Journal of Automatica Sinica, 6( 2): 516–526

[36] Wang L, Pan Z, Wang J, (2021b). A review of reinforcement learning based intelligent optimization for manufacturing scheduling. Complex System Modeling and Simulation, 1( 4): 257–270

[37] Wang L, Wang J, Jiang E, (2021a). Decomposition based multiobjective evolutionary algorithm with adaptive resource allocation for energy-aware welding shop scheduling problem. Computers & Industrial Engineering, 162: 107778

[38] Wu J, Song B, Zhang G, Ou J, Chen Y, Yao F, He L, Xing L, (2022). A data-driven improved genetic algorithm for agile earth observation satellite scheduling with time-dependent transition time. Computers & Industrial Engineering, 174: 108823

[39] Wu J, Yao F, Song Y, He L, Lu F, Du Y, Yan J, Chen Y, Xing L, Ou J, (2023). Frequent pattern-based parallel search approach for time-dependent agile earth observation satellite scheduling. Information Sciences, 636: 118924

[40] Yao F, Du Y, Li L, Xing L, Chen Y, (2023). General modeling and optimization technique for real-world earth observation satellite scheduling. Frontiers of Engineering Management, 10( 4): 695–709

[41] Yu Y, Sun W, Tang J, Wang J, (2017). Line-hybrid seru system conversion: Models, complexities, properties, solutions and insights. Computers & Industrial Engineering, 103: 282–299

[42] Zhao F, Jiang T, Wang L, (2023). A reinforcement learning driven cooperative meta-heuristic algorithm for energy-efficient distributed no-wait flow-shop scheduling with sequence-dependent setup time. IEEE Transactions on Industrial Informatics, 19( 7): 8427–8440

[43] Zhou L, Liang Z, Chou C A, Chaovalitwongse W A, (2020). Airline planning and scheduling: Models and solution methodologies. Frontiers of Engineering Management, 7( 1): 1–26

[44] Zhu W, Ao Z, Baldacci R, Qin H, Zhang Z, (2023). Enhanced solution representations for vehicle routing problems with split deliveries. Frontiers of Engineering Management, 10( 3): 483–498

RIGHTS & PERMISSIONS

Higher Education Press