LLM-assisted adaptive large neighborhood search for agile earth observation satellite scheduling

Abstract

The Agile Earth Observation Satellite Scheduling Problem (AEOSSP) is a complex NP-hard challenge that involves selecting, sequencing, and timing observation tasks to maximize imaging profits while adhering to various constraints. In our study, we developed a mixed-integer programming model for AEOSSP, incorporating key constraints related to visible time windows and time dependencies. To tackle this, we propose an Evolutionary Adaptive Large Neighborhood Search Algorithm (evALNS) enhanced by Large Language Models (LLMs). Our work pioneers the application of LLMs to ALNS by being the first to automatically develop and evolve its critical destroy heuristics. However, a naive application of LLMs is insufficient for such a complex domain. We therefore introduce a novel Dual-Population Co-Evolutionary Computing Framework (DPEC) to bridge the LLM’s knowledge gap by synergizing LLM-generated heuristics with expert-designed ones. This co-evolution, guided by a Functional Natural Language Embedding (FNLE) strategy and customized prompts, significantly enhances the adaptability and efficiency of ALNS. Extensive numerical experiments demonstrated the superiority of the evALNS evolved under our framework, achieving an average profit improvement of 8.48% compared to the original ALNS with expert-designed destroy operators.

Graphical abstract

Keywords

large language model / algorithm design / adaptive large neighborhood search / satellite scheduling

References

[1] Chatterjee A, Tharmarasa R, (2024). Multi-stage optimization framework of satellite scheduling for large areas of interest. Advances in Space Research, 73( 3): 2024–2039

[2] Chen C, Li L, Du Y, Yao F, Xing L, (2025a). A hybrid learning-assisted multi-parallel algorithm for a large-scale satellite-ground networking optimization problem. Engineering Management, 12( 4): 1157–1174

[3] Chen M, Du Y, Tang K, Xing L, Chen Y, Chen Y, (2024a). 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

[4] Chen X, Gao L, Zhang M, Chen C, Yan S, (2024b). Spectral-spatial adversarial multi-domain synthesis network for cross-scene hyperspectral image classification. IEEE Transactions on Geoscience and Remote Sensing, 62: 1–16

[5] Chen X, Zhang M, Liu Y, (2024c). Target detection with spectral graph contrast clustering assignment and spectral graph transformer in hyperspectral imagery. IEEE Transactions on Geoscience and Remote Sensing, 62: 1–16

[6] Chen Y, Zhang H, Li C, Chi B, Chen X, Wu J, (2025b). Large language model empowered smart city mobility. Engineering Management, 12( 1): 201–207

[7] Ding N, Qin Y, Yang G, Wei F, Yang Z, Su Y, Hu S, Chen Y, Chan C M, Chen W, Yi J, Zhao W, Wang X, Liu Z, Zheng H T, Chen J, Liu Y, Tang J, Li J, Sun M, (2023). Parameter-efficient fine-tuning of large-scale pre-trained language models. Nature Machine Intelligence, 5( 3): 220–235

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

[9] 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

[10] 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

[11] Fan WDing YNing LWang SLi HYin DChua T SLi Q (2024). A survey on rag meeting llms: Towards retrieval-augmented large language models. In: Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining: 6491–6501

[12] Gao YXiong YGao XJia KPan JBi YDai YSun JWang H (2023). Retrieval-augmented generation for large language models: A survey. Preprint at arXiv. arXiv:2312.10997

[13] Han C, Gu Y, Wu G, Wang X, (2023). Simulated annealing-based heuristic for multiple agile satellites scheduling under cloud coverage uncertainty. IEEE Transactions on Systems, Man, and Cybernetics. Systems, 53( 5): 2863–2874

[14] He L, De Weerdt M, Yorke-Smith N, (2020). Time/sequence-dependent scheduling: the design and evaluation of a general purpose tabu-based adaptive large neighbourhood search algorithm. Journal of Intelligent Manufacturing, 31( 4): 1051–1078

[15] He L, Liu X, Laporte G, Chen Y, Chen Y, (2018). An improved adaptive large neighborhood search algorithm for multiple agile satellites scheduling. Computers & Operations Research, 100: 12–25

