Earth Observation Satellite Scheduling With Interval-Varying Profits

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.