Search Results

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.