摘要
The agile earth observing satellite scheduling (AEOSS) problem consists of scheduling a subset of images among a set of candidates that satisfy imperative constraints and maximize a gain function. In this paper, we consider a new AEOSS model which integrates a time-dependent temporal constraint. To solve this problem, we propose a highly efficient branch and bound algorithm whose effective ingredients include a look-ahead constructionmethod (for generating a high quality initial lower bound) and a combined use of three pruning strategies (which help to prune a large portion of the search space). We conducted computational experiments on a set of test data that were generated with information from real-life scenarios. The results showed that the proposed algorithmis efficient enough for engineering application. In particular, it is able to solve instances with 55 targets to optimalitywithin 164 seconds on average. Furthermore, we carried out additional experiments to analyze the contribution of each key algorithm ingredient.
- 出版日期2017
- 单位中国人民解放军国防科学技术大学