# Solving the Agile Earth Observation Satellite Scheduling Problem with CP and Local Search

Valentin Antuori, Damien T Wojtowicz, Emmanuel Hebrard

► To cite this version:

Valentin Antuori, Damien T Wojtowicz, Emmanuel Hebrard. Solving the Agile Earth Observation Satellite Scheduling Problem with CP and Local Search. 31st International Conference on Principles and Practice of Constraint Programming (CP 2025), Aug 2025, Edinburgh, Scotland, United Kingdom. pp.3:1-3:22, 10.4230/LIPIcs.CP.2025.3 . hal-05466229

HAL Id: hal-05466229

https://hal.science/hal-05466229v1

Submitted on 19 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Solving the Agile Earth Observation Satellite Scheduling Problem with CP and Local Search

Valentin Antuori

<figure><img src="image_2.png" /></figure>

LAAS - CNRS, Toulouse, France

Damien T. Wojtowicz

<figure><img src="image_3.png" /></figure>

LAAS - CNRS, Toulouse, France

Emmanuel Hebrard

<figure><img src="image_4.png" /></figure>

LAAS - CNRS, Toulouse, France

## Abstract

The increasing hunger for remote sensing data fuels a boom in satellite imagery, leading to larger agile Earth observation satellite (AEOS) constellations. Therefore, instances of the AEOS scheduling problem (AEOSSP) has become harder to solve. As most existing approaches to solve AEOSSP are designed for a single spacecraft or smaller constellations in mind, they are not tailored to the need of our industrial partner that is about to launch a constellation of 20 AEOSs. Hence, we designed a local search solver able to schedule observations and downloads at such a scale. It relies on solving a series of sub-problems as travelling salesman problem with time windows (TSPTW), first greedily, then using a CP-SAT exact solver in order to find a solution when the greedy insertion fails. Lastly, it schedules downloads and enforces memory constraints with greedy algorithms. Experiments were carried out on instances from the literature as well as generated instances from a simulator we designed. Our experiments show that using CP to solve the sub-problem significantly improve the solutions, and overall our method is slightly better than state-of-the-art approaches.

**2012 ACM Subject Classification** Computing methodologies → Planning and scheduling; Applied computing → Operations research

**Keywords and phrases** Local Search, Greedy Algorithms, Aerospace Applications

**Digital Object Identifier** 10.4230/LIPIcs.CP.2025.3

**Supplementary Material** Dataset: https://github.com/ssquilla/Earth_Observing_Satellites_benchmarks [35]; archived at swh:1:dir:c1c87cf9c3a3e7ffe616bdffdc9c52af9e30cb35

**Funding** France Relance grant (project JAPETUS)

## 1 Introduction

Fueled by an increasingly easier access to space, technological advances, and an ever-growing hunger for up-to-date information, satellite imagery is booming. Since the introduction of the Pléiades project [13], satellite surveillance has typically been carried out using agile Earth observation satellites (AEOS), because of their ability to observe an area within a large horizon thanks to their yawing, pitching and rolling capabilities (see Fig. 1). Those satellites are typically deployed within constellations of a few spacecrafts. Current existing projects, such as JAPETUS, lead by our industrial partner Prométhée<fnref n="1" />, aim at launching constellations of several dozen satellites.

As a consequence of the growing size of instances and constellations, the already NP-hard AEOS Scheduling Problem (AEOSSP) becomes even harder to solve in practice. This is a major problem for AEOS constellation operators, as low-quality observation plans would

<figure><img src="image_5.png" /></figure>

© Valentin Antuori, Damien T. Wojtowicz, and Emmanuel Hebrard; licensed under Creative Commons License CC-BY 4.0

31st International Conference on Principles and Practice of Constraint Programming (CP 2025).

Editor: Maria Garcia de la Banda; Article No. 3; pp. 3:1–3:22

<figure><img src="image_6.png" /></figure>

LIPICS

Leibniz International Proceedings in Informatics

Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

<footnote n="1">¹ See https://promethee.earth/.</footnote>
<figure><img src="image_7.png" /><figcaption>Figure 1 Schematic view of an agile satellite’s observation capabilities.</figcaption></figure>

compromise their profitability. Moreover, their business model is increasingly based on reactivity, allowing their customers to request images and have them delivered within a few hours. AEOSSP must then be solved as fast as possible, since it is part of broader processes that are all subject to tightening deadlines. As a side effect, image download planning has to be efficient in order to minimize the overall processing time of a request. In the past two decades, extensive work has been carried out on solving several versions of the AEOSSP [34]. Many methods have been proposed so far, including exact methods, heuristics and metaheuristics. However, most of these proposals are designed with a single spacecraft or smaller constellations in mind, and without considering download planning or a reactive business model.

In this paper, we introduce the industrial application of an acquisition planning method using several techniques from CP, that can deal with large scale instances including complex requests while performing download planning. Our method can quickly find good solutions for a constellation of twenty AEOSs on instances reaching up to a thousand complex requests over a planning horizon of six hours. Our approach is similar to the algorithm designed by Squillaci, Pralet and Roussel [25] in that it relies on a local search approach hybridized with an external solver. However, our method not only uses a SAT-based CP solver to solve sub-problems rather than solely relying on greedy algorithms, but also considers satellite memory constraints and takes download decisions instead of pre-assigning time intervals dedicated to downloads.

It solves the AEOSSP by decomposing it into an acquisition planning problem and a
download planning problem. The first one is solved via local search whose moves aims at
building a sequence of acquisitions for a single satellite over a given time period consisting of
several overlapping acquisition opportunities, which often correspond to a daylight portion
of the satellite's orbit over land. Those moves are performed using calls to a CP solver and
greedy algorithms. The download planning problem takes an acquisition plan as input and is
solved using a greedy algorithm.

Experiments were carried out over a set of instances from the literature as well as instances generated using a simulator we designed. Results shows that our solver is comparatively faster and finds better solutions than both the state-of-the-art aforementioned LNS method tailored for AEOSSP and a baseline model implemented with IBM's CP Optimizer.

This paper is organized as follows. AEOSSP is defined in Sect. 2. Then, a brief overview of related work is provided in Sect. 3. Our approach is explained in Sect. 4, then evaluated and compared with the literature in Sect. 5. Finally, this paper is concluded in Sect. 6.
## 2 Problem Statement

The AEOSSP problem aims at scheduling observations and data transfers in order to maximize the profit of the constellation's operator. Together with our industrial partner, we adopted an integrated planning definition, i.e. including constraints on AEOSs' memory and computing not only an observation planning but also a download planning. In this respect, it is similar to that adopted in some of the latest research [11, 10]. Since our partner emphasizes reactivity, AEOSSP is periodically solved over a few-hour rolling planning horizon. Hereafter, we describe the elements of the problem before formalizing it.

### 2.1 Input Data

Let $\mathcal{R}$ be a set of customer requests. A request $r$ involves observing an area split into a set $\mathcal{M}_r$ of meshes. Requests can be repeated, hence we define the set $\mathcal{P}_r$ of those repetitions. For instance, there can be a request to observe the area around Glasgow, which is decomposed into a grid of meshes covering the city, with a two-hour period during the CP 2025 conference.

The constellation we consider has a set $\mathcal{S}$ of satellites, that can be used to observe a mesh for a given period. Such an action is called an acquisition opportunity, although we shall use acquisition for short. Let $\mathcal{A}$ be the set of acquisitions. We define the subset $\mathcal{A}_{r,t,m}$ as the set of possible acquisitions of the request $r$ for the period $t$ and the mesh $m$, and $\mathcal{A}^s$ as the subset of acquisitions which can be made by satellite $s$. Each acquisition $a$ has a duration $p_a$ to make that observation, which must occur during a time window $[r_a, d_a]$. It is associated to a profit $v_a$, and it consumes a quantity of memory $\gamma_a$. Satellites may have some acquisitions in memory at the beginning of the planning period. For each satellite $s$, $\mathcal{F}^s$ is the set of such acquisitions, and we note $\mathcal{F} = \cup_{s \in \mathcal{S}} \mathcal{F}^s$. There can be many alternative acquisitions for the same observation task (i.e. a mesh for a given period), since the same image can be shot by different satellites or the same satellite on different orbits. Therefore, the goal is to select acquisitions among the many alternatives, so that as many requests as possible are fulfilled.

Then, the acquisitions must be scheduled. As satellites need to maneuver in order to aim at their targets (i.e. to observe a mesh), there are transition times between successive acquisitions performed by the same satellite. In agreement with our industrial partner and in line with other works in the literature [3], we assume that transition times are time-independent. Thus, $T(a_1, a_2)$ is the transition time between two acquisitions $\{a_1, a_2\} \subseteq \mathcal{A}^s$ on a satellite $s$.

Finally, a network of ground stations (GS) are used to download the observations. For each acquisition $a$, there is a set $\mathcal{W}_a$ of possible download windows. A download time window $w$ is a time window $[r_w, d_w]$ during which acquisitions can be downloaded. It has a total capacity $\gamma_w$ which is the product of its bandwidth by its duration. Each satellite $s$ has a memory capacity $C_s$.

Memory management is the second part of the problem. It consists of assigning each selected acquisition in the plan to a download time windows, while ensuring that onboard memory and download capacity constraints are respected.

### 2.2 Decision Variables and Constraints

The following model formally describes the problem. For each acquisition $i \in \mathcal{A}$, we have a boolean selection variable $x_a \in \{0, 1\}$ and a start time variable $s_a \in \{r_a, d_a - p_a\}$. Moreover, for each acquisition $a \in \mathcal{A} \cup \mathcal{F}$ and for each of its download options $w \in \mathcal{W}_a$, there is a boolean selection variable $y_{a,w} \in \{0, 1\}$.
## 3:4 Solving AEOSSP with CP and Local Search

The problem is to compute a mission, i.e. select and schedule the acquisitions and downloads for each satellite in order to maximize the profit, satisfying the following constraints:

**Acquisitions time windows:** Selected acquisitions must occur wholly within their time windows.

$$x_a \Rightarrow r_a \le s_a \le d_a - p_a \quad \forall a \in \mathcal{A} \quad (1)$$

**Acquisitions no-overlap:** On a satellite $s \in \mathcal{S}$, the selected acquisitions must not overlap in time.

$$x_a \wedge x_b \Rightarrow s_a + p_a + T(a, b) \le s_b \vee s_b + p_b + T(b, a) \le s_a \quad \forall \{a, b\} \subseteq \mathcal{A}^s \quad (2)$$

**Acquisitions alternatives:** No more than one acquisition among alternatives for each observation target shall be done.

$$\sum_{a \in \mathcal{A}_{r,t,m}} x_a \le 1 \quad \forall r \in \mathcal{R}, \forall t \in \mathcal{P}_r, \forall m \in \mathcal{M}_r \quad (3)$$

**Acquisitions download:** Selected acquisitions cannot be downloaded more than once, they must be finished before being downloaded<fnref n="2" />.

$$\sum_{w \in \mathcal{W}_a} y_{a,w} \le x_a \quad \forall a \in \mathcal{A} \quad (4)$$

$$y_{a,w} \Rightarrow s_a + p_a \le r_w \quad \forall a \in \mathcal{A}, \forall w \in \mathcal{W}_a \quad (5)$$

**Satellite memory:** At any given time $t$, the quantity of data stored on a satellite $s \in \mathcal{S}$ (equal to the total acquired before $t$ minus the total download before $t$) must not exceed its capacity<fnref n="3" />.

$$\sum_{a \in \mathcal{A}^s | x_a \wedge s_a < t} \gamma_a - \sum_{a \in \mathcal{A}^s, w \in \mathcal{W}_a | y_{a,w} \wedge d_w < t} \gamma_a \le C_s \quad \forall t \quad (6)$$

**Downloads capacity:** The total quantity of data downloaded during a time window must not exceed its capacity.

$$\sum_{a \in \mathcal{A}} y_{a,w} \gamma_a \le \gamma_w \quad \forall w \in \mathcal{W} \quad (7)$$

The objective is then simply to maximize the total profit:

$$\sum_{a \in \mathcal{A}} x_a v_a \quad (8)$$

