Earth Observation Satellites (EOSs) are crucial for tasks like environmental monitoring and resource management. The new generation of Agile Earth Observation Satellites (AEOSs) offers enhanced flexibility but introduces immense complexity to scheduling, making it an NP-hard problem. While heuristic algorithms like Adaptive Large Neighborhood Search (ALNS) are effective, their performance heavily relies on manually designed "destroy heuristics"—the rules for how to intelligently break and rebuild a potential schedule. This design process is a significant bottleneck, requiring deep human expertise.

To overcome this, a research team has pioneered a new method that uses Large Language Models (LLMs) to automatically design and evolve these critical heuristics. Their proposed algorithm, evALNS, leverages the creative power of LLMs to generate novel and efficient scheduling strategies.

Recognizing that LLMs lack the specialized domain knowledge for such a complex problem, the researchers introduced an innovative Dual-Population Co-Evolutionary Computing Framework (DPEC). This framework sets up two evolving populations of heuristics: one generated by the LLM and another seeded with proven, expert-designed rules. The two populations periodically exchange their best-performing individuals, allowing the LLM to learn from the expert strategies and fuse that knowledge into its own creative solutions. This process is further enhanced by a Functional Natural Language Embedding (FNLE) strategy, where natural language descriptions embedded in the code help the LLM better "understand" the logic and purpose of the heuristics it evolves.

Extensive experiments showed that the evALNS algorithm, powered by the DPEC framework, significantly outperformed a traditional ALNS using only expert-designed operators. The new approach achieved an average profit improvement of 8.48% across various complex scenarios. This work not only provides a more effective solution for satellite scheduling but also establishes a powerful new paradigm for using LLMs to automate the design of sophisticated algorithms for other complex real-world optimization problems.

The work titled “LLM-assisted adaptive large neighborhood search for agile earth observation satellite scheduling”, was published on ENGINEERING Management (published on Oct 26, 2025).
DOI：10.1007/s42524-026-5124-4