A Heuristic Construction Neural Network Method for the Time-Dependent Agile Earth Observation Satellite Scheduling Problem
Jiawei Chen, Ming Chen, Jun Wen, Lei He, Xiaolu Liu
Abstract
The agile earth observation satellite scheduling problem (AEOSSP), as a time-dependent and arduous combinatorial optimization problem, has been intensively studied in the past decades. Many studies have proposed non-iterative heuristic construction algorithms and iterative meta-heuristic algorithms to solve this problem. However, the heuristic construction algorithms spend a relatively shorter time at the expense of solution quality, while the iterative meta-heuristic algorithms accomplish a high-quality solution with a lot of time. To overcome the shortcomings of these approaches and efficiently utilize the historical scheduling information and task characteristics, this paper introduces a new neural network model based on the deep reinforcement learning and heuristic algorithm (DRL-HA) to the AEOSSP and proposes an innovative non-iterative heuristic algorithm. The DRL-HA is composed of a heuristic construction neural network (HCNN) model and a task arrangement algorithm (TAA), where the HCNN aims to generate the task planning sequence and the TAA generates the final feasible scheduling order of tasks. In this study, the DRL-HA is examined with other heuristic algorithms by a series of experiments. The results demonstrate that the DRL-HA outperforms competitors and HCNN possesses outstanding generalization ability for different scenario sizes and task distributions. Furthermore, HCNN, when used for generating initial solutions of meta-heuristic algorithms, can achieve improved profits and accelerate interactions. Therefore, the DRL-HA algorithm is verified to be an effective method for solving AEOSSP. In this way, the high-profit and high-timeliness of agile satellite scheduling can be guaranteed, and the solution of AEOSSP is further explored and improved.