This objective function might seem overly simple. However, from the point of view of the operators, this is relatively easy way to steer the plan toward their true objectives. In particular, some efforts have been put into complex requests with non-additive rewards [25]. For instance, imagine that you want a complete map of Scotland. It requires to perform a large set of acquisitions, hence having only a subset of the observations may be worthless, or at least the profit should not be linear with the ratio of the observations that were made. However, such complex requests are likely to span over several planning horizons. Therefore, modeling a complex cost system might be detrimental if the whole request can never fit within one planning horizon. On the other hand, with a simple additive objective, the operators may for instance start with attaching low profits to each observation of a complex request, and then increase the weight associated to missing observations on subsequent planning sequences, depending on how close to completion they are.

## 3 Related Work

Initial work on AEOSSP was carried out as part of the development of the Pléiades constellation [13]. Since then, there have been numerous articles on this topic [34, 24], considering several variations of the problem, and exploring a wide array of methods that are generally in line with related aerospace problems [36]. In this section, we provide a brief overview of the state of the art on AEOSSP.

<footnote n="2">² We make the conservative assumption that an acquisition can be downloaded only if the acquisition is finished at the start of the download time window.</footnote>

<footnote n="3">³ We make the conservative assumption that memory is released at the end of the download time windows.</footnote>
## 3.1 AEOSSP variations

Substantial differences exist in the scope of the AEOSSP used throughout the literature, mainly on extensions to the core observation scheduling problem [13]. This core is NP-hard [13]. Moreover, exhaustively taking into account all possible extensions of the AEOSSP can make it too complex, therefore intractable for existing methods. As a consequence, all the publications that we are aware of about AEOSSP consider only a subset of the constraints with more or less radical simplifications. We also defined with our industrial partner a somewhat simplified version of AEOSSP in this paper, as previously discussed in Sect. 2.

Some models [28, 6, 14] consider the breakdown into meshes and strips (i.e. long polygons imaged while the satellite is moving) of the requests' areas of interest as decision. As in most of the literature, we assume that this step is part of some preprocessing and therefore outside of the scope of our work.

Depending on the AEOSs' capabilities, the nature of the requests themselves can vary. Indeed, they can be simple, one-shot images of a given area, strips covering long areas [1], repetitive, stereoscopic [20], video requests [5], or even be instrument-specific when several sensors are on the spacecrafts [18, 17, 37]. Our solver is agnostic to the nature of the acquisitions; expressing punctual and stereoscopic requests can be done at preprocessing time using repetitions.

The *quality* of the images is time-dependent [21, 16, 29, 33, 22] and multifaceted (shooting angle, luminosity, cloud cover, customer preferences, etc.), leading some authors to consider AEOSSP as a multi-objective problem [16, 15]. Hence, in addition to profit, those works seek to maximize image quality or use of the satellites. *Profit* itself can be time-dependent [28] since it is quality-dependent. It can also be affected by urgency and priority policies among requests [29, 27], and even be sequence-dependent in the case of repetitive or stereoscopic requests [4, 12, 14, 20]. In our work, we have a black-box approach to profit as it is determined for each acquisition by our partner: quality and urgency are therefore sidelined as they are embedded within the profit, hence removing its time-dependence.

There are also operational constraints. Firstly, *transition times*, which is the time the satellite needs to maneuver towards its target. They are by nature dependent on the time and sequence of acquisitions made by AEOS [3, 22, 2]. They are either modeled as such, or approximated by piecewise linear functions or constants, or simply ignored. Our approach also approximates transition time using a transition time matrix between categories of attitude adopted by the AEOSs when performing the acquisitions. Hence, it allows to take into account time and sequence dependencies at a granularity defined at preprocessing time while formally removing time-dependence from our model.

Then there can be constraints about onboard *energy* management. The energy comes from solar panels, and the rate at which batteries are refilled therefore depends on both the time (the exposition to the sun depends on the orbit of the satellites) and the tasks performed by the satellite since it constrains the orientation of the solar panels [32, 33]. However, on-board energy management is rarely a bottleneck, and hence it is usually not taken into account when planning the observations. In accordance with the needs expressed by our industrial partner, this aspect is not covered in our work.

Finally, there is the management of onboard *memory* and its corollary: the management of *downloads* [21, 10, 11, 19]. Scheduling both acquisitions and downloads is often referred to *integrated scheduling* in the literature [34]. Memory can be looked at in two ways. By ignoring the files, it becomes a reservoir that is filled and emptied according to linear functions. If the files are taken into account, then it is a set of blocks that must be distributed between the download windows according to their capacity. We take the second approach, as it best fits our partner's processes.
## 3.2 Resolution methods

The wide range of variations in AEOSSP has resulted in the study of numerous resolution methods.

Exact methods have been extensively used to solve the AEOSSP. For instance, a branch-and-bound algorithm taking into account time-dependent constraints was proposed and shown to be effective on small instances [3]. Several MILP formulations have also been proposed [29, 12], including in the context of integrated scheduling [10, 11]. Some work only focus on data download [19] and are more in line with broader work on the Antenna-Satellite scheduling problem. Although MILP was successfully used to perform integrated scheduling with a commercial solver for Planet Lab's constellation of over a hundred spacecrafts [23], they are not *agile* satellites and hence the scheduling problem is a lot easier than the AEOSSP. Moreover, while projects with a problem statement roughly similar to ours [11] does use MILP, their instances are way smaller (4 satellites, up to 3 ground stations and 200 requests), do not take into account transition times, and have a time limit orders of magnitude too high (approx. 3 h) to be used in our industrial partner's processes. For all these reasons, we have not retained the possibility of using CP to solve the problem as a whole, but rather to solve sub-problems as a local search move.

Much of the work on AEOSSP has chosen to abandon optimality guarantees and propose methods based on heuristics and metaheuristics. Several methods solely based on heuristics have been proposed to solve AEOSSP. The scheduler of the COSMO-SkyMed constellation, comprising four spacecrafts, simply selects as much acquisitions as it can by descending order of priority [1]. Heuristics can also be used to compute the acquisitions given areas of interest in the context of an online scheduler [14]. A method using deep reinforcement learning and heuristic algorithm has also recently been proposed to solve AEOSSP for a single satellite [2]. Although those heuristics-based methods are easy to implement and yield good results for a single satellite or smaller constellation, they are not expected to be as good when applied to a whole constellation because of the larger number of alternative acquisitions. Methods using machine learning are also of great interest to solve AEOSSP, as satellite operators accumulate many instances over time, but the size of the instances and the lack of real-world data from our industrial partner led us away from learned heuristics.

Many metaheuristics-based methods has also been proposed since the first studies on AEOSSP, such as taboo search [4]. Genetic algorithms have been widely used to tackle multi-objective versions of the AEOSSP, for instance when considering operator's preferences [16], load balancing [7], or solution stability in an online setting [15] in addition to profit. They were also applied to decompose sub-problems. In a first example, it is used for single-satellite scheduling within a broader game theory framework where satellites are players [20]. In a second example, it is used to choose between overlapping acquisitions within multi-level clusters computing using priority metrics [8]. Agent-based methods are also interesting to solve small-scale instances of AEOSSP [5].

Finally, local search and large neighborhood search (LNS) methods have also been extensively studied, including in the context of multi-objective optimization [28, 37] and online solvers [27]. Moves proposed in the literature rely on a wide array of algorithms. On the more complex side, there is a move based on computing maximum independent sets within acquisitions interval graphs using an evolutionary algorithm [6]. Unsupervised learning has also been used as a preprocessing tool for destructive LNS moves [21]. However, most of the constructive LNS moves are simpler, as they widely rely on random choices [9] and greedy algorithms [9, 22, 25]. It should be noted that these local search and LNS methods are similar to what can be found in the team orienteering problem [30], since it shares many characteristics of the acquisition selection sub-problem of AEOSSP.
<figure><img src="image_8.png" /><figcaption>■ **Figure 2** Example of sequences defined from the dependence graph built from a set of acquisitions. Acquisitions with the same colour are alternatives to cover the same mesh for the same task of the same request. The interval graph contains three connected components.</figcaption></figure>

The solver we present in this article is also in this line of work, as local search methods are particularly effective for solving complex instances in satellite constellations, while making it easier to break down the problem into acquisition planning and download management.

# 4 A Local Search Approach

In order to solve our version of AEOSSP, we leverage the structure of the problem to decompose it into two parts. Firstly, the selection and allocation of the acquisitions – the master problem – is solved using a local search method that computes sequences of acquisitions for each satellite. Secondly, one planning of file downloads – the sub-problem – is solved using a greedy algorithm. Those two parts are repeated until a time limit.

## 4.1 Acquisition Planning

The acquisition planning phase aims at building a sequence of acquisitions for each satellite maximizing the profit under the aforementioned constraints 1, 2 and 3.

Our method uses the fact that there exists subsets of acquisitions of a given satellite that are temporally independent of each other [6, 26]. This can happen when the satellite flies over a large area with little interest (e.g. an ocean, cloudy areas, etc.), or simply because of the satellite's orbital nighttime. Formally, for each satellite $s \in S$ we can define a dependence graph whose nodes are the acquisitions $a \in A^s$. There is an edge between two acquisitions $\{a, b\} \subseteq A^s$ if $d_a + T(a, b) > r_b \lor d_b + T(b, a) > r_a$, i.e., when their time windows overlap while taking into account transition time. As a consequence, each connected component of these graphs are temporally independent of each other (see example in Fig. 2). Hence, local optimization may be performed over each connected component in order to build the plan in the form of sequences of acquisitions.

Our algorithm for acquisition planning has two phases. Firstly, it builds a solution from scratch with a greedy algorithm. Secondly, a local search phase aims at improving the solution until a local minimum is reached.
### 4.1.1 Greedy Initial Solution Construction

The greedy algorithm iteratively tries to insert an acquisition. It uses a utility criterion $U(a) = v_a/p_a$ defined as the ratio of an acquisition a's profit over its duration to select the next acquisition to insert. The algorithm iterates over the acquisitions whose associated mesh and task are not currently covered by descending order of their utility, by trying to insert them in their satellite's plan to minimize the increment of transition times.

The time complexity to find the best valid position is linear in the length of the current sequence and to insert the acquisition is linear in the size of the sequence under construction.

Therefore, the algorithm runs in $O(|A|^2)$ time overall for a sequence of acquisition $A$.

Let $A = a_0, a_1, \dots, a_k, a_{k+1}$ be a feasible sequence of acquisitions with $a_0$ and $a_{k+1}$ dummy acquisitions of null duration, null transition time with all other acquisitions and such that $r_{a_0} = 0$ and $d_{a_{k+1}} = \infty$. The greedy insertion algorithm returns the position $i \in [0, k]$ such that inserting $a$ between acquisitions $a_i$ and $a_{i+1}$ yields a feasible sequence and $T(a_i, a) + T(a, a_{i+1})$ is minimum.

The following quantities can be accessed in constant time:

$$s_{a_i} = \max(r_{a_i}, s_{a_{i-1}} + p_{a_{i-1}} + T(a_{i-1}, a_i)) \quad \forall 1 \le i \le k \quad (9)$$

$$\text{slack}(a_i) = d_{a_i} - s_{a_i} - p_{a_i} \quad \forall 1 \le i \le k \quad (10)$$

$$\text{gap}(a_i) = s_{a_i} - s_{a_{i-1}} + p_{a_{i-1}} + T(a_{i-1}, a_i) \quad \forall 1 \le i \le k \quad (11)$$

Then, we store the values of the cumulative gap up until acquisition $a_i$ in linear space:

$$\text{cgap}[a_i] = \sum_{j=0}^{i-1} \text{gap}(a_j) \quad \forall 1 \le i \le k \quad (12)$$

Therefore, we can access in constant time $F(a_i, a_j)$ the time length available between tasks $a_i$ and $a_j$ (with $j > i$) in the sequence:

$$F(a_i, a_j) = \text{cgap}[a_j] - \text{cgap}[a_i] + \text{slack}(a_j) \quad \forall 1 \le i \le k \quad (13)$$

