The Agile Earth Observation Satellite (AEOS) is a new generation system equipped with imaging instruments who can rotate to observe targets. In this study, we focus on a single orbit scheduling of an AEOS, that is to schedule a subset of observation tasks during a given orbit to maximize profits, subject to operational constraints. This problem shares some similarities with the Orienteering Problem with Time Windows (OPTW) where the collected profit is determined by the selection of tasks, and each task is constrained by a time window.

 Some crucial new characteristics are taken into account. Firstly, for each pair of two consecutive tasks, a transition time is required to maneuver the look angle of the imaging instrument. Since different observation start times have different look angles, the transition time depends on the observation start times. Secondly, the quality of an image, i.e. the profit of an observation, also depends on the observation start time.

We develop an exact algorithm for this problem, based on a label setting algorithm and decremental state space relaxation (DSSR). For each label, we define an accumulated profit function. An improved calculation of the transition times is incorporated into the extension of the labels. Furthermore, we propose a new strategy of inserting critical vertices, based on the current optimal path at each iteration.

Unfortunately, no algorithm to compare with is published for the problem. Nevertheless, results show that our algorithm can solve the instances with 100 vertices to optimality in only 15 seconds on average.