EOS (Earth Observing Satellite) imaging scheduling is characterized by multiple complex constraints, including slewing, storage capacity and power. Generating the sequence of imaging requests is a complex combinatorial optimization problem which has been proved to be strong NP-hard. Most of the proposed methods to solve this problem make different simplifications to some extent. This paper deals with the imaging scheduling problem of an optical earth observing satellite, that considers all the above mentioned constraints.Firstly,for the small number imaging targets,we build the directed acyclic graph model with weight on both vertexes and edges, propose a satellite imaging scheduling algorithm with complex constraints (SISACC) based on label-setting shortest path, which adopts hiberarchical dominating and the divide-and-conquer idea. Then, we make some improvements to the SISACC. Moreover, we analyze some characteristics of the SISACC and the improved algorithm. Finally, we do a great deal of experiments to analyze the applicability of the proposed algorithms and prove their feasibility. The proposed approach has been successfully used in an on-line satellite system for daily imaging scheduling.%对地观测卫星成像调度需要考虑卫星动作时间切换、存储容量、星上能量等复杂约束,确定要观测的观测目标序列,是一个具有强NP-Hard特性的组合优化问题,一般研究者都对问题约束进行了不同程度的简化.针对一类可见光对地观测卫星小问题规模下的应用,考虑上述多种约束,建立顶点和边都带权的无环路有向图模型,并基于标记更新最短路径算法,采用分层支配和分治思想,提出了复杂约束成像卫星调度算法(SISACC)进行完全路径搜索,得到问题精确解;在此基础上,给出了算法改进措施,分析了完全算法和改进方法的性质;最后通过大量实验验证了算法的适用条件和可行性.该方法已成功应用于某在轨卫星的日常成像调度任务中.
展开▼