Finally, we store the time length available for a task insertion immediately after task $a_i$ using linear space:

$$I[a_i] = \min_{i<j \le k} F(a_i, a_j) \quad \forall 1 \le i \le k \quad (14)$$

When trying to insert acquisition $a$, the algorithm makes a linear search over the sequence $a_0, a_1, \dots, a_k$ to find the position $i \in [0, k]$ that minimizes $T(a_i, a) + T(a, a_{i+1})$, whilst ensuring that the insertion is feasible using the value of $I[a_i]$. Then, after the actual insertion, the values of $s$, $cgap$ and $I$ are updated in linear time by once again traversing the acquisition in the sequence. An insertion therefore requires two linear-time traversals of the sequence.

Finally, we introduce randomization. Indeed, instead of taking the next acquisition in utility order, there is a small probability to take a random one instead. Once this algorithm has produced an initial solution, the local search starts.

### 4.1.2 Local Search

Our method locally optimizes the plan by iteratively recomputing sub-sequences. A move for our local search consists in solving a kind of *orienteering problem* over the complete graph formed by the acquisitions of a given connected component. In this graph, each node is an acquisition with the same time window, and is associated to a profit, which we will describe
below. The transition time between two acquisitions is the length of the path between the two associated nodes. The goal is to find a path in this graph that maximizes the sum of the profit of the visited nodes, while respecting time windows (i.e. finding a maximum-profit sequence of acquisitions).

The profit of selecting an acquisition *a* is defined as follows. It uses the marginal profit *P* that is the profit increment that would occur if an acquisition was inserted in the plan instead of another alternative acquisition (i.e., the cost of swapping acquisition *a* for an alternative acquisition *b* if it was in the current plan, that is, if $x_b = 1$).

$$ \mathcal{P}(a) = v_a - \sum_{b \in \mathcal{A}_{r,t,m} \setminus a} x_b v_b \quad r \in \mathcal{R}, t \in \mathcal{P}_r, m \in \mathcal{M}_r, a \in \mathcal{A}_{r,t,m} \quad (15) $$

Should the move find a solution with a higher overall profit than the current plan, the new sequence that was built for the considered connected component substitutes the one in the plan. The latter is updated as a whole, by deselecting already selected alternative acquisitions from the new sequence.

To solve this sub-problem, we use the same procedure as for the initialization: for each acquisition in decreasing order of marginal profit, it tries to insert acquisitions within the sequence. This procedure stops when the first acquisition with a non positive marginal profit is reached. Two insertion techniques are used. The first tries to insert the acquisition in the sequence so that transition times are minimized, just as in the initial solution construction. The second technique is used when the first fails: an external solver is called to perform the insertion of the new acquisition by rescheduling the whole connected component.

We use Tempo<fnref n="4" />, a CP-SAT solver that we are developing as part of a distinct project. It is asked to solve a traveling salesman problem with time windows (TSPTW), where the goal is to find a valid tour in the graph formed by the acquisitions already in the sequence extended with the acquisition we are trying to insert. The time window of a node is the time window of the acquisition, and the transition time between two nodes is the transition time between the two associated acquisitions. We model this problem with one interval variable for each acquisition *i*. The release and due dates of the interval variable of an acquisition *i* are $r_a$ and $d_a$ respectively, and its duration is $p_a$. Then the only constraint of the model is a NOOVERLAP on all the acquisitions, taking into account the transition times. There is no objective function as we just seek a valid sequence of acquisitions. Tempo's search is limited by a fail limit. The main benefit of this approach is that it allows to reorder the sequence when a solution is found, possibly leaving space for further acquisition insertions.

Finally, the neighborhood of a given plan is defined by the number of connected components. Indeed, we have one possible move per connected component, that eventually leads to an improving neighbor. Therefore we choose to perform a simple descent, choosing at each iteration the first improving neighbor among all randomly ordered neighbors, until a local minimum is reached, i.e. none of move can improve the current plan.

## 4.2 Download Planning

The download planning phase takes place when a local minimum is found. Its aim is twofold. It first computes a download plan by affecting download windows to the planned acquisitions and the initial memory elements aboard the satellite. Then, it fixes potential remaining memory overloads on the satellites by progressively deselecting acquisitions.

<footnote n="4">⁴ See https://gitlab.laas.fr/roc/emmanuel-hebrard/tempo.</footnote>
## 3:10 Solving AEOSSP with CP and Local Search

For each satellite, the algorithm iterates over the download windows by increasing order of their starting time, in order to greedily affect acquisitions until the download window's capacity is reached or there is no remaining acquisition to download. This greedy algorithm starts by collecting the acquisitions that are still on board at the starting time of the download time window, and sort them by decreasing order of their memory consumption. Then acquisitions are assigned in this order to the window if they fit.

Despite download decisions being taken, memory constraints may still be violated as the algorithm is blind to memory overloads. Hence, a memory overload repairing procedure is applied to satellites with overloads. Since we assume that the memory is freed at the end of the download window, overloads are checked at these time points. When one is found, a knapsack problem is solved over the onboard acquisitions. The knapsack capacity is the memory capacity of the satellite, the weights are the memory consumption of the acquisitions, and the values are the profits of the acquisitions. We use a simple greedy algorithm with a profit over size ratio utility to solve the knapsack problem.

It should be noted that while both procedures are using greedy algorithms, it is not an issue as download planning is often an easy task and memory is rarely a bottleneck. Finally, it should be noted that since our overall method is solved on a rolling horizon, some images may not be downloaded during the current planning horizon. They will be the content of the set $\mathcal{F}$ of the next planning horizon.

# 5 Experiments and Results

We evaluated our approach against a state-of-the-art commercial solver and recent proposals from the literature, over instances from the literature as well as generated by a simulator of our own design.

## 5.1 Experimental setting

Experiments were run on a cluster of computers with 2,1 GHz Intel CPUs and 256 GB RAM. Results are the aggregation of 5 runs with different seeds and a 10 min timeout. We implemented our solver with C++ 20.

### 5.1.1 Instances

We used two instance sets to evaluate our work.

The first instance set, hereafter referred to as “Squillaci et al.”, comes from recent work<fnref n="5" /> [25]. It contains 32 instances containing up to 1140 requests. Details of the instances are provided in Table 7 (Appendix A). They are regional instances focusing on Europe, half of them are generated using a uniform target distribution and the other half focus on fifty large European airports, containing one-shot, video, stereoscopic and periodic requests. It should be noted that video requests are like one-shot requests but longer and more profitable. Moreover, a stereoscopic request implies observing the same area twice with the same satellite with two different angles. Therefore, we slightly adapted our method in order to support stereoscopic requests, by trying to insert the second acquisition right after the first one has been inserted into its satellite's sequence. If the second insertion fails, then the first acquisition's selection is canceled. The marginal profit of an acquisition from a stereoscopic

<footnote n="5">⁵ Instances retrieved from https://github.com/ssquilla/Earth_Observing_Satellites_benchmarks.</footnote>
■ **Table 1** Satellites orbital parameters for the simulation, including plane inclination *i* (deg), altitude *a* (km), longitude of ascending node Ω (deg), mean anomaly *M* and period *P* (min).

<table><caption>(a) Inclined plane orbits.</caption><thead><tr><th><i>i</i></th><th><i>a</i></th><th>Ω</th><th><i>M</i></th><th><i>P</i></th></tr></thead><tbody><tr><td>90</td><td>500</td><td>-180</td><td>{-180, -90, 0, 90}</td><td>90</td></tr><tr><td>90</td><td>500</td><td>-90</td><td>{-180, -90, 0, 90}</td><td>90</td></tr><tr><td>90</td><td>500</td><td>0</td><td>{-180, -90, 0, 90}</td><td>90</td></tr><tr><td>90</td><td>500</td><td>90</td><td>{-180, -90, 0, 90}</td><td>90</td></tr></tbody></table>

<table><caption>(b) Heliosynchronous orbits.</caption><thead><tr><th><i>i</i></th><th><i>a</i></th><th>Ω</th><th><i>M</i></th><th><i>P</i></th></tr></thead><tbody><tr><td>98</td><td>550</td><td>-144</td><td>-180</td><td>90</td></tr><tr><td>98</td><td>550</td><td>-60</td><td>-90</td><td>90</td></tr><tr><td>98</td><td>550</td><td>60</td><td>0</td><td>90</td></tr><tr><td>98</td><td>550</td><td>144</td><td>90</td><td>90</td></tr></tbody></table>

request is the sum of both's marginal profits. We did not use the profit function proposed in [25] for periodic requests since we have an all-or-nothing approach for the requests. Finally, as the instance files did not provide transition times, we followed the method of Squillaci et al. to compute it as a function of the euclidean distance between the targets.

The second instance set we used was produced by an instance generator we designed<fnref n="6" />. The latter's input is a set of coordinates corresponding to points of interest (POIs) distributed over the Earth, then calculates meshes covering them using a greedy algorithm. It then simulates satellite orbits to determine the visibility time windows for each mesh and ground station over a given planning horizon. Requests are then generated by randomly selecting a subset of the meshes, with a probability of also selecting their neighbors in order to simulate requests over large geographical areas. The number of periods depends on the view accesses associated with the selected meshes, and is also randomly selected.

We produced a set of 20 instances<fnref n="7" />, containing up to 500 requests over a planning horizon of 6 h, assuming a constellation of twenty satellites evenly spaced on four parallel inclined orbits and an heliosynchronous orbit (see orbital parameters in Table 1). We assumed a network of 6 ground stations with characteristics similar to KSATlite<fnref n="8" />. As in many other work, we used non-uniform POI distribution at regional scale [1, 9, 25] – hereafter referred to as “Antilles”, “Sahara” and “Fountains” – and worldwide scale – “Military” and “World Heritage” – that we extracted from OpenStreetMap. For each POI set, we generated 4 instances from 50 to 500 requests. Further details about the instances are in Table 6 (Appendix. A).

In order to make a comparison, we use the same hypothesis to compute transition time as in Squillaci et al. instances. For a given target, we choose a base profit and a decreasing slope randomly, each acquisition has then a profit that depends on its start date, the later it is, the lower will be the profit. In addition to that, each acquisition has a chance to have a large penalty in order to simulate bad weather.

## 5.2 Comparison points

We compared our algorithm with the results of the aforementioned LNS method from the literature, as well as a baseline model with IBM's CP Optimizer (CPO).

<footnote n="6">⁶ See source code at https://gitlab.laas.fr/roc/damien-wojtowicz/aeossp_instance_generator.</footnote>

<footnote n="7">⁷ Instances available at https://gitlab.laas.fr/roc/damien-wojtowicz/aeossp_instances.</footnote>

<footnote n="8">⁸ See https://www.ksat.no/ground-network-services/ksatlite/.</footnote>
## 5.2.1 LNS Method

We choose Squillaci, Roussel and Pralet's [25] LNS method because, to our knowledge, it is the most similar to ours in the literature. It uses dedicated moves to relax sets of requests before reinserting the requests in the plan.

Its destructive phases use the same concept of connected components within an acquisitions' time windows graph as our method, as well as other work in the literature [6]. Those phases randomly select a subset of connected components, then relax a subset of acquisitions within, so as to have more choice to reinsert a request after relaxation.

Repair phases use CPO to solve an orienteering problem over the subset of the selected connected components. Although this algorithm can run in a multi-core parallel mode, we run the experiments with a single core in order to do a fair comparison with our algorithm.

## 5.2.2 CP Model with CPO

Finally, we implemented a baseline CP model with CPO version 20.1.0 using its C++ API, solved with a single thread and running on the same machines as our solver. Under the default parameter setting, CPO runs LNS until a local optimum is detected and then switches to complete search, namely, Failure Directed Search [31]. We defined three sets of interval variables to model this problem. First, there is an optional interval $X_a := \langle s_a, e_a \rangle$ for each acquisition $a \in A$, with $s_a \ge r_a$, $e_a \le d_a$ and $e_a - s_a = p_a$. Then, there is an interval $Y_w := \langle s_w, e_w \rangle$ for each download window $w \in W$ with $s_w \ge r_w$ and $e_w \le d_w$. Lastly, there is an optional interval $Z_{a,w} := \langle s_{a,w}, e_{a,w} \rangle$ for each download window $w \in W_a$ for each acquisition $a \in A$ with $s_{a,w} \ge s_w \wedge s_{a,w} \ge e_a$, $e_{a,w} \le e_w$ and $e_{a,w} - s_{a,w} = m_a/b_w$.