[16] Herrmann A, Schaub H, (2023). Reinforcement learning for the agile earth-observing satellite scheduling problem. IEEE Transactions on Aerospace and Electronic Systems, 59( 5): 5235–5247

[17] Jia S, Deng L, Zhao Q, Chen Y, (2023). An adaptive large neighborhood search heuristic for multi-commodity two-echelon vehicle routing problem with satellite synchronization. Journal of Industrial and Management Optimization, 19( 2): 1187–1210

[18] Kaddour JHarris JMozes MBradley HRaileanu RMcHardy R (2023). Challenges and applications of large language models. Preprint at arXiv. arXiv:2307.10169

[19] Kasneci E, Sessler K, Küchemann S, Bannert M, Dementieva D, Fischer F, Gasser U, Groh G, Günnemann S, Hüllermeier E, Krusche S, Kutyniok G, Michaeli T, Nerdel C, Pfeffer J, Poquet O, Sailer M, Schmidt A, Seidel T, Stadler M, Weller J, Kuhn J, Kasneci G, (2023). ChatGPT for good? On opportunities and challenges of large language models for education. Learning and Individual Differences, 103: 102274

[20] Li R, Gong W, Wang L, Lu C, Zhuang X, (2023). Surprisingly popular-based adaptive memetic algorithm for energy-efficient distributed flexible job shop scheduling. IEEE Transactions on Cybernetics, 53( 12): 8013–8023

[21] Li R, Wang L, Gong W, Ming F, (2025). An evolutionary multitasking memetic algorithm for multiobjective distributed heterogeneous welding flow shop scheduling. IEEE Transactions on Evolutionary Computation, 29( 6): 2287–2298

[22] Liu FLiu YShi LHuang HWang RYang ZZhang LLi ZMa Y (2024a). Exploring and evaluating hallucinations in LLM-powered code generation. Preprint at arXiv. arXiv:2404.00971

[23] Liu FTong XYuan MLin XLuo FWang ZLu ZZhang Q (2024b). Evolution of heuristics: towards efficient automatic algorithm design using large language lodel. In: Forty-first International Conference on Machine Learning. PMLR 235, 32201–32223

[24] Liu FTong XYuan MZhang Q (2023a). Algorithm evolution using large language model. Preprint at arXiv. arXiv:2311.15249

[25] Liu SChen CQu XTang KOng Y S (2024c). Large language models as evolutionary optimizers. In: 2024 IEEE Congress on Evolutionary Computation (CEC), 1–8

[26] 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

[27] Liu Y, Roberto B, Zhou J, Yu Y, Zhang Y, Sun W, (2023b). Efficient feasibility checks and an adaptive large neighborhood search algorithm for the time-dependent green vehicle routing problem with time windows. European Journal of Operational Research, 310( 1): 133–155

[28] Liu Z, Liu J, Liu X, Yang W, Wu J, Chen Y, (2024d). Knowledge-assisted adaptive large neighbourhood search algorithm for the satellite–ground link scheduling problem. Computers & Industrial Engineering, 192: 110219

[29] Ou J, Xing L, Yao F, Li M, Lv J, He Y, Song Y, Wu J, Zhang G, (2023). Deep reinforcement learning method for satellite range scheduling problem. Swarm and Evolutionary Computation, 77: 101233

[30] Pan Z, Wang L, Dong C, Chen J F, (2024). A knowledge-guided end-to-end optimization framework based on reinforcement learning for flow shop scheduling. IEEE Transactions on Industrial Informatics, 20( 2): 1853–1861

[31] Pan Z, Wang L, Wang J, Zhang Q, (2025). A bi-learning evolutionary algorithm for transportation-constrained and distributed energy-efficient flexible scheduling. IEEE Transactions on Evolutionary Computation, 29( 1): 232–246

[32] Peng G, Song G, Xing L, Gunawan A, Vansteenwegen P, (2020). An exact algorithm for agile earth observation satellite scheduling with time-dependent profits. Computers & Operations Research, 120: 104946

