论文部分内容阅读
光学对地观测卫星是从太空获取地球表面图像信息数据的重要平台,具有成像时间长、覆盖范围广、不受地域国界限制等优势,在自然灾害监测、气候监测、军事态势侦察等领域发挥着举足轻重的作用。随着经济发展和科学进步,越来越多的成像任务需求涌现出来。如何利用有限的卫星资源,合理规划任务需求,完成任务调度,最大化成像卫星的使用效能,是一个非常值得研究的课题。作为新一代光学对地观测卫星,敏捷对地观测卫星具有多个自由度的机动能力,从而具备更强的观测能力,但其复杂的约束,巨大的解空间,也为敏捷卫星的任务调度带来了不少挑战。本文着眼于时间依赖转换时间型敏捷卫星调度与时间依赖收益型敏捷卫星调度这两种问题模型。前者是指考虑姿态转换时间的时间依赖特性的调度问题,后者则是在前者模型的基础上,考虑观测目标的收益值随其观测时间变化的情况。针对这两种问题,本文分别提出了高效的启发式算法和精确算法。其中启发式算法设计秉承简单高效原则,求解思路清晰,适合应用于工程实践中,其求解质量相比前人研究的算法有巨大提升。精确算法是敏捷卫星调度领域开创性的工作,设计复杂精细,融合了多种高阶求解技巧,数学上证明了算法的最优性,求解效率突出,具有较高的理论价值。主要工作有:(1)首次对敏捷卫星调度中转换时间的时间依赖特性建模分析,数学上证明其满足先进先出和三角不等式规则,为求解算法的设计开辟了思路。基于上述规则,提出了最小转换时间来替代实际转换时间,对复杂约束降维处理,并提出了最小转换时间的预处理算法,减少了大量重复计算转换时间浪费的计算资源。在规模为100-600的中国区域算例的启发式结果显示,考虑转换时间的时间依赖特性比固定转换时间的收益值要高40%,而采用预处理方法后,计算时间节省了50%。此外,论文对非单调形式的时间依赖收益模型建模描述,首次构建了时间依赖收益型敏捷卫星调度整数规划模型,并采用基于时间索引的决策变量将模型线性化。(2)设计了时间依赖转换时间型敏捷卫星调度的启发式算法。秉承简单高效的原则,算法采用了贪婪随机迭代局部搜索的求解框架,自适应调整启发式搜索的多样性。为降低时间窗约束对解的可行性的影响,基于满足先进先出规则的前提,提出了一种快速可行性检查的插入算子,该算子允许通过前移或推迟的方式改变已调度任务的观测时间,从而使更多的任务插入到序列,并以较低的计算代价保证插入操作的可行性。实验结果表明,该算法的求解质量在规模为100-600的中国区域算例上,比当前最新的单星调度算法提高了50%,在规模为100-1000的中国区域算例上,比最新的多星算法提高了30%。(3)提出了时间依赖收益型敏捷卫星调度的启发式求解算法。该算法是基于双向动态规划的迭代局部搜索算法,将双向动态规划评估嵌入到插入算子,使算子在保证快速可行性检查的情况下,实现插入操作的快速评估,以指引启发式搜索方向。算法主要解决两个方面的子问题:1)给定任务序列,优化每个任务的观测开始时间,从而评估该序列的实际收益;2)插入新任务时,有可能会影响序列中其他任务的观测时间,进而影响整个序列的总收益。此时,需要借助第一个子问题的方法评估插入前后解的实际收益的变化量,用于判断该插入操作的有效性,但有可能占用大量计算资源。对第一个子问题,本研究提出了最优子结构性质,进而采用动态规划的方法在多项式时间内求解序列的最大实际收益。对于第二个问题,将动态规划方法与插入算子巧妙结合,利用双向递推动态规划的方式,实现了插入效果的快速评估。与前置时间评估、后置时间、随机评估、单向动态规划评估等多种评估方法的对比结果显示,双向动态规划不仅能有效指引启发式的搜索,还最大程度地减少了评估所带来的计算代价。(4)开创性地提出了时间依赖转换时间型敏捷卫星多圈调度的精确算法。利用模型约束矩阵的分块对角结构特点,算法采用了分支定价割平面求解框架。该算法框架是在分支定价的基础上,引入有效不等式(割平面)来优化整性间隙,从而加速分支定界的收敛。分支定价是在分支定界搜索的每个结点上,利用列生成算法求解问题的线性松弛模型。首先,基于Dantzig-Wolfe分解模型重构为set packing主问题和定价子问题,发现子问题对应于资源受限的初等最短路问题,可采用基于标号扩展的双向动态规划方法求解。由于初等约束使定价子问题难以求解,本研究提出了两种初等约束松弛技术,降低了问题的复杂度。根据主问题模型特点,提出了新的分支策略,保证了分支搜索的可行性和有效性。为减少列生成的求解时间,本研究推导出问题的拉格朗日上界作为新的算法终止条件。为减少分支搜索树的规模,提出了原始启发式方法构造高质量的初始下界。实验结果表明,所提出的多种算法机制,能有效提高精确求解的效率。对规模为200以下的中国区域算例,精确算法都能在几百秒内得到最优解。在单圈调度问题规模为30-50的算例上,算法的计算效率超越当前最新单圈调度精确算法300-400倍。(5)提出了时间依赖收益型敏捷卫星调度的精确求解算法。由于与前一个问题的模型相似性,算法采用了分支定价的求解框架,但本问题的定价子问题是一种非常特殊的资源受限的初等最短路问题,其路径权重与调度目标的观测开始时间息息相关,而这类问题尚未有人研究。本文在动态规划的基础上,为每个标号(子路径)定义了累积权重函数,而函数中每一时刻对应一个“状态”,即该定价子问题的一个解。随后,研究将标号的扩展函数和占优准则推广至“状态”,使该子问题得以精确求解,但其求解效率较慢,难以满足列生成算法的性能要求。为此,本文定义了“部分占优准则”,通过强化占优准则来提高被剪枝标号的数量,并证明了该准则的可行性。其次,在保证算法最优性的前提下,实现标号间的融合,减少标号的扩展数量。再次,提出了迂回剪枝策略,提前剪枝可被迂回路径占优的标号扩展。最后,由于不同方向的标号扩展会极大地影响算法效率,研究提出了一种启发式规则,来自适应地调整标号扩展的方向。数值实验证明了四种改进方法能大幅度提高定价子问题的求解效率,而基于该子问题求解方法的分支定价算法,能在几百秒内求解大多数200规模以下的中国区域算例。