We address the multi-satellite scheduling problem with limited observation capacities that arises from the need to observe a set of targets on the Earth's surface using imaging resources installed on a set of satellites. We define and analyze the conflict indicators of all available visible time windows of missions, as well as the feasible time intervals of resources. The problem is then formulated as a mixed integer linear programming model, in which constraints are derived from a careful analysis of the interdependency between feasible time intervals that are eligible for observations. We apply the proposed model to several different problem instances that reflect real-world situations. The computational results verify that our approach is effective for obtaining optimum solutions or solutions with a very good quality.
Given the complexity of the issue, a large portion of previous works is concerned with single satellite scheduling and address the efficient performance by providing an optimal solution and an upper bound. A common set of benchmark instances (S5-DPSP) of the satellite SPOT5 scheduling problem is proposed by @cite_15 . Based on this data, a weighted acyclic digraph model is formulated by @cite_14 , and solved with a label-setting shortest path algorithm. Alternatively, formulations as generalized knapsack problems can be solved with a tabu search algorithm or a genetic algorithm . Two 0-1 linear programming models are considered by @cite_7 . Based on the valid inequalities that arise from node packing and the 3-regular independence system polyhedra, a strengthened formulation for the SPOT5 daily photograph scheduling is presented by @cite_12 . However, the benchmark instances are provided without consideration of the constraints that are imposed by a limited observation time of the target.
@cite_15 @cite_14 @cite_12 @cite_7
1786712251 2050724929 2058114259 1975845493
The daily management of an earth observation satellite is a challenging combinatorial optimization problem. This problem can be roughly stated as follows: given (1) a set of candidate images for the next day, each one associated with a weight reflecting its importance, (2) a set of imperative constraints expressing physical limitations (no overlapping images, sufficient transition times, bounded instantaneous data flow and recording capacity), select a subset of candidates which meets all the constraints and maximizes the sum of the weights of the selected candidates. It can be easily cast in variants of the CSP, ILP or SAT frameworks. As a benchmark, we propose to the CONSTRAINTS community a set of instances, which have been produced from a simulator of the order book of the future satellite SPOT5. The fact that only some of them have been optimally solved should make them very attractive. We consider a satellite following orbits around the earth in order to take shots corresponding to images requested by various customers. The daily operations of such a satellite consist of defining a feasible and satisfactory shot sequence. This problem involves both combinatorial and multiple criteria difficulties. Indeed, the number of feasible shot sequences grows significantly with the number of images asked for, and the evaluation of a shot sequence is based on several conflicting criteria. We propose to formulate this problem as the selection of a multiple criteria path in a graph without circuit. Our approach for solving this problem involves two stages: generation of efficient paths and selection of a satisfactory path using a multiple criteria interactive procedure. Earth observation satellites, such as the SPOT 5, take photographs of the earth according to consumers' demands. Obtaining a good schedule for the photographs is a combinatorial optimization problem known in the literature as the daily photograph scheduling problem (DPSP). The DPSP consists of selecting a subset of photographs, from a set of candidates, to different cameras, maximizing a profit function and satisfying a large number of constraints. Commercial solvers, with standard integer programming formulations, are not able to solve some DPSP real instances available in the literature. In this paper we present a strengthened formulation for the DPSP, based on valid inequalities arising in node packing and 3-regular independence system polyhedra. This formulation was able, with a commercial solver, to solve to optimality all those instances in a short computation time. In this paper, we compare several 0-1 linear programs for solving the satellite mission planning problem. We prove that one of them presents a smaller integrality gap. Our explanation is based on stable set polytope formulations for perfect graphs.