The objective function is stated as follow:

$$ \max \sum_{a \in A} \text{PRESENCEOf}(X_a) \times v_a \qquad (16) $$

We defined the following constraints. Constraint 17 ensures that acquisitions do not overlap in the plan for each satellite, taking into account a transition matrix $T$. Constraint 18 ensures uniqueness of observations. Constraint 19 defines a profile of memory usage, and Constraint 20 sets a limit on this profile. It should be noted that this is the typical way to model a reservoir using CPO, which we chose over a cumulative global constraint in order to avoid adding a task that starts with the acquisitions and ends at the download. Constraints 21 and 22 enforce consistency between acquisitions and downloads: only acquisitions in the plan can be downloaded and only one download can be done for each acquisition. Finally, Constraint 23 ensures that the capacity of each download window is not exceeded.

$$ \text{NOOVERLAP}(\{X_a | S_a = s\}, T) \qquad \forall s \in S \qquad (17) $$

$$ \text{ALTERNATIVE}(\{X_a | R_a = r \wedge T_a = t \wedge M_a = m\}) \qquad \forall r \in \mathcal{R}, \forall t \in \mathcal{P}_r, \forall m \in \mathcal{M}_r \qquad (18) $$

$$ p_s := \sum_{a \in A_s} \text{step}(X_a, m_a) - \sum_{w \in W_s} \text{step}(Z_{a,w}, m_a) \qquad \forall s \in S \qquad (19) $$

$$ \text{ALWAYSIn}(p_s, 0, C_s) \qquad \forall s \in S \qquad (20) $$

$$ \text{PRESENCEOf}(Z_{a,w}) \implies \text{PRESENCEOf}(X_a) \qquad \forall a \in A, \forall w \in W_a \qquad (21) $$

$$ \text{ALTERNATIVE}(\{Z_{a,w} | w \in W_a\}) \qquad \forall a \in A \qquad (22) $$

$$ \text{NOOVERLAP}(\{Z_{a,w} | \forall a \in A_w\}) \qquad \forall w \in W \qquad (23) $$

It should be noted that, for Squillaci et al. instances, this model has to be adapted by removing all constraints and variables dealing with the memory and the downloads, treating all the downloads as acquisitions except that their intervals are not optional, and by adding an equality constraint between the presence variable of stereoscopic pairs of acquisitions.
## 5.3 Results and Discussion

We now present and discuss the experimental results, by first comparing our method with the aforementioned comparison approaches. Then, we assess the impact of our use of the CP-SAT solver Tempo within the local search move, as well as the consequences of how our method manages satellite's memory.

### 5.3.1 Comparison with LNS and CPO

We compared our method (noted as LS-tempo, with a fail limit of 50 when using the solver) against the LNS from the literature (LNS) and the CPO model (CPO) over Squillaci et al.'s instances (see Table 2) and over our set of instances in (see Table 3).

The baseline CPO model is the most competitive for the smaller instances in every instance set. However, it does not scale up to large instances as well as the two other methods. On Squillaci et al.'s instances, it has good results up to 500 requests, is the best on 4 instances and can also prove optimality on 4 instances. On our instances, it is the best up to 100 requests and proves optimality on 3 instances. Auxiliary experiments on Squillaci's instances showed that CPO performs better with a 1 hour time budget (up to 27 % increase in profit), but still stays behind other methods (with 10 minutes budgets), especially on large instances (for example the 0-1000-0-0 instances: 22 % and 17 % behind our method). Nevertheless, our industrial context does not allow such a time budget as the resolution is part of a larger process.

Secondly, LS-tempo shows good performances and has often the best solutions on both instance sets (21 times the best solution, compared to 16 for CPO and 7 for LNS). On Squillaci et al. instances, while our solver is the worst over instances with periodic requests only, it is especially good for the 1000 video requests instance of concentrated target (16 % gap versus 21 % for LNS). LNS has the most balanced performances, is particularly good for the periodic-only instances, and has the best gap in average. Over our instances, LS-tempo is the best solver in average (0.5 % gap better). Therefore, the overall performance difference between LNS and LS-tempo is not clear since LNS seems to be good in average, but LS-tempo finds the best solution more often.

It should be noted that the low efficiency of LS-tempo on periodic-only instances is the consequence of a comparatively smaller number of successful acquisition insertion using the CP-SAT solver. Even when allowing our method to run for up to an hour and with a larger fail limit for the solver, results on the large periodic-only instances solely improved the gap by at most 1 %.

### 5.3.2 Impact of the CP-SAT Solver

We assessed the advantages of using Tempo inside our approach. Hereafter, LS-tempo refers to our method when it includes calls to Tempo and Greedy is our method without calls to Tempo.

Over Squillaci et al. instances, LS-tempo, the impact is significant. We observe a 0.9 % gap improvement in average, with LS-tempo giving better results on all but two instances. Averaging the gap makes the differences between the two solvers smaller, as 15 instances over the 32 are solved optimally with the base solver (see Table 4 for data on a subset of instances).

Over our set of instances, however, the advantage of using Tempo is not as clear. We observe no difference in the average gap of LS-tempo and Greedy. Indeed, the method makes a very high number of calls to Tempo with a very low success rate. In other words, the
3:14 Solving AEOSSP with CP and Local Search

<table><caption>Table 2 Profit and gap of the solutions found by CPO, LNS and LS-tempo over Squillaci et al.'s instances. Optimal profit is noted with a star (*). For the sake of clarity, only instances where at least one solver has not found the optimal solution are shown.</caption><thead><tr><th rowspan="2">|R|</th><th rowspan="2">OS</th><th rowspan="2">V</th><th rowspan="2">S</th><th rowspan="2">P</th><th colspan="2">CPO</th><th colspan="2">LNS</th><th colspan="2">LS-tempo</th></tr><tr><th>profit</th><th>gap</th><th>profit</th><th>gap</th><th>profit</th><th>gap</th></tr></thead><tbody><tr><td>500</td><td>500</td><td>0</td><td>0</td><td>0</td><td><strong>5070*</strong></td><td>0.00</td><td>5069</td><td>&lt;0.01</td><td><strong>5070*</strong></td><td>0.00</td></tr><tr><td>1000</td><td>1000</td><td>0</td><td>0</td><td>0</td><td>10165</td><td>0.13</td><td>11382</td><td>0.03</td><td><strong>11536</strong></td><td>0.01</td></tr><tr><td>500</td><td>0</td><td>500</td><td>0</td><td>0</td><td>21176</td><td>0.01</td><td>20988</td><td>0.02</td><td><strong>21200</strong></td><td>0.01</td></tr><tr><td>1000</td><td>0</td><td>1000</td><td>0</td><td>0</td><td>40280</td><td>0.39</td><td>52024</td><td>0.21</td><td><strong>55367</strong></td><td>0.16</td></tr><tr><td>250</td><td>0</td><td>0</td><td>0</td><td>250</td><td><strong>4100</strong></td><td>0.03</td><td>4018</td><td>0.05</td><td>3946</td><td>0.07</td></tr><tr><td>500</td><td>0</td><td>0</td><td>0</td><td>500</td><td>10856</td><td>0.12</td><td><strong>11072</strong></td><td>0.10</td><td>10512</td><td>0.15</td></tr><tr><td>1000</td><td>0</td><td>0</td><td>0</td><td>1000</td><td>14643</td><td>0.33</td><td><strong>15415</strong></td><td>0.29</td><td>13953</td><td>0.36</td></tr><tr><td>570</td><td>120</td><td>150</td><td>270</td><td>30</td><td>22379</td><td>0.02</td><td>22409</td><td>0.02</td><td><strong>22585</strong></td><td>0.01</td></tr><tr><td>1140</td><td>240</td><td>300</td><td>540</td><td>60</td><td>13075</td><td>0.19</td><td><strong>16223</strong></td><td>&lt;0.01</td><td>16220</td><td>&lt;0.01</td></tr><tr><td>500</td><td>500</td><td>0</td><td>0</td><td>0</td><td><strong>9270*</strong></td><td>0.00</td><td>9263</td><td>&lt;0.01</td><td>9267</td><td>&lt;0.01</td></tr><tr><td>1000</td><td>1000</td><td>0</td><td>0</td><td>0</td><td>13409</td><td>0.26</td><td>17920</td><td>0.02</td><td><strong>18055</strong></td><td>0.01</td></tr><tr><td>250</td><td>0</td><td>250</td><td>0</td><td>0</td><td><strong>18500*</strong></td><td>0.00</td><td>18456</td><td>&lt;0.01</td><td><strong>18500*</strong></td><td>0.00</td></tr><tr><td>500</td><td>0</td><td>500</td><td>0</td><td>0</td><td><strong>36592</strong></td><td>0.01</td><td>36304</td><td>0.02</td><td>36420</td><td>0.02</td></tr><tr><td>1000</td><td>0</td><td>1000</td><td>0</td><td>0</td><td>51732</td><td>0.29</td><td>67868</td><td>0.07</td><td><strong>68564</strong></td><td>0.06</td></tr><tr><td>250</td><td>0</td><td>0</td><td>0</td><td>250</td><td><strong>6445*</strong></td><td>0.00</td><td>6442</td><td>&lt;0.01</td><td>6388</td><td>0.01</td></tr><tr><td>500</td><td>0</td><td>0</td><td>0</td><td>500</td><td>12024</td><td>0.10</td><td><strong>12307</strong></td><td>0.08</td><td>11662</td><td>0.13</td></tr><tr><td>1000</td><td>0</td><td>0</td><td>0</td><td>1000</td><td>17410</td><td>0.35</td><td><strong>19385</strong></td><td>0.27</td><td>18055</td><td>0.32</td></tr><tr><td>570</td><td>120</td><td>150</td><td>270</td><td>30</td><td>22132</td><td>&lt;0.01</td><td>22152</td><td>&lt;0.01</td><td><strong>22187</strong></td><td>&lt;0.01</td></tr><tr><td>1140</td><td>240</td><td>300</td><td>540</td><td>60</td><td>31666</td><td>0.29</td><td>43828</td><td>0.02</td><td><strong>43899</strong></td><td>0.02</td></tr></tbody><tfoot><tr><td colspan="5">Average</td><td>0.134</td><td></td><td>0.064</td><td></td><td>0.070</td><td></td></tr></tfoot></table>

