A Neural-Guided Adaptive Large Neighborhood Search Algorithm for the Communication Satellite Range Scheduling Problem

The communication satellite range scheduling problem (CSRSP) is indispensable for the regular operation of the low Earth orbit (LEO) internet constellation. By utilizing a multilayer perceptron (MLP), a neural-guided adaptive large neighborhood search (NGALNS) algorithm is presented for the CSRSP. In this algorithm, six destroy methods and four repair methods are designed to adaptively optimize the solution. To increase the possibility of successful task scheduling, an MLP is trained based on historical data as an executability prediction model to predict the highest executability arc of each task, which is embedded in a fast insertion algorithm to quickly generate a task execution plan in each repair operation. Experimental results show that NGALNS can solve the CSRSP more effectively than three satellite scheduling algorithms.