[33] Pluhacek MKazikova AKadavy TViktorin ASenkerik R (2023). Leveraging large language models for the generation of novel metaheuristic optimization algorithms. In: Proceedings of the Companion Conference on Genetic and Evolutionary Computation, 1812–1820

[34] Kandepi R, Saini H, George R K, Konduri S, Karidhal R, (2024). Agile earth observation satellite constellations scheduling for large area target imaging using heuristic search. Acta Astronautica, 219: 670–677

[35] Song Y, Ou J, Suganthan P N, Pedrycz W, Yang Q, Xing L, (2023). Learning adaptive genetic algorithm for earth electromagnetic satellite scheduling. IEEE Transactions on Aerospace and Electronic Systems, 59( 6): 9010–9025

[36] Song Y, Suganthan P N, Pedrycz W, Yan R, Fan D, Zhang Y, (2024). Energy-efficient satellite range scheduling using a reinforcement learning-based memetic algorithm. IEEE Transactions on Aerospace and Electronic Systems, 60( 4): 4073–4087

[37] Thirunavukarasu A J, Ting D S J, Elangovan K, Gutierrez L, Tan T F, Ting D S W, (2023). Large language models in medicine. Nature Medicine, 29( 8): 1930–1940

[38] Vaithilingam PZhang TGlassman E L (2022). Expectation vs. experience: Evaluating the usability of code generation tools powered by large language models. In: Chi Conference on Human Factors in Computing Systems, Extended Abstracts. New Orleans: ACM, 2022: 1-7

[39] Stein N, Bäck T, (2025). Llamea: A large language model evolutionary algorithm for automatically generating metaheuristics. IEEE Transactions on Evolutionary Computation, 29( 2): 331–345

[40] Wang X, Wang L, Dong C, Ren H, Xing K, (2024). Reinforcement learning-based dynamic order recommendation for on-demand food delivery. Tsinghua Science and Technology, 29( 2): 356–367

[41] Wang X, Wu G, Xing L, Pedrycz W, (2021). Agile earth observation satellite scheduling over 20 years: Formulations, methods, and future directions. IEEE Systems Journal, 15( 3): 3881–3892

[42] Wong T T, Yeh P Y, (2020). Reliable accuracy estimates from k-Fold cross validation. IEEE Transactions on Knowledge and Data Engineering, 32( 8): 1586–1594

[43] Wu G, Xiang Z, Wang Y, Gu Y, Pedrycz W, (2024a). Improved adaptiv large neighborhood search algorithm based on the two-stage framework for scheduling multiple super-agile satellites. IEEE Transactions on Aerospace and Electronic Systems, 60( 5): 7185–7200

[44] 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

[45] 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

[46] Wu Y, Wang L, Chen J, Zheng J, Pan Z, (2024b). A reinforcement learning driven two-stage evolutionary optimisation for hybrid seru system scheduling with worker transfer. International Journal of Production Research, 62( 11): 3952–3971

[47] Xhafa F, Sun J, Barolli A, Biberaj A, Barolli L, (2012). Genetic algorithms for satellite scheduling problems. Mobile Information Systems, 8( 4): 351–377

[48] Yang C, (2021). Innovation and development of BeiDou Navigation Satellite System (BDS) project management mode. Engineering Management, 8( 2): 312–320

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

[50] Ye HXu HYan ACheng Y (2025). Large language model-driven large neighborhood search for large-scale MILP problems. In: 42nd International Conference on Machine Learning, Vienna, Austria, July 14-20, 2025

[51] Zhang M RDesai NBae JLorraine JBa J (2023). Using large language models for hyperparameter optimization. In: NeurIPS 2023 Foundation Models for Decision Making, New Orleans, LA, USA, December 10-16, 2023

[52] Zhao W XZhou KLi JTang TWang XHou YMin YZhang BZhang JDong ZDu YYang CChen YChen ZJiang JRen RLi YTang XLiu ZLiu PNie J YWen J R (2023). A survey of large language models. Preprint at arXiv. arXiv:2303.18223

RIGHTS & PERMISSIONS

Higher Education Press