A Simple and Fast Heuristic Algorithm for Time-dependent AEOS Scheduling Problem

Agile earth observing satellites(AEOS) scheduling problem has drawn much research attention in the last few years due to its wide range of applications in both military and civilian areas. Recently, a state-of-the-art adaptive large neighborhood search algorithm(ALNS) was proposed for solving this problem where a dichotomy algorithm was used to calculate the time-dependent transition time. ALNS was demonstrated to be very effective in comparison to CPLEX and other heuristic algorithms at the time of publishment. However, we find two major drawbacks of ALNS. First, the imbalance between diversification and intensification leads to premature convergence; Second, the frequent invoke of the dichotomy algorithm leads to tremendous duplicate calculations and thus high computational complexity of ALNS. In this paper, we propose a simple and fast heuristic algorithm (SFHA) which is composed of an intensified local improvement procedure and a diversified perturbation operation. SFHA also includes a preprocessing procedure to precalculate all possible transition times, which avoids duplicate calculation and speeds up search process. Computational results show that the proposed SFHA outperforms ALNS in terms of both solution quality and computational time. In particular, SFHA consistently attains better solutions than ALNS in half of its running time.