<table><caption>Table 3 Profit and gap of the solutions found by CPO, LNS and LS-tempo over our instances. Optimal profit is noted with a star (*).</caption><thead><tr><th rowspan="2">Set</th><th rowspan="2">|R|</th><th colspan="2">CPO</th><th colspan="2">LNS</th><th colspan="2">LS-tempo</th></tr><tr><th>profit</th><th>gap</th><th>profit</th><th>gap</th><th>profit</th><th>gap</th></tr></thead><tbody><tr><td rowspan="4">antilles</td><td>50</td><td><strong>20104</strong></td><td>&lt;0.01</td><td>20050,6</td><td>0,01</td><td>20090</td><td>&lt;0.01</td></tr><tr><td>100</td><td><strong>36480</strong></td><td>0,02</td><td>36192,6</td><td>0,03</td><td>36328</td><td>0,02</td></tr><tr><td>250</td><td>71324</td><td>0,30</td><td>73033,8</td><td>0,28</td><td><strong>74035</strong></td><td>0,27</td></tr><tr><td>500</td><td>81745</td><td>0,60</td><td><strong>89858,4</strong></td><td>0,56</td><td>88222</td><td>0,57</td></tr><tr><td rowspan="4">sahara</td><td>50</td><td><strong>17751</strong></td><td>0,01</td><td>17725</td><td>0,01</td><td>17743</td><td>0,01</td></tr><tr><td>100</td><td><strong>38702</strong></td><td>0,03</td><td>38393,6</td><td>0,04</td><td>38570</td><td>0,03</td></tr><tr><td>250</td><td>73972</td><td>0,32</td><td>75885,2</td><td>0,30</td><td><strong>76020</strong></td><td>0,30</td></tr><tr><td>500</td><td>76581</td><td>0,61</td><td><strong>87462,4</strong></td><td>0,56</td><td>85559</td><td>0,57</td></tr><tr><td rowspan="4">fountains</td><td>50</td><td><strong>20304</strong></td><td>0,01</td><td>20265,4</td><td>0,01</td><td>20287</td><td>0,01</td></tr><tr><td>100</td><td><strong>37048</strong></td><td>0,02</td><td>36897,8</td><td>0,02</td><td>37014</td><td>0,02</td></tr><tr><td>250</td><td>90934</td><td>0,15</td><td>95060,6</td><td>0,11</td><td><strong>97721</strong></td><td>0,08</td></tr><tr><td>500</td><td>106102</td><td>0,52</td><td>141014,6</td><td>0,37</td><td><strong>141331</strong></td><td>0,37</td></tr><tr><td rowspan="4">military</td><td>50</td><td><strong>22467*</strong></td><td>0.00</td><td>22442,2</td><td>&lt;0.01</td><td><strong>22467*</strong></td><td>0.00</td></tr><tr><td>100</td><td><strong>38489*</strong></td><td>0.00</td><td>38447</td><td>&lt;0.01</td><td><strong>38489*</strong></td><td>0.00</td></tr><tr><td>250</td><td>102849</td><td>&lt;0.01</td><td>101945,6</td><td>0,01</td><td><strong>102868</strong></td><td>&lt;0.01</td></tr><tr><td>500</td><td>206813</td><td>0,03</td><td>207729,2</td><td>0,03</td><td><strong>211080</strong></td><td>0,01</td></tr><tr><td rowspan="4">world heritage</td><td>50</td><td><strong>18222*</strong></td><td>0.00</td><td>18213,8</td><td>&lt;0.01</td><td><strong>18222*</strong></td><td>0.00</td></tr><tr><td>100</td><td><strong>36699</strong></td><td>&lt;0.01</td><td>36655,4</td><td>&lt;0.01</td><td>36691</td><td>&lt;0.01</td></tr><tr><td>250</td><td>103648</td><td>0,02</td><td>103253,8</td><td>0,02</td><td><strong>103860</strong></td><td>0,01</td></tr><tr><td>500</td><td>185196</td><td>0,09</td><td>192808,4</td><td>0,05</td><td><strong>197782</strong></td><td>0,03</td></tr></tbody><tfoot><tr><td colspan="5">Average</td><td>0.136</td><td></td><td>0.120</td><td></td><td>0.115</td><td></td></tr></tfoot></table>

TSPTW sub-problems are either easily solved by the greedy insertion, or are very hard to solve, and hence using a complete solver is not worth the effort. Full details on those results are given in appendix B.
<table><caption>**Table 4** Average gap, average number of restart (r), average number of calls to Tempo (t), average success rate when calling Tempo (s), time spent in the solver (Ts) and time ratio spent in modelling the sub-problem with the solver (Tm) for various fail limits. For Squillaci et al. instances, we only used the instances where at least one of the solvers did not find the optimal solution</caption><thead><tr><th rowspan="2">Fail limit</th><th colspan="6">Squillaci et al. instances</th><th colspan="6">Our instances</th></tr><tr><th>Gap</th><th>r</th><th>t</th><th>s</th><th>Ts</th><th>Tm</th><th>Gap</th><th>r</th><th>t</th><th>s</th><th>Ts</th><th>Tm</th></tr></thead><tbody><tr><td>0</td><td>0.089</td><td>2507</td><td>-</td><td>-</td><td>-</td><td>-</td><td>0.115</td><td>45772</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>50</td><td>0.070</td><td>337</td><td>153300</td><td>47.6%</td><td>32%</td><td>15%</td><td>0.115</td><td>5302</td><td>1341790</td><td>7.68%</td><td>21%</td><td>54%</td></tr><tr><td>100</td><td>0.071</td><td>264</td><td>104603</td><td>48.0%</td><td>36%</td><td>13%</td><td>0.115</td><td>3047</td><td>851625</td><td>7.81%</td><td>26%</td><td>48%</td></tr><tr><td>500</td><td>0.071</td><td>251</td><td>122940</td><td>50.1%</td><td>51%</td><td>8%</td><td>0.115</td><td>5418</td><td>1046200</td><td>8.10%</td><td>41%</td><td>40%</td></tr><tr><td>1000</td><td>0.074</td><td>233</td><td>114420</td><td>50.6%</td><td>56%</td><td>7%</td><td>0.115</td><td>4649</td><td>946012</td><td>8.15%</td><td>48%</td><td>34%</td></tr><tr><td>10000</td><td>0.083</td><td>208</td><td>123406</td><td>50.9%</td><td>65%</td><td>5%</td><td>0.116</td><td>3665</td><td>525106</td><td>8.20%</td><td>66%</td><td>19%</td></tr><tr><td>100000</td><td>0.089</td><td>188</td><td>113339</td><td>51.5%</td><td>69%</td><td>5%</td><td>0.118</td><td>3364</td><td>414748</td><td>8.26%</td><td>73%</td><td>14%</td></tr></tbody></table>

Table 4 shows the impact of the fail limit given to Tempo. We can see this parameter is not sensitive, since as a fail limit of 50 and 1000 yields roughly the same results. Beyond this value, the gap increases as well as the time spent calling the solver. More importantly, we note that the simple fact of using Tempo with a small fail limit dramatically improves the gap. It means that solutions to the TSPTW sub-problem solutions can be easily solved with a small tree search in about half the cases. Therefore, there is no use in increasing the fail limit too much, indicating that heuristics designed to solve TSPTW could yield even better performances than using a complete CP-SAT solver.

### 5.3.3 Memory Management Impact

Finally, Table 5 shows the comparison between the profit and the gap yielded by CPO, LS-tempo and Greedy when taking into account the memory constraints and computing a download plan. We can see that CPO loses 3.5 % on the average gap when adding these constraints, while our solver performance does not change. It means that memory constraints are not tight, and that the 6 ground stations are sufficient for the parameters we used for our instance generator. Those results are consistent with other work in the literature, which explains why memory management is often overlooked or simplified when dealing with AEOSSP [34].

## 6 Conclusion

In this paper, we presented a solver for the AEOSSP that is designed for our industrial partner Prométhée's the upcoming constellation of 20 AEOSs. This solver is able to tackle two sub-problems of AEOSSP, namely acquisition selection and download planning. Acquisition selection is solved by a local search procedure, which is based on greedily solving a sequence of TSPTW, with occasional help from a CP solver in order to get a maximal-profit sequence of acquisitions for each satellite. Download planning is seen as a sequence of knapsack problems, that are solved greedily. When we include the download planning, experiments showed that our solver find better solution than IBM CPO on average, especially on larger instances. Overall, with and without the download planning, IBM CPO unsurprisingly does not scale very much. We show that including calls to a CP-SAT solver inside our solver lead to an improvement on average, but these improvements depend on the type of instances. Also, the type of instances is important to choose which solver to use. Especially we show that while our solver is not good on period requests only, it exhibits state-of-the-art capabilities on other types of instances.
<table><caption>Table 5 Result on our set of instance with memory management</caption><thead><tr><th rowspan="2">Set</th><th rowspan="2">|R|</th><th colspan="2">CPO</th><th colspan="2">Greedy</th><th colspan="2">LS-tempo</th></tr><tr><th>profit</th><th>gap</th><th>profit</th><th>gap</th><th>profit</th><th>gap</th></tr></thead><tbody><tr><td rowspan="4">antilles</td><td>50</td><td><b>20102</b></td><td>&lt;0.01</td><td>20089</td><td>&lt;0.01</td><td>20087</td><td>0.01</td></tr><tr><td>100</td><td>36323</td><td>0.02</td><td>36308</td><td>0.02</td><td><b>36326</b></td><td>0.02</td></tr><tr><td>250</td><td>69674</td><td>0.31</td><td><b>74115</b></td><td>0.27</td><td>73929</td><td>0.27</td></tr><tr><td>500</td><td>67979</td><td>0.67</td><td><b>89069</b></td><td>0.56</td><td>88329</td><td>0.57</td></tr><tr><td rowspan="4">sahara</td><td>50</td><td><b>17748</b></td><td>0.01</td><td>17736</td><td>0.01</td><td>17744</td><td>0.01</td></tr><tr><td>100</td><td>38517</td><td>0.03</td><td><b>38568</b></td><td>0.03</td><td>38564</td><td>0.03</td></tr><tr><td>250</td><td>73805</td><td>0.32</td><td><b>76101</b></td><td>0.30</td><td>76036</td><td>0.30</td></tr><tr><td>500</td><td>68814</td><td>0.65</td><td><b>86572</b></td><td>0.56</td><td>85834</td><td>0.57</td></tr><tr><td rowspan="4">fountains</td><td>50</td><td><b>20301</b></td><td>0.01</td><td>20282</td><td>0.01</td><td>20289</td><td>0.01</td></tr><tr><td>100</td><td>36939</td><td>0.02</td><td>36991</td><td>0.02</td><td><b>37012</b></td><td>0.02</td></tr><tr><td>250</td><td>84771</td><td>0.21</td><td>97456</td><td>0.09</td><td><b>97703</b></td><td>0.09</td></tr><tr><td>500</td><td>93629</td><td>0.58</td><td><b>142525</b></td><td>0.36</td><td>141493</td><td>0.36</td></tr><tr><td rowspan="4">military</td><td>50</td><td><b>22467*</b></td><td>0.00</td><td><b>22467*</b></td><td>0.00</td><td><b>22467*</b></td><td>0.00</td></tr><tr><td>100</td><td><b>38489*</b></td><td>0.00</td><td>38488</td><td>&lt;0.01</td><td><b>38489*</b></td><td>0.00</td></tr><tr><td>250</td><td>100592</td><td>0.03</td><td>102838</td><td>&lt;0.01</td><td><b>102865</b></td><td>&lt;0.01</td></tr><tr><td>500</td><td>165914</td><td>0.23</td><td>211001</td><td>0.02</td><td><b>211088</b></td><td>0.01</td></tr><tr><td rowspan="4">world heritage</td><td>50</td><td><b>18222*</b></td><td>0.00</td><td>18217</td><td>&lt;0.01</td><td><b>18222*</b></td><td>0.00</td></tr><tr><td>100</td><td><b>36692</b></td><td>&lt;0.01</td><td>36686</td><td>&lt;0.01</td><td>36691</td><td>&lt;0.01</td></tr><tr><td>250</td><td>98776</td><td>0.06</td><td>103766</td><td>0.01</td><td><b>103856</b></td><td>0.01</td></tr><tr><td>500</td><td>152770</td><td>0.25</td><td>197722</td><td>0.03</td><td><b>197794</b></td><td>0.03</td></tr><tr><td colspan="2">Average</td><td>0.170</td><td></td><td>0.115</td><td></td><td>0.116</td><td></td></tr></tbody></table>

Finally, further work could focus on adding different moves and variations to our solver. We did experiment the resolution of the orienteering problem with our CP solver, but it does not scale for this problem today. We also would like to use it for the insertion of several acquisitions, in order to make its use more efficient by decreasing the number of calls.

References

1 Nicola Bianchessi and Giovanni Righini. Planning and Scheduling Algorithms for the COSMO-SkyMed Constellation. *Aerospace Science and Technology*, 12(7):535-544, 2008. doi:10.1016/j.ast.2008.01.001.

2 Jiawei Chen, Ming Chen, Jun Wen, Lei He, and Xiaolu Liu. A Heuristic Construction Neural Network Method for the Time-Dependent Agile Earth Observation Satellite Scheduling Problem. *Mathematics*, 10(19):3498, 2022. doi:10.3390/math10193498.

3 Xiaogeng Chu, Yuning Chen, and Lining Xing. A Branch and Bound Algorithm for Agile Earth Observation Satellite Scheduling. *Discrete Dynamics in Nature and Society*, 2017, 2017. doi:10.1155/2017/7345941.

