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

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