Satellite observation scheduling with a novel adaptive simulated annealing algorithm and a dynamic task clustering strategy

•We propose a dynamic task clustering strategy for satellite observation scheduling.•We first present a novel adaptive simulated annealing algorithm with three adaptation mechanisms.•We integrate the dynamic task clustering strategy with the adaptive simulated annealing algorithm effectively.•We conduct extensive experiments to verify the effectiveness of the proposed method.

Efficient scheduling is significant for the effective use of scarce satellite resources. Task clustering has been demonstrated as an effective strategy for improving the efficiency of satellite scheduling. However, current task clustering strategies are static, i.e., they are integrated into the scheduling in a two-phase manner rather than in a dynamic fashion, without expressing their full potential in improving the satellite scheduling performance. In this study, we present an adaptive simulated annealing-based scheduling algorithm integrated with a dynamic task clustering strategy (ASA-DTC) for satellite observation scheduling problems (SOSPs). Firstly, we develop a formal model for the scheduling of Earth observing satellites. Secondly, we analyse the related constraints involved in the observation task clustering process. Thirdly, we detail an implementation of the dynamic task clustering strategy and the adaptive simulated annealing algorithm. The adaptive simulated annealing algorithm is efficient and contains sophisticated mechanisms, i.e., adaptive temperature control, tabu-list-based short-term revisiting avoidance mechanism and intelligent combination of neighbourhood structures. Finally, we report on experimental simulation studies to demonstrate the competitive performance of ASA-DTC. We show that ASA-DTC is particularly effective when SOSPs contain a large number of targets or when these targets are densely distributed in a certain area.