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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Earth Observation Satellite Scheduling With Interval-Varying Profits


    Contributors:
    Li, Jiaojiao (author) / Zhu, Jianghan (author) / Xu, Dongyang (author) / Wang, Jianjiang (author) / Li, Zhimeng (author) / Zhang, Kunlun (author)


    Publication date :

    2024-12-01


    Size :

    2787865 byte




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    Agile Earth Observation Satellite Scheduling With a Quantum Annealer

    Stollenwerk, Tobias / Michaud, Vincent / Lobe, Elisabeth et al. | IEEE | 2021




    Developing the Reconfigurable Earth Observation Satellite Scheduling Problem

    Pearl, Brycen D. / Miller, Joseph M. / Lee, Hang Woon | AIAA | 2025