面向多星协同观测的区域覆盖优化方法

论文摘要

在成像卫星的工程应用中,常常遇到这样的场景,在指定的时间内,需要使用多颗成像卫星协同对单个较大的区域目标进行成像观测。制定该场景下卫星合理的覆盖计划即为本文研究的面向多星协同观测的区域覆盖优化问题。给定一个待观测的大区域,和若干成像卫星,每颗卫星每次只能覆盖一个矩形条带区域（小于待观测区域）。由于卫星所携带的相机可以侧摆,不同侧摆角度下覆盖的条带区域的位置不同;卫星相机具有固定的视场角,不同侧摆角度下覆盖的条带区域的宽度不同;卫星相机的开关机时间不同,覆盖的条带区域的位置和长度也不相同。因此,不同的卫星观测动作,会覆盖不同位置、不同长度、不同宽度的条带区域。覆盖优化要求:合理地安排每个卫星每次过境机会内的观测动作,使得总体的覆盖方案对应某一个给定的目标尽可能的优。该问题是一个与计算几何高度耦合的连续空间组合优化问题,其求解具有一定的挑战性。本文对该问题进行了深入研究,提出了一系列技术方法,所取得的主要创新点如下:（1）提出了三种面向多星协同观测的区域覆盖优化问题,即覆盖资源有限情形下最大覆盖面积、覆盖资源充足情形下最小完工时间、覆盖资源充足情形下最小化覆盖成本问题,分析了各个问题的特征,并基于网格离散化技术建立了相应的整数线性规划模型。（2）针对最大覆盖面积问题,设计了多项式时间复杂度的启发式算法,并使用拉格朗日松弛技术计算对应的上界,仿真实验结果表明,在小规模情况下,该启发式算法能够求得近似最优解（最优性GAP<1%）;针对最小完工时间问题,提出了多项式时间的两阶段启发式算法,仿真实验表明,该两阶段启发式算法能够以较少的计算花费求得高质量的解;针对最小覆盖成本问题,设计了基于隐枚举算法求解子问题的branch and price算法（IE-BP）,提出并证明了可以削剪价格子问题解空间的支配原则,使得大量的列可以预先排除,大大加速了求解的速度,仿真实验表明,所提出的支配原则可以削减约68%的列,部分算例能够求得近似最优解,且计算效率优于美国著名商业优化软件Gurobi。（3）提出基于嵌套网格的逼近策略。先使用启发式、两阶段启发式、IE-BP算法在单元格尺寸较大的网格上进行求解,在求得解方案以后,进一步地,在现有网格内构造一个单元格尺寸更小的嵌套网格,并且在已有的解方案（即覆盖方案）“周围”再次进行搜索寻优,进行精度更细的求解。由于二次搜索是在一次求解的基础上进行,仅需消耗少量的计算量。重复使用这样的逼近策略可以不断提高离散化的精细程度,求得高质量的解方案。仿真实验表明,该方法稳定高效。（4）针对大规模问题,基于“分而治之”的总体思路,提出一种基于分区的求解策略:即将大区域分割成较小的分区,将覆盖资源分配给各个分区,并在各个分区内求解覆盖方案,各分区覆盖方案合并起来形成总体覆盖方案。不同的资源分配方案对应不同的分区覆盖方案,从而导致不同的总体覆盖方案。为获取高质量的总体覆盖方案,采用模拟退火亚启发式算法,对覆盖机会分配方案进行搜索,实现覆盖机会的动态分配。仿真实验表明,直接求解需要消耗极大的计算资源,甚至无法直接求解,而基于分区的求解策略能够在可接受的时间内求得高质量的解。

论文目录

• 致谢
• 摘要
• abstract
• 第一章 绪论
•   1.1 研究背景与研究意义
•     1.1.1 研究背景
•     1.1.2 研究意义
•   1.2 研究内容与技术框架
•     1.2.1 研究内容
•     1.2.3 技术框架
•   1.3 国内外研究现状
•     1.3.1 卫星任务规划问题
•     1.3.2 多边形几何覆盖问题
•     1.3.3 设施选址覆盖问题
•     1.3.4 二维装箱问题
•     1.3.5 研究现状综合分析
•   1.4 文章结构
• 第二章 相关的基础理论与方法
•   2.1 拉格朗日松弛技术
•     2.1.1 拉格朗日松弛问题
•     2.1.2 拉格朗日对偶问题
•   2.2 割平面算法
•     2.2.1 GF不等式
•     2.2.2 MIR不等式
•     2.2.3 GMI不等式
•   2.3 Branch and price算法
•     2.3.1 分支定界算法
•     2.3.2 列生成算法
•   2.4 本章小结
• 第三章 面向多星协同观测的最大覆盖面积问题
•   3.1 引言
•   3.2 问题描述与建模
•   3.3 最长基本覆盖模式生成算法
•   3.4 启发式求解算法
•   3.5 拉格朗日松弛上界
•   3.6 基于嵌套网格的逼近策略
•   3.7 基于分区的求解策略
•   3.8 仿真实验
•     3.8.1 启发式算法求解效率验证
•     3.8.2 逼近策略求解效率验证
•     3.8.3 分区策略求解效率验证
•   3.9 本章小结
• 第四章 面向多星协同观测的最小完工时间问题
•   4.1 引言
•   4.2 问题描述与建模
•   4.3 两阶段启发式求解算法
•   4.4 基于嵌套网格的逼近策略
•   4.5 基于分区的求解策略
•   4.6 仿真实验
•     4.6.1 两阶段启发式算法求解效率验证
•     4.6.2 逼近策略求解效率验证
•     4.6.3 分区策略求解效率验证
•   4.7 本章小结
• 第五章 面向多星协同观测的最小覆盖成本问题
•   5.1 引言
•   5.2 问题描述与建模
•   5.3 Branch and price求解算法
•     5.3.1 列生成求解线性松弛问题
•     5.3.2 分支定界策略
•   5.4 逼近策略与分区策略
•   5.5 仿真实验
•     5.5.1 IE-BP算法求解效率验证
•     5.5.2 逼近策略求解效率验证
•     5.5.3 分区策略求解效率验证
•   5.6 本章小结
• 第六章 总结与展望
• 参考文献
• 攻读博士学位期间的学术活动及成果情况

文章来源

类型: 博士论文

作者: 朱外明

导师: 胡笑旋

关键词: 地球观测卫星,多星协同观测,拉格朗日松弛,割平面算法,列生成,嵌套网格逼近策略,基于分区的策略

来源: 合肥工业大学

年度: 2019

分类: 基础科学

专业: 自然地理学和测绘学

单位: 合肥工业大学

分类号: P228

DOI: 10.27101/d.cnki.ghfgu.2019.000476

总页数: 118

文件大小: 3699K

下载量: 162