Abstract: Earth Observation Satellites (EOS) usually refer to a type of satellite platform equipped with optical remote sensors to obtain optical images of the earth’s surface to respond to the needs of different users. EOS are widely used in fields such as weather forecasting, disaster monitoring, natural resource exploration, and military reconnaissance due to their advantages such as wide coverage, long observation duration, and having no airspace and national boundaries. How to make effective use of limited satellite resources and improve the efficiency of reconnaissance satellite task scheduling has become a key problem to be solved urgently. The scheduling problem of EOS is given a set of observation targets with different benefits, and under the condition of satisfying a series of satellite operation and resource constraints, to select and rank a part of the observation targets, formulate a reasonable observation scheduling plan, and achieve the maximum observation benefit change. Due to the influence of look angles on the image quality, the time-dependent profits should be considered in the problem, which undoubtedly increases its difficulty. According to different attitude maneuvering capabilities and working mechanisms, EOS can be divided into two types: traditional Non-agile EOS and Agile EOS (AEOS). AEOS have maneuverability in three axes of roll, pitch and yaw. Among them, the yaw angle refers to the angle between the rotation of the satellite around the normal vector of the ground plane and the running track. Pitching maneuverability enables the satellite to conduct observation activities before or after passing directly above the target, that is, the target is visible to the satellite within a period of time with the time passing through the nadir point as the midpoint, and this period of time is called visible time window. The yaw maneuvering capability does not need the satellite to take images along the direction of the running track. Therefore, the task scheduling of non-sensitive satellites only needs to consider which targets are selected for observation, while the task scheduling of agile satellites also needs to determine the observation time of the targets within the visible time window. Obviously, the flexible attitude maneuvering ability can greatly improve the working efficiency of agile satellites, but at the same time, the increase in solution space and difficulty also poses huge challenges to the design of satellite task scheduling algorithms. Moreover, time-dependent characteristic increases the difficulty. This characteristic originates from the application scenario of satellite image acquisition: generally speaking, images taken from different observation angles ( different observation times) will result in different image quality. For example, at the nadir point, the straight-line distance between the satellite and the observation target is the shortest, and the image distortion caused by the observation angle is small when shooting images, so the quality of the captured image is the best; on the contrary, at the position away from the nadir point, the distance is the farthest, and the larger the viewing angle, the worse the image quality.
   Based on these problem characteristics, we build an integer programming model. To efficiently solve this model, we propose a branch-and-price exact algorithm and an efficient primal heuristic with the guarantee of the solution quality. The proposed exact algorithm is the first to solve the multi-orbit agile satellite scheduling to optimality. The original formulation is decomposed into a master problem and several identical pricing problems. Each pricing problem is equivalent to a single-orbit scheduling problem, which corresponds to a well-known resource constrained elementary shortest path problem. The pricing problem is solved by a bidirectional dynamic programming algorithm with Decremental Space State Relaxation technique. The basic idea is to firstly assign a forward label to the virtual initial node and a backward label to the virtual end node, and gradually extend the label to the rest of the reachable nodes from the forward and backward directions through the defined expansion function. A new label is generated on the new node, and according to the extended termination condition, the forward label and backward label are spliced together to form a complete path, and the path with the largest weight is taken as the optimal solution to the pricing sub-problem. The primal heuristic algorithm provides high-quality initial solutions for branch and price algorithm, and the optimality gap of the heuristic solutions can be given. The idea of the primal heuristic is to use the column generation algorithm to solve the master problem on the root node, according to the information of the fractional solution, fix the single-orbit scheduling scheme with value equals to 1, and continue to solve the master problem with the remaining orbits with value less than 1, until the schemes during all orbits are determined.
   We generate a large number of benchmark instances and conduct experiments in this research. The observation target in the calculation example is uniformly and randomly generated from a rectangular area according to the latitude and longitude. The range of the rectangular area is latitude 3°N-53°N and longitude 74°E-133°E. The results show that the branch and price algorithm can find the optimal integer feasible solution in most cases with only a few dozen steps of branch search. It can solve the 150-target instances with no more than 500 seconds on average. With an increase in the scale of the calculation example, the integrity gap of the calculation instance becomes larger, and the number of branch nodes increases. The branch pricing algorithm needs to spend more computing time getting the optimal solution. Furthermore, the proposed primal heuristic outperforms the state-of-the-art heuristic in terms of solution quality. For the 150-target instances, its optimality gap is no more than 0.3% on average.

Key words: satellite scheduling, branch-and-price, column generation, primal heuristic, time-dependent profits

摘要： 随着地球影像需求的日益增长,敏捷对地观测卫星的任务调度问题已经成为了一个亟待解决的技术难题。由于观测角度对成像质量的影响,敏捷卫星调度问题需要考虑到一个重要的问题特性——时间依赖收益特性,即不同角度观测同一目标的收益不同,这无疑增加了调度的复杂性。根据问题模型特点,本文提出了一种基于分支定价的精确求解算法和一种高效且求解质量有理论保证的启发式算法。该精确算法是首个求解敏捷卫星多圈调度问题的精确算法,求解效果突出,对规模为150的算例能在平均500秒内得到最优解,性能远超商业求解器。所提出的启发式算法在求解质量上超越了文献中最先进的启发式算法,对规模为150的算例最优间隙平均不超过0.3%。

关键词: 卫星调度, 分支定价, 列生成, 原始启发式, 时间依赖收益