4 J. F. Cordeau and G. Laporte. Maximizing the Value of an Earth Observation Satellite Orbit. *The Journal of the Operational Research Society*, 56(8):962-968, 2005. doi:10.1057/PALGRAVE.JORS.2601926.

5 Kaikai Cui, Junhua Xiang, and Yulin Zhang. Mission Planning Optimization of Video Satellite for Ground Multi-Object Staring Imaging. *Advances in Space Research*, 61(6):1476-1489, 2018. doi:10.1016/j.asr.2017.10.056.

6 Duncan Eddy and Mykel J. Kochenderfer. A Maximum Independent Set Method for Scheduling Earth-Observing Satellite Constellations. *Journal of Spacecraft and Rockets*, 58(5):1416-1429, 2021. doi:10.2514/1.A34931.
7 Yanxiang Feng, Ruipeng Zhang, Sida Ren, Shuailin Zhu, and Yikang Yang. A Distributed Approach for Time-Dependent Observation Scheduling Problem in the Agile Earth Observation Satellite Constellation. *Remote Sensing*, 15(7):1761, 2023. doi:10.3390/rs15071761.

8 Mohamed Elamine Galloua, Shuai Li, and Jiahao Cui. Earth Observation Satellite Imaging Task Scheduling with Metaheuristics: Multi-Level Clustering and Priority-Driven Pre-Scheduling. *Advances in Space Research*, 2024. doi:10.1016/j.asr.2024.11.023.

9 Lei He, Xiaolu Liu, Gilbert Laporte, Yingwu Chen, and Yingguo Chen. An Improved Adaptive Large Neighborhood Search Algorithm for Multiple Agile Satellites Scheduling. *Computers & Operations Research*, 100:12-25, 2018. doi:10.1016/j.cor.2018.06.020.

10 Lijun He, Ben Liang, Jiandong Li, and Min Sheng. Joint Observation and Transmission Scheduling in Agile Satellite Networks. *IEEE Transactions on Mobile Computing*, 21(12):4381-4396, 2022. doi:10.1109/TMC.2021.3076088.

11 Chae-Hyeon Kim, Sung Jun Kim, and Han-Lim Choi. Optimal Integrated Scheduling of Observation and Download Tasks for Multiple Satellites with Memory Constraints. In *2024 IEEE 20th International Conference on Automation Science and Engineering (CASE)*, pages 2287-2294, 2024. doi:10.1109/CASE59546.2024.10711478.

12 Junhong Kim, Doo-Hyun Cho, Jaemyung Ahn, and Han-Lim Choi. Task Scheduling of Multiple Agile Satellites with Transition Time and Stereo Imaging Constraints, 2019. doi: 10.48550/arXiv.1912.00374.

13 Michel Lemaître, Gérard Verfaillie, Frank Jouhaud, Jean-Michel Lachiver, and Nicolas Bataille. Selecting and Scheduling Observations of Agile Satellites. *Aerospace Science and Technology*, 6(5):367-381, 2002. doi:10.1016/S1270-9638(02)01173-2.

14 Rich Levinson, Sreeja Nag, and Vinay Ravindra. Agile Satellite Planning for Multi-Payload Observations for Earth Science, 2021. doi:10.48550/arXiv.2111.07042.

15 Hai Li, Yongjun Li, Yuanhao Liu, Kai Zhang, Xin Li, Yu Li, and Shanghong Zhao. A Multi-Objective Dynamic Mission-Scheduling Algorithm Considering Perturbations for Earth Observation Satellites. *Aerospace*, 11(8):643, 2024. doi:10.3390/aerospace11080643.

16 Longmei Li, Feng Yao, Ning Jing, and Michael Emmerich. Preference Incorporation to Solve Multi-Objective Mission Planning of Agile Earth Observation Satellites. In *Proceedings of the 2017 IEEE Congress on Evolutionary Computation (CEC)*, pages 1366-1373, 2017. doi:10.1109/CEC.2017.7969463.

17 Wei-Chen Lin and Da-Yin Liao. A Tabu Search Algorithm for Satellite Imaging Scheduling. In *2004 IEEE International Conference on Systems, Man and Cybernetics*, volume 2, pages 1601-1606, 2004. doi:10.1109/ICSMC.2004.1399860.

18 Wei-Cheng Lin, Chung-Yang Liu, Da-Yin Liao, and Yung-Yao Lee. Daily Imaging Scheduling of an Earth Observation Satellite. In *Proceedings of the 2003 IEEE International Conference on Systems, Man and Cybernetics (SMC)*, volume 2, pages 1886-1891 vol.2, 2003. doi: 10.1109/ICSMC.2003.1244686.

19 Lorena Linares, Rafael Vazquez, Federico Perea, and Jorge Galán-Vioque. A Mixed Integer Linear Programming Model for Resolution of the Antenna-Satellite Scheduling Problem. *IEEE Transactions on Aerospace and Electronic Systems*, 60(1):463-473, 2024. doi:10.1109/TAES.2023.3326422.

20 Lihao Liu, Zhenghong Dong, Haoxiang Su, and Dingzhan Yu. A Study of Distributed Earth Observation Satellites Mission Scheduling Method Based on Game-Negotiation Mechanism. *Sensors*, 21(19):6660, 2021. doi:10.3390/s21196660.

21 Xiaolu Liu, Gilbert Laporte, Yingwu Chen, and Renjie He. An Adaptive Large Neighborhood Search Metaheuristic for Agile Satellite Scheduling with Time-Dependent Transition Time. *Computers & Operations Research*, 86:41-53, 2017. doi:10.1016/j.cor.2017.04.006.

22 Guansheng Peng, Guopeng Song, Yongming He, Jing Yu, Shang Xiang, Lining Xing, and Pieter Vansteenwegen. Solving the Agile Earth Observation Satellite Scheduling Problem With Time-Dependent Transition Times. *IEEE Transactions on Systems, Man, and Cybernetics: Systems*, 52(3):1614-1625, 2022. doi:10.1109/TSMC.2020.3031738.
3:18 Solving AEOSSP with CP and Local Search

23 Vishwa Shah, Vivek Vittaldev, Leon Stepan, and Cyrus Foster. Scheduling the World's Largest Earth-Observing Fleet of Medium-Resolution Imaging Satellites. In *11th International Workshop on Planning and Scheduling for Space (IWPSS)*, page 6, 2019.

