Earth Observation Satellite Scheduling With Interval-Varying Profits
Jiaojiao Li, Jianghan Zhu, Dongyang Xu, Jianjiang Wang, Zhimeng Li, Kunlun Zhang
Abstract
This study investigates an Earth observation satellite scheduling problem for monitoring key targets’ dynamics, where each target requires two observations within a reasonable time interval. The observation profit and observation effect depend on the interval between the two observations. To define the relationship between observation profits and intervals, a new profit function is introduced. Subsequently, a mixed-integer linear programming model is formulated. Furthermore, in order to efficiently address the problem, an exact branch-and-price algorithm is proposed. To improve solution efficiency, a neighborhood search algorithm is utilized to provide initial feasible solutions. In addition, the pricing problem is solved using a bidirectional label-setting algorithm, employing dynamic ng-path relaxation. To obtain integer solutions quickly, diving heuristic and matheuristic branching strategies are presented. More specifically, the diving heuristic strategy is used to obtain a lower bound at each column generation iteration. Computational results demonstrate that the proposed branch-and-price algorithm is superior to the conventional branch-and-cut algorithm used in CPLEX software package. Furthermore, when integrating the diving heuristic and matheuristic branching strategies, computational time is drastically reduced by an average of 98.7% compared to the exact branch-and-price algorithm. The practical applicability of the proposed algorithms is further validated and assessed through a real-world case study.