Expectation and SAA Models and Algorithms for Scheduling of Multiple Earth Observation Satellites Under the Impact of Clouds

In the explosively increased number of applications of earth observation satellites (EOSs), scheduling is a significative issue to satisfy more requests and obtain a high observation efficiency. This article investigates the scheduling of multiple EOSs under the impact of clouds. First, we formulate the presences of clouds as stochastic events, and propose an expectation model. Afterwards, for the first time, a branch-and-price algorithm based on Dantzig-Wolfe decomposition is devised to solve the model optimally and efficiently. In order to obtain initial columns for column generation, a dynamic programming algorithm and a heuristic algorithm are suggested, respectively. Furthermore, we discuss the impact of clouds in the case of joint probabilities, and establish a sample average approximation (SAA) model accordingly. With respect to the expectation model, numerical experiment results demonstrate the relative dominance of the proposed branch-and-price algorithm in terms of solution time compared to CPLEX. In addition, the solution of the proposed SAA model is proven to be more robust than that of the expectation model.

I. Introduction

Earth observation satellites (EOSs) are the platforms equipped with sensors that orbit the Earth to take photographs of special areas at the request of users [5], [13]. EOSs can take images, while moving along their orbits, which is shown in Fig. 1. After capturing the photographs, the acquired data will be stored in the on-board memory and transferred to a ground station when the satellites are in the feasible transferring range. Most EOSs operate at low altitudes with the orbital periods being dozens of minutes or several hours. However, it takes several days for a single EOS to view the whole area of the Earth. Hence, multisatellite collaboration has been applied extensively in order to accelerate the response to users.