24 Samuel Squillaci. *Mission plan optimization for a constellation of Earth observation satellites (Optimisation de plans de mission pour une constellation de satellites d'observation de la Terre)*. PhD thesis, Office national d'études et de recherches aérospatiales (ONERA) and Institut supérieur de l'aéronautique et de l'espace (ISAE-SUPAERO), Toulouse, France, 2023.

25 Samuel Squillaci, Cédric Pralet, and Stéphanie Roussel. Scheduling Complex Observation Requests for a Constellation of Satellites: Large Neighborhood Search Approaches. In *Proceedings of the 20th International Conference on Integration of AI and OR Techniques in Constraint Programming (CPAIOR)*, 2023. doi:10.1007/978-3-031-33271-5_29.

26 Samuel Squillaci, Stéphanie Roussel, and Cédric Pralet. Parallel Scheduling of Complex Requests for a Constellation of Earth Observing Satellites. In *PAIS 2022*, pages 100-113. IOS Press, 2022. doi:10.3233/FAIA220068.

27 Haiquan Sun, Wei Xia, Zhilong Wang, and Xiaoxuan Hu. Agile Earth Observation Satellite Scheduling Algorithm for Emergency Tasks Based on Multiple Strategies. *Journal of Systems Science and Systems Engineering*, 30(5):626-646, 2021. doi:10.1007/s11518-021-5506-4.

28 Panwadee Tangpattanakul, Nicolas Jozefowiez, and Pierre Lopez. A Multi-Objective Local Search Heuristic for Scheduling Earth Observations Taken by an Agile Satellite. *European Journal of Operational Research*, 245(2):542-554, 2015. doi:10.1016/j.ejor.2015.03.011.

29 Christopher G. Valicka, Deanna Garcia, Andrea Staid, Jean-Paul Watson, Gabriel Hackebeil, Sivakumar Rathinam, and Lewis Ntaimo. Mixed-Integer Programming Models for Optimal Constellation Scheduling given Cloud Cover Uncertainty. *European Journal of Operational Research*, 275(2):431-445, 2019. doi:10.1016/j.ejor.2018.11.043.

30 Pieter Vansteenwegen, Wouter Souffriau, Greet Vanden Berghe, and Dirk Van Oudheusden. Iterated Local Search for the Team Orienteering Problem with Time Windows. *Computers & Operations Research*, 36(12):3281-3290, 2009. doi:10.1016/j.cor.2009.03.008.

31 Petr Vilím, Philippe Laborie, and Paul Shaw. Failure-Directed Search for Constraint-Based Scheduling. In *Proceedings of the 12th International Conference on Integration of AI and OR Techniques in Constraint Programming (CPAIOR)*, pages 437-453, 2015. doi:10.1007/978-3-319-18008-3_30.

32 Jianjiang Wang, Erik Demeulemeester, and Dishan Qiu. A Pure Proactive Scheduling Algorithm for Multiple Earth Observation Satellites under Uncertainties of Clouds. *Computers & Operations Research*, 74:1-13, 2016. doi:10.1016/j.cor.2016.04.014.

33 Xinwei Wang, Guopeng Song, Roel Leus, and Chao Han. Robust Earth Observation Satellite Scheduling With Uncertainty of Cloud Coverage. *IEEE Transactions on Aerospace and Electronic Systems*, 56(3):2450-2461, 2020. doi:10.1109/TAES.2019.2947978.

34 Xinwei Wang, Guohua Wu, Lining Xing, and Witold Pedrycz. Agile Earth Observation Satellite Scheduling Over 20 Years: Formulations, Methods, and Future Directions. *IEEE Systems Journal*, 15(3):3881-3892, 2021. doi:10.1109/JSYST.2020.2997050.

35 Damien Wojtowicz. AEOSSP Instance Generator. Dataset, France Relance grant (project JA-PETUS), swhId: swh:1:dir:c1c87cf9c3a3e7ffe616bdffdc9c52af9e30cb35 (visited on 2025-07-24). URL: https://github.com/ssquilla/Earth_Observing_Satellites_benchmarks, doi:10.4230/artifacts.24101.

36 Fatos Xhafa and Andrew W.H. Ip. Optimisation Problems and Resolution Methods in Satellite Scheduling and Space-Craft Operation: A Survey. *Enterprise Information Systems*, 15(8):1022-1045, 2021. doi:10.1080/17517575.2019.1593508.

37 Wenyuan Zhang and Gangtie Zheng. Scheduling an Agile Multipayload Earth-Observing Satellite. *Journal of Spacecraft and Rockets*, 61(1):143-156, 2024. doi:10.2514/1.A35726.
A Instances Details

Table 6 Generated instances details. It shows, for each instance, its set of POIs, the number of requests $|R|$, of periodic requests P, of multi-mesh requests M, of downloads $|W|$, of acquisition opportunities $|A|$, of acquisitions needed to satisfy all the requests $s(A)$, of connected components nc, the average size of the components sc, and the average number of acquisition opportunities per target ar.

<table><thead><tr><th>Set</th><th>|R|</th><th>P</th><th>M</th><th>|W|</th><th>|A|</th><th>s(A)</th><th>nc</th><th>sc</th><th>ar</th></tr></thead><tbody><tr><td rowspan="4">antilles</td><td>50</td><td>11</td><td>2</td><td>60</td><td>1017</td><td>70</td><td>19</td><td>54</td><td>15</td></tr><tr><td>100</td><td>18</td><td>4</td><td>60</td><td>1993</td><td>133</td><td>19</td><td>105</td><td>15</td></tr><tr><td>250</td><td>54</td><td>17</td><td>60</td><td>5313</td><td>370</td><td>19</td><td>280</td><td>14</td></tr><tr><td>500</td><td>88</td><td>29</td><td>60</td><td>10510</td><td>717</td><td>19</td><td>553</td><td>15</td></tr><tr><td rowspan="4">sahara</td><td>50</td><td>3</td><td>4</td><td>74</td><td>872</td><td>59</td><td>22</td><td>40</td><td>15</td></tr><tr><td>100</td><td>18</td><td>10</td><td>74</td><td>1857</td><td>147</td><td>23</td><td>81</td><td>13</td></tr><tr><td>250</td><td>43</td><td>19</td><td>89</td><td>4455</td><td>361</td><td>23</td><td>193</td><td>13</td></tr><tr><td>500</td><td>89</td><td>39</td><td>74</td><td>9043</td><td>721</td><td>23</td><td>393</td><td>13</td></tr><tr><td rowspan="4">fountains</td><td>50</td><td>9</td><td>3</td><td>82</td><td>1692</td><td>67</td><td>31</td><td>55</td><td>25</td></tr><tr><td>100</td><td>14</td><td>4</td><td>82</td><td>3273</td><td>133</td><td>32</td><td>102</td><td>25</td></tr><tr><td>250</td><td>51</td><td>14</td><td>82</td><td>8372</td><td>359</td><td>32</td><td>262</td><td>23</td></tr><tr><td>500</td><td>112</td><td>33</td><td>82</td><td>17037</td><td>748</td><td>32</td><td>532</td><td>23</td></tr><tr><td rowspan="4">military</td><td>50</td><td>10</td><td>6</td><td>159</td><td>1503</td><td>83</td><td>104</td><td>14</td><td>18</td></tr><tr><td>100</td><td>22</td><td>2</td><td>164</td><td>2648</td><td>140</td><td>108</td><td>24</td><td>19</td></tr><tr><td>250</td><td>48</td><td>4</td><td>165</td><td>6735</td><td>347</td><td>141</td><td>48</td><td>19</td></tr><tr><td>500</td><td>97</td><td>40</td><td>163</td><td>14039</td><td>741</td><td>163</td><td>86</td><td>19</td></tr><tr><td rowspan="4">world heritage</td><td>50</td><td>4</td><td>4</td><td>158</td><td>1729</td><td>67</td><td>119</td><td>14</td><td>26</td></tr><tr><td>100</td><td>17</td><td>1</td><td>160</td><td>2952</td><td>130</td><td>135</td><td>22</td><td>23</td></tr><tr><td>250</td><td>40</td><td>20</td><td>164</td><td>8153</td><td>360</td><td>136</td><td>59</td><td>23</td></tr><tr><td>500</td><td>85</td><td>38</td><td>166</td><td>15979</td><td>717</td><td>133</td><td>120</td><td>22</td></tr></tbody></table>
3:20 Solving AEOSSP with CP and Local Search

<table><caption>**Table 7** Squillaci et al. instances details. It shows, for each instance, the number of request $|R|$, of one-shot requests OS, video requests V, stereoscopic requests S and periodic requests P, of downloads $|W|$, of acquisition opportunities $|A|$, of acquisitions needed to satisfy all the requests $s(A)$, of connected components nc, the average size of the components sc(when $sc > 1$), and of acquisition opportunities per target ar. The first part of this table is about the concentrated instances and the second part is about the spread instances.</caption><thead><tr><th>|R|</th><th>OS</th><th>V</th><th>S</th><th>P</th><th>|W|</th><th>|A|</th><th>s(A)</th><th>nc</th><th>sc</th><th>ar</th></tr></thead><tbody><tr><td>50</td><td>50</td><td>0</td><td>0</td><td>0</td><td>123</td><td>2607</td><td>50</td><td>124</td><td>23</td><td>50</td></tr><tr><td>250</td><td>250</td><td>0</td><td>0</td><td>0</td><td>123</td><td>13149</td><td>250</td><td>127</td><td>112</td><td>52</td></tr><tr><td>500</td><td>500</td><td>0</td><td>0</td><td>0</td><td>123</td><td>25646</td><td>500</td><td>116</td><td>221</td><td>51</td></tr><tr><td>1000</td><td>1000</td><td>0</td><td>0</td><td>0</td><td>123</td><td>51189</td><td>1000</td><td>117</td><td>437</td><td>51</td></tr><tr><td>50</td><td>0</td><td>50</td><td>0</td><td>0</td><td>123</td><td>2436</td><td>50</td><td>115</td><td>21</td><td>46</td></tr><tr><td>250</td><td>0</td><td>250</td><td>0</td><td>0</td><td>123</td><td>12162</td><td>250</td><td>114</td><td>107</td><td>48</td></tr><tr><td>500</td><td>0</td><td>500</td><td>0</td><td>0</td><td>123</td><td>25554</td><td>500</td><td>118</td><td>216</td><td>51</td></tr><tr><td>1000</td><td>0</td><td>1000</td><td>0</td><td>0</td><td>123</td><td>49149</td><td>1000</td><td>116</td><td>424</td><td>49</td></tr><tr><td>50</td><td>0</td><td>0</td><td>0</td><td>50</td><td>123</td><td>576</td><td>150</td><td>26</td><td>18</td><td>3</td></tr><tr><td>250</td><td>0</td><td>0</td><td>0</td><td>250</td><td>123</td><td>2367</td><td>750</td><td>25</td><td>91</td><td>3</td></tr><tr><td>500</td><td>0</td><td>0</td><td>0</td><td>500</td><td>123</td><td>4794</td><td>1501</td><td>28</td><td>168</td><td>3</td></tr><tr><td>1000</td><td>0</td><td>0</td><td>0</td><td>1000</td><td>123</td><td>9777</td><td>3000</td><td>27</td><td>359</td><td>3</td></tr><tr><td>57</td><td>12</td><td>15</td><td>27</td><td>3</td><td>123</td><td>2125</td><td>90</td><td>112</td><td>19</td><td>22</td></tr><tr><td>285</td><td>60</td><td>75</td><td>135</td><td>1</td><td>123</td><td>10327</td><td>450</td><td>115</td><td>90</td><td>23</td></tr><tr><td>570</td><td>120</td><td>150</td><td>270</td><td>30</td><td>123</td><td>19203</td><td>900</td><td>117</td><td>164</td><td>21</td></tr><tr><td>1140</td><td>240</td><td>300</td><td>540</td><td>60</td><td>123</td><td>45985</td><td>1800</td><td>111</td><td>414</td><td>25</td></tr><tr><td>50</td><td>50</td><td>0</td><td>0</td><td>0</td><td>123</td><td>2438</td><td>50</td><td>115</td><td>21</td><td>46</td></tr><tr><td>250</td><td>250</td><td>0</td><td>0</td><td>0</td><td>123</td><td>12269</td><td>250</td><td>118</td><td>104</td><td>49</td></tr><tr><td>500</td><td>500</td><td>0</td><td>0</td><td>0</td><td>123</td><td>24475</td><td>500</td><td>119</td><td>206</td><td>49</td></tr><tr><td>1000</td><td>1000</td><td>0</td><td>0</td><td>0</td><td>123</td><td>49035</td><td>1000</td><td>121</td><td>405</td><td>50</td></tr><tr><td>50</td><td>0</td><td>50</td><td>0</td><td>0</td><td>123</td><td>2427</td><td>50</td><td>115</td><td>21</td><td>46</td></tr><tr><td>250</td><td>0</td><td>250</td><td>0</td><td>0</td><td>123</td><td>12190</td><td>250</td><td>118</td><td>103</td><td>48</td></tr><tr><td>500</td><td>0</td><td>500</td><td>0</td><td>0</td><td>123</td><td>24326</td><td>500</td><td>119</td><td>204</td><td>48</td></tr><tr><td>1000</td><td>0</td><td>1000</td><td>0</td><td>0</td><td>123</td><td>48686</td><td>1000</td><td>120</td><td>406</td><td>49</td></tr><tr><td>50</td><td>0</td><td>0</td><td>0</td><td>50</td><td>123</td><td>568</td><td>150</td><td>27</td><td>17</td><td>3</td></tr><tr><td>250</td><td>0</td><td>0</td><td>0</td><td>250</td><td>123</td><td>2348</td><td>750</td><td>27</td><td>83</td><td>3</td></tr><tr><td>500</td><td>0</td><td>0</td><td>0</td><td>500</td><td>123</td><td>4594</td><td>1501</td><td>28</td><td>161</td><td>3</td></tr><tr><td>1000</td><td>0</td><td>0</td><td>0</td><td>1000</td><td>123</td><td>9162</td><td>3004</td><td>28</td><td>324</td><td>3</td></tr><tr><td>57</td><td>12</td><td>15</td><td>27</td><td>3</td><td>123</td><td>2025</td><td>90</td><td>115</td><td>18</td><td>21</td></tr><tr><td>285</td><td>60</td><td>75</td><td>135</td><td>15</td><td>123</td><td>10467</td><td>451</td><td>119</td><td>88</td><td>23</td></tr><tr><td>570</td><td>120</td><td>150</td><td>270</td><td>30</td><td>123</td><td>20820</td><td>900</td><td>118</td><td>176</td><td>23</td></tr><tr><td>1140</td><td>240</td><td>300</td><td>540</td><td>60</td><td>123</td><td>41693</td><td>1800</td><td>119</td><td>350</td><td>23</td></tr></tbody></table>

B Results Tables

Table 8 shows the profit and the gap yielded by both methods on Squillaci et al. instances, while Table 8 shows it on our instances, both using a fail limit of 50 for Tempo. The gap was computed using an upper bound calculated with the CPO model. Thanks to a naive upper bound (sum of the profit of the best opportunities for each request), the solver can prove optimality on trivial instances.

Over Squillaci et al. instances, LS-tempo has better results on all instances but 2, with an improvement of 0.9 % gap in average. Averaging the gap makes the differences between the two solvers smaller, as 15 instances out of the 32 are solved optimal with the base solver (see Table 4 for data on a subset of instances). We can see the number of restart drops with the
number of requests, especially for instances with periodic requests only. The same remark holds for the Tempo calls success rate. We note that for instance with 1000 video requests with concentrated target, tempo has only 4 % of success, nevertheless the result of LS-tempo is much better than Greedy.

Over our set of instances, the use advantage of using Tempo is not as clear. At first glance, it seems that there is a difference in the results between regional and worldwide instances. Using Tempo always seems to give the best solution, but the difference are in fact very small and the average gap for LS-tempo and Greedy are the same. Compared to the other instance set the number of restart and calls to Tempo is very high. On the contrary the success rate is very low, especially on regional datasets. It seems that instance of the sub-problem are either easily solve with the greedy insertion, or are very hard and cannot be solved with a small fail limit.

<table><caption>**Table 8** Profit, gap and number of restarts (r) found using LS-tempo and Greedy over our instances. Average values over 5 runs. A star (*) means the profit is optimal, a dash (“-”) means the instance was solved optimally during the initial descent.</caption><thead><tr><th rowspan="2">|R|</th><th rowspan="2">OS</th><th rowspan="2">V</th><th rowspan="2">S</th><th rowspan="2">P</th><th colspan="3">Greedy</th><th colspan="5">LS-tempo</th></tr><tr><th>profit</th><th>gap</th><th>r</th><th>profit</th><th>gap</th><th>r</th><th>t</th><th>s</th></tr></thead><tbody><tr><td>50</td><td>50</td><td>0</td><td>0</td><td>0</td><td><strong>390*</strong></td><td>0.00</td><td>-</td><td><strong>390*</strong></td><td>0.00</td><td>-</td><td>-</td><td>-</td></tr><tr><td>250</td><td>250</td><td>0</td><td>0</td><td>0</td><td><strong>1655*</strong></td><td>0.00</td><td>-</td><td><strong>1655*</strong></td><td>0.00</td><td>-</td><td>12</td><td>100%</td></tr><tr><td>500</td><td>500</td><td>0</td><td>0</td><td>0</td><td><strong>5070*</strong></td><td>0.00</td><td>-</td><td><strong>5070*</strong></td><td>0.00</td><td>-</td><td>26</td><td>100%</td></tr><tr><td>1000</td><td>1000</td><td>0</td><td>0</td><td>0</td><td>11440</td><td>0.02</td><td>601</td><td><strong>11536</strong></td><td>0.01</td><td>322</td><td>68427</td><td>79%</td></tr><tr><td>50</td><td>0</td><td>50</td><td>0</td><td>0</td><td><strong>4060*</strong></td><td>0.00</td><td>-</td><td><strong>4060*</strong></td><td>0.00</td><td>-</td><td>1</td><td>100%</td></tr><tr><td>250</td><td>0</td><td>250</td><td>0</td><td>0</td><td><strong>7440*</strong></td><td>0.00</td><td>-</td><td><strong>7440*</strong></td><td>0.00</td><td>-</td><td>13</td><td>100%</td></tr><tr><td>500</td><td>0</td><td>500</td><td>0</td><td>0</td><td>21040</td><td>0.01</td><td>3054</td><td><strong>21200</strong></td><td>0.01</td><td>1841</td><td>98269</td><td>89%</td></tr><tr><td>1000</td><td>0</td><td>1000</td><td>0</td><td>0</td><td>51524</td><td>0.22</td><td>441</td><td><strong>55367</strong></td><td>0.16</td><td>76</td><td>1439698</td><td>4%</td></tr><tr><td>50</td><td>0</td><td>0</td><td>0</td><td>50</td><td><strong>780*</strong></td><td>0.00</td><td>11</td><td><strong>780*</strong></td><td>0.00</td><td>-</td><td>3</td><td>100%</td></tr><tr><td>250</td><td>0</td><td>0</td><td>0</td><td>250</td><td>3777</td><td>0.11</td><td>9475</td><td><strong>3946</strong></td><td>0.07</td><td>39</td><td>37802</td><td>14%</td></tr><tr><td>500</td><td>0</td><td>0</td><td>0</td><td>500</td><td>10120</td><td>0.18</td><td>4997</td><td><strong>10512</strong></td><td>0.15</td><td>5</td><td>36189</td><td>5%</td></tr><tr><td>1000</td><td>0</td><td>0</td><td>0</td><td>1000</td><td><strong>13996</strong></td><td>0.36</td><td>1992</td><td>13953</td><td>0.36</td><td>1</td><td>34562</td><td>1%</td></tr><tr><td>57</td><td>12</td><td>15</td><td>27</td><td>3</td><td><strong>2010*</strong></td><td>0.00</td><td>-</td><td><strong>2010*</strong></td><td>0.00</td><td>-</td><td>1</td><td>100%</td></tr><tr><td>285</td><td>60</td><td>75</td><td>135</td><td>1</td><td><strong>6265*</strong></td><td>0.00</td><td>3</td><td><strong>6265*</strong></td><td>0.00</td><td>-</td><td>21</td><td>100%</td></tr><tr><td>570</td><td>120</td><td>150</td><td>270</td><td>30</td><td>22092</td><td>0.03</td><td>2414</td><td><strong>22585</strong></td><td>0.01</td><td>524</td><td>97259</td><td>60%</td></tr><tr><td>1140</td><td>240</td><td>300</td><td>540</td><td>60</td><td>16126</td><td>0.01</td><td>234</td><td><strong>16220</strong></td><td>&lt;0.01</td><td>17</td><td>24299</td><td>36%</td></tr><tr><td>50</td><td>50</td><td>0</td><td>0</td><td>0</td><td><strong>720*</strong></td><td>0.00</td><td>3</td><td><strong>720*</strong></td><td>0.00</td><td>-</td><td>4</td><td>100%</td></tr><tr><td>250</td><td>250</td><td>0</td><td>0</td><td>0</td><td><strong>4625*</strong></td><td>0.00</td><td>81</td><td><strong>4625*</strong></td><td>0.00</td><td>-</td><td>15</td><td>100%</td></tr><tr><td>500</td><td>500</td><td>0</td><td>0</td><td>0</td><td>9138</td><td>0.01</td><td>1952</td><td><strong>9267</strong></td><td>&lt;0.01</td><td>870</td><td>64068</td><td>81%</td></tr><tr><td>1000</td><td>1000</td><td>0</td><td>0</td><td>0</td><td>17833</td><td>0.02</td><td>444</td><td><strong>18055</strong></td><td>0.01</td><td>214</td><td>66872</td><td>69%</td></tr><tr><td>50</td><td>0</td><td>50</td><td>0</td><td>0</td><td><strong>2880*</strong></td><td>0.00</td><td>7</td><td><strong>2880*</strong></td><td>0.00</td><td>-</td><td>2</td><td>100%</td></tr><tr><td>250</td><td>0</td><td>250</td><td>0</td><td>0</td><td><strong>18500*</strong></td><td>0.00</td><td>65</td><td><strong>18500*</strong></td><td>0.00</td><td>7</td><td>137</td><td>89%</td></tr><tr><td>500</td><td>0</td><td>500</td><td>0</td><td>0</td><td>35416</td><td>0.04</td><td>3103</td><td><strong>36420</strong></td><td>0.02</td><td>1443</td><td>223688</td><td>65%</td></tr><tr><td>1000</td><td>0</td><td>1000</td><td>0</td><td>0</td><td>66660</td><td>0.08</td><td>317</td><td><strong>68564</strong></td><td>0.06</td><td>155</td><td>436114</td><td>17%</td></tr><tr><td>50</td><td>0</td><td>0</td><td>0</td><td>50</td><td><strong>1060*</strong></td><td>0.00</td><td>-</td><td><strong>1060*</strong></td><td>0.00</td><td>-</td><td>4</td><td>100%</td></tr><tr><td>250</td><td>0</td><td>0</td><td>0</td><td>250</td><td>6139</td><td>0.05</td><td>9243</td><td><strong>6388</strong></td><td>0.01</td><td>82</td><td>31641</td><td>41%</td></tr><tr><td>500</td><td>0</td><td>0</td><td>0</td><td>500</td><td>11177</td><td>0.17</td><td>4397</td><td><strong>11662</strong></td><td>0.13</td><td>5</td><td>28955</td><td>7%</td></tr><tr><td>1000</td><td>0</td><td>0</td><td>0</td><td>1000</td><td><strong>18078</strong></td><td>0.32</td><td>1964</td><td>18055</td><td>0.32</td><td>1</td><td>28728</td><td>2%</td></tr><tr><td>57</td><td>12</td><td>15</td><td>27</td><td>3</td><td><strong>1765*</strong></td><td>0.00</td><td>-</td><td><strong>1765*</strong></td><td>0.00</td><td>-</td><td>1</td><td>100%</td></tr><tr><td>285</td><td>60</td><td>75</td><td>135</td><td>15</td><td><strong>12210*</strong></td><td>0.00</td><td>24</td><td><strong>12210*</strong></td><td>0.00</td><td>1</td><td>43</td><td>95%</td></tr><tr><td>570</td><td>120</td><td>150</td><td>270</td><td>30</td><td>22048</td><td>0.01</td><td>2468</td><td><strong>22187</strong></td><td>&lt;0.01</td><td>701</td><td>110152</td><td>84%</td></tr><tr><td>1140</td><td>240</td><td>300</td><td>540</td><td>60</td><td>42908</td><td>0.04</td><td>480</td><td><strong>43899</strong></td><td>0.02</td><td>105</td><td>85822</td><td>62%</td></tr></tbody><tfoot><tr><td colspan="6">Average</td><td>0.053</td><td></td><td>0.042</td><td></td><td></td><td>67.6%</td></tr></tfoot></table>
3:22 Solving AEOSSP with CP and Local Search

<table><caption>Table 9 Profit, gap and number of restarts (r) found using LS-tempo and Greedy over our instances. Average values over 5 runs. A star (*) means the profit is optimal, a dash (“-”) means the instance was solved optimally during the initial descent.</caption><thead><tr><th rowspan="2">POIs</th><th rowspan="2">|R|</th><th colspan="3">Greedy</th><th colspan="5">LS-tempo</th></tr><tr><th>profit</th><th>gap</th><th>r</th><th>profit</th><th>gap</th><th>r</th><th>t</th><th>s</th></tr></thead><tbody><tr><td rowspan="4">antilles</td><td>50</td><td><strong>20090</strong></td><td>&lt;0.01</td><td>167166</td><td><strong>20090</strong></td><td>&lt;0.01</td><td>13186</td><td>3055040</td><td>6%</td></tr><tr><td>100</td><td>36307</td><td>0.02</td><td>82066</td><td><strong>36328</strong></td><td>0.02</td><td>2396</td><td>2296988</td><td>4%</td></tr><tr><td>250</td><td><strong>74129</strong></td><td>0.27</td><td>22835</td><td>74035</td><td>0.27</td><td>255</td><td>2263862</td><td>1%</td></tr><tr><td>500</td><td><strong>88913</strong></td><td>0.56</td><td>10785</td><td>88222</td><td>0.57</td><td>119</td><td>1983807</td><td>0%</td></tr><tr><td rowspan="4">sahara</td><td>50</td><td>17736</td><td>0.01</td><td>242973</td><td><strong>17743</strong></td><td>0.01</td><td>11743</td><td>1785669</td><td>13%</td></tr><tr><td>100</td><td><strong>38575</strong></td><td>0.03</td><td>79356</td><td>38570</td><td>0.03</td><td>1504</td><td>1400336</td><td>4%</td></tr><tr><td>250</td><td>75919</td><td>0.30</td><td>19381</td><td><strong>76020</strong></td><td>0.30</td><td>212</td><td>1898979</td><td>1%</td></tr><tr><td>500</td><td><strong>86522</strong></td><td>0.56</td><td>10690</td><td>85559</td><td>0.57</td><td>85</td><td>1532961</td><td>0%</td></tr><tr><td rowspan="4">fountains</td><td>50</td><td>20282</td><td>0.01</td><td>122542</td><td><strong>20287</strong></td><td>0.01</td><td>10309</td><td>1986404</td><td>7%</td></tr><tr><td>100</td><td>36989</td><td>0.02</td><td>39253</td><td><strong>37014</strong></td><td>0.02</td><td>1806</td><td>1824849</td><td>4%</td></tr><tr><td>250</td><td>97433</td><td>0.09</td><td>8422</td><td><strong>97721</strong></td><td>0.08</td><td>112</td><td>891194</td><td>2%</td></tr><tr><td>500</td><td><strong>142314</strong></td><td>0.36</td><td>3564</td><td>141331</td><td>0.37</td><td>36</td><td>1342948</td><td>0%</td></tr><tr><td rowspan="4">military</td><td>50</td><td><strong>22467*</strong></td><td>0.00</td><td>44987</td><td><strong>22467*</strong></td><td>0.00</td><td>30372</td><td>585242</td><td>19%</td></tr><tr><td>100</td><td>38488</td><td>&lt;0.01</td><td>15250</td><td><strong>38489*</strong></td><td>0.00</td><td>9135</td><td>418030</td><td>29%</td></tr><tr><td>250</td><td>102838</td><td>&lt;0.01</td><td>3742</td><td><strong>102868</strong></td><td>&lt;0.01</td><td>391</td><td>324473</td><td>12%</td></tr><tr><td>500</td><td>211019</td><td>0.01</td><td>1116</td><td><strong>211080</strong></td><td>0.01</td><td>35</td><td>186169</td><td>6%</td></tr><tr><td rowspan="4">world heritage</td><td>50</td><td>18221</td><td>&lt;0.01</td><td>23588</td><td><strong>18222*</strong></td><td>0.00</td><td>19290</td><td>760620</td><td>24%</td></tr><tr><td>100</td><td>36684</td><td>&lt;0.01</td><td>13974</td><td><strong>36691</strong></td><td>&lt;0.01</td><td>4706</td><td>1214798</td><td>13%</td></tr><tr><td>250</td><td>103770</td><td>0.01</td><td>2714</td><td><strong>103860</strong></td><td>0.01</td><td>310</td><td>717050</td><td>6%</td></tr><tr><td>500</td><td>197736</td><td>0.03</td><td>1040</td><td><strong>197782</strong></td><td>0.03</td><td>39</td><td>366371</td><td>3%</td></tr><tr><td colspan="2">Average</td><td colspan="3">0.115</td><td colspan="5">0.115</td><td>7.7%</td></tr></tbody></table>