Solving the Agile Earth Observation Satellite Scheduling Problem With Time-Dependent Transition Times

The scheduling of agile Earth observation satellites is to select a subset of candidate targets each associated with a profit during their visible time windows in order to maximize the collected profits, under some operational constraints. For each pair of two consecutive observations, a transition time is required to perform a rotating movement of the camera, depending on the start times of the two observations. This time-dependency significantly increases the complexity of the scheduling problem. To solve this problem efficiently, we model the time-dependent transition time and prove that it satisfies the first-in–first-out rule and the triangle inequalities rule. On this basis, we develop a novel hybrid heuristic, called “greedy randomized iterated local search” (GRILS). A specific insert operator, including a fast feasibility check and an assignment procedure are specifically designed to address the operational constraints of the scheduling. Extensive experiments on the single satellite instances and multisatellite instances demonstrate that our algorithm outperforms the state-of-the-art algorithms with respect to solution quality and computation time.