Publication Type

Journal Article

Version

acceptedVersion

Publication Date

8-2020

Abstract

The scheduling of an Agile Earth Observation Satellite (AEOS) consists of selecting and scheduling a subset of possible targets for observation in order to maximize the collected profit related to the images while satisfying its operational constraints. In this problem, a set of candidate targets for observation is given, each with a time-dependent profit and a visible time window. The exact profit of a target depends on the start time of its observation, reaching its maximum at the midpoint of its visible time window. This time dependency stems from the fact that the image quality is determined by the look angle between the satellite and the target to be observed. We present an exact algorithm for the single-orbit scheduling for an AEOS considering the time-dependent profits. The algorithm is called Adaptive-directional Dynamic Programming with Decremental State Space Relaxation (ADP-DSSR). This algorithm is based on the dynamic programming approach for the Orienteering Problem with Time Windows (OPTW). Several algorithmic improvements are proposed to address the time-dependent profits. The proposed algorithm is evaluated based on extensive computational tests. The experimental results show that the algorithmic improvements significantly reduce the required computational time. The comparison between the proposed exact algorithm and a state-of-the-art heuristic illustrates that our algorithm can find the optimal solutions for sufficiently large instances within limited computational time. The results also show that our algorithm is capable of efficiently solving benchmark OPTW instances.

Keywords

Agile satellite scheduling, Time-dependent profits, Dynamic programming, Decremental state space relaxation

Discipline

Theory and Algorithms

Research Areas

Intelligent Systems and Optimization

Publication

Computers and Operations Research

Volume

120

First Page

1

Last Page

15

ISSN

0305-0548

Identifier

10.1016/j.cor.2020.104946

Publisher

Elsevier

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1016/j.cor.2020.104946

Download

Share

COinS