Simulated Annealing-Based Heuristic for Multiple Agile Satellites Scheduling Under Cloud Coverage Uncertainty

Abstract

Agile satellites are the new generation of Earth observation satellites (EOSs) with stronger attitude maneuvering capability. Since optical remote sensing instruments cannot see through the cloud, the cloud coverage brings a significant influence on the satellite observation missions. The scheduling of multiple agile EOSs (AEOSs) is already complicated due to strong satellite maneuverability and onboard satellite energy constraints. Moreover, introducing cloud coverage uncertainty further increases scheduling complexity. Motivated by these challenges, we address the multiple AEOSs scheduling problem under cloud coverage uncertainty where the objective aims to maximize the entire observation profit. A chance constraint programming model is adopted to describe the uncertainty initially, and the observation profit under cloud coverage uncertainty is then calculated via a sample approximation method. To overcome the solving difficulty, an improved simulated annealing (ISA)-based heuristic including a fast insertion strategy is proposed for large-scale observation missions. Finally, extensive experiments are conducted to verify the effectiveness and efficiency of the proposed method. Experimental results show that the ISA-based heuristic outperforms other algorithms for the multiple AEOSs scheduling problem under cloud coverage uncertainty, which validates the proposed algorithm.