Search Results

Documents authored by Pralet, Cedric

Document
DOI: 10.4230/OASIcs.TIME.2026.12
Earth Observation Satellite Constellation Planning with Matheuristics and Metaheuristics Combination

Authors: Romain Barrault, Cedric Pralet, Gauthier Picard, and Eric Sawyer

Published in: OASIcs, Volume 146, 33rd International Symposium on Temporal Representation and Reasoning (TIME 2026)

Abstract
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.
Cite as

Romain Barrault, Cedric Pralet, Gauthier Picard, and Eric Sawyer. Earth Observation Satellite Constellation Planning with Matheuristics and Metaheuristics Combination. In 33rd International Symposium on Temporal Representation and Reasoning (TIME 2026). Open Access Series in Informatics (OASIcs), Volume 146, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{barrault_et_al:OASIcs.TIME.2026.12,
  author =	{Barrault, Romain and Pralet, Cedric and Picard, Gauthier and Sawyer, Eric},
  title =	{{Earth Observation Satellite Constellation Planning with Matheuristics and Metaheuristics Combination}},
  booktitle =	{33rd International Symposium on Temporal Representation and Reasoning (TIME 2026)},
  pages =	{12:1--12:17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-448-2},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{146},
  editor =	{Orlandini, AndreA and Pinchinat, Sophie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.TIME.2026.12},
  URN =		{urn:nbn:de:0030-drops-277089},
  doi =		{10.4230/OASIcs.TIME.2026.12},
  annote =	{Keywords: Scheduling, Earth Observation Satellite, Matheuristic, Metaheuristic, Linear Programming}
}
Document
DOI: 10.4230/LIPIcs.CP.2026.3
Approximating Time-Dependent Transition Times in Constraint Programming for an Earth Observation Mission

Authors: Romain Barrault, Cédric Pralet, Gauthier Picard, and Eric Sawyer

Published in: LIPIcs, Volume 379, 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)

Abstract
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.
Cite as

Romain Barrault, Cédric Pralet, Gauthier Picard, and Eric Sawyer. Approximating Time-Dependent Transition Times in Constraint Programming for an Earth Observation Mission. In 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 379, pp. 3:1-3:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{barrault_et_al:LIPIcs.CP.2026.3,
  author =	{Barrault, Romain and Pralet, C\'{e}dric and Picard, Gauthier and Sawyer, Eric},
  title =	{{Approximating Time-Dependent Transition Times in Constraint Programming for an Earth Observation Mission}},
  booktitle =	{32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)},
  pages =	{3:1--3:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-432-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{379},
  editor =	{Beldiceanu, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2026.3},
  URN =		{urn:nbn:de:0030-drops-266368},
  doi =		{10.4230/LIPIcs.CP.2026.3},
  annote =	{Keywords: Earth observation satellites, Constraint Programming, Large Neighborhood Search, Scheduling}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact