2026-10-10T21:17:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27708 2026-10-10T19:48:19Z ddc:004 open_access

Earth Observation Satellite Constellation Planning with Matheuristics and Metaheuristics Combination Barrault, Romain Pralet, Cedric Picard, Gauthier Sawyer, Eric Scheduling Earth Observation Satellite Matheuristic Metaheuristic Linear Programming A standard problem in the field of Earth observation is the scheduling of the observations of an agile satellite constellation. Given a set of end-user requests over Points Of Interest (POIs), it consists in selecting observations among the candidate ones, attributing each of them to a satellite, and defining the sequence of observations planned for each satellite given operational constraints. The latter are related to the visibility windows available to observe the POIs and the time-dependent maneuvers required to reorient the observation instrument between two POIs. They result in a highly combinatorial problem that must be solved in a restricted amount of time. To solve such a complex problem, we propose an approach that combines matheuristics to filter the observation tasks and metaheuristics to schedule them. Firstly, we solve a Sequential Ordering Problem for each satellite to get a giant tour visiting all the visible POIs. From this giant tour, we exploit a Linear Programming Model to compute the best set of observations under several tour length constraints. Finally, we schedule the selected observations based on a Large Neighborhood Search. This three-step method notoriously improves the solution quality when compared to a baseline scheduling approach. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Romain Barrault and Cedric Pralet and Gauthier Picard and Eric Sawyer 2026 Is Part Of OASIcs, Volume 146, 33rd International Symposium on Temporal Representation and Reasoning (TIME 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.TIME.2026.12 urn:nbn:de:0030-drops-277089 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.TIME.2026.12 eng https://creativecommons.org/licenses/by/4.0/legalcode