الگوریتم شاخه و قیمت برای تصویربرداری صورت فلکی EOS
Abstract
1- Introduction
2- Literature review
3- Problem description
4- Problem formulation
5- A branch and price algorithm
6- Computational experiments
7- Conclusion and future work
References
Abstract
Earth observation satellite (EOS) constellation imaging and downloading integrated scheduling (EOSCIDIS) is a challenging optimization problem with several engineering applications. Given a large number of imaging requests and a constellation consisting of a group of EOSs, a workable schedule must be developed for each EOS to allow for imaging and downloading in the most efficient manner given a certain scheduling horizon. No studies have proposed exact algorithms for the EOSCIDIS problem, although it has considerable potential for applications. In this paper, we developed a branch and price (B&P) algorithm for the EOSCIDIS problem. First, we decomposed the problem by extracting the sub-structure of the problem, and the decomposition resulted in a master problem and multiple pricing problems. Solving the linear relaxed master problem with column generation (CG) method provides a very tight upper bounds for the primal problem. We then embedded the CG process into a branch and bound (B&B) framework to find optimal integer solutions. In order to accelerate the convergence of the algorithm, we developed a heuristic utilizing the generated columns to construct feasible integer solutions to prune B&P tree branches earlier. We tested the B&P algorithm on highly-simulated instances that are constructed according to the Chinese Gaofen-1 satellite and 3 types of random instances which correspond to short, medium and long term scheduling respectively. Both results show that our method could find high-quality solutions with optimality gap less than 10% for most instances using reasonable computational costs .
Introduction
Earth observation satellites (EOSs) are launched for the primary purpose of collecting surface images from orbit. EOS imagery has recently been used in agriculture, map making, land surveys, and disaster warning and recovery (Madry, 2013). An EOS constellation is an imaging system with a certain geometrical shape, composed of a group of EOSs providing coordinated ground coverage. These systems are beneficial as they reduce revisit time, the duration between repeated observations of the same site. Multiple EOS constellations have been commissioned in recent years, including the French Pléiades (Lemaître et al., 2002) and Italy‘s COSMO-SkyMed (Bianchessi and Righini, 2008). Presently, several countries have committed to enhancing EOS constellation infrastructure, particularly China, which will continue to increase investment in this field. An EOS will first image a series of ground-based sites and then store the acquired image data to on-board memory (i.e., high performance hard disks). These data are then downloaded to ground stations during radio communications, freeing storage resources for subsequent observations. This process requires manual intervention, in which commands are computed according to workable imaging and downloading schedules. EOS constellation imaging and downloading integrated scheduling (EOSCIDIS) is an optimization problem that has become of interest as the number of constellations in operation has increased. Given a large number of imaging requests and limited imaging and downloading resources (EOS constellation), an optimal imaging and downloading schedule would allow for imaging and downloading in the most efficient manner given a certain scheduling horizon. The EOSCIDIS problem is a generalization of the EOS scheduling (EOSS) problem.