2026-07-20T14:23:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26636 2026-07-13T14:00:36Z ddc:004 open_access

Approximating Time-Dependent Transition Times in Constraint Programming for an Earth Observation Mission Barrault, Romain Pralet, Cédric Picard, Gauthier Sawyer, Eric Earth observation satellites Constraint Programming Large Neighborhood Search Scheduling 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), the problem 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 under operational constraints. These constraints stem from the visibility windows of the POIs and from the time‑dependent maneuvers required to reorient the satellites between successive POI observations (duration of the maneuvers function depending on their start times). This paper presents how Constraint Programming (CP) can be applied to solve this combinatorial observation dispatching and scheduling problem, the objective being to maximize a sum of collected individual observation rewards. Our main focus is the search for efficient strategies to approximate time-dependent no-overlap constraints given CP solvers that only manage sequence-dependent no-overlap constraints. In particular, we introduce constant-step and variable-step time-discretization methods, together with several approximation parameters. To get actually feasible solutions, the CP model is coupled with a greedy repair strategy that takes time-dependency into account, and a Large Neighborhood Search (LNS) that post-optimizes the solutions. This CP-Repair-LNS pipeline delivers high‑quality solutions compared to a baseline LNS. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Romain Barrault and Cédric Pralet and Gauthier Picard and Eric Sawyer 2026 Is Part Of LIPIcs, Volume 379, 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CP.2026.3 urn:nbn:de:0030-drops-266368 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2026.3 eng https://creativecommons.org/licenses/by/4.0/legalcode