【假一罚四】时间依赖型敏捷卫星调度模型及方法彭观胜, 邢立宁著

对地观测卫星是获取地球表面遥感图像的一类重要平台，它具有覆盖范围广、信息精度高、不受空域国界限制等优势，在军事侦察、国土资源勘探、环境保护、灾害救助等方面发挥着非常重要的作用。对地观测卫星在我国得到了快速的发展，目前我国已经发射资源系列、环境系列、高分系列等卫星，为经济建设和国防建设提供有力支撑。
敏捷对地观测卫星（以下简称“敏捷卫星”）是具有更强姿态机动能力的新一代对地观测卫星，具有侧摆、俯仰、偏航三个轴向上的姿态机动能力。相比传统的非敏捷卫星，敏捷卫星可前视、后视、正视，即在经过观测目标正上空之前或之后都可拍摄图像，因此，观测目标的可见时间窗口更长，观测任务之间的约束冲突更容易通过姿态调整解决。然而，敏捷性提高了卫星的观测能力，也给卫星调度带来了巨大的挑战。如何合理地进行敏捷卫星调度并制定观测计划，充分发挥这种强大的观测能力，提高对地观测系统的使用效能，成为亟待解决的关键问题。
敏捷卫星任务调度是指在满足卫星运行约束的基础上，对待观测目标制定调度计划，将卫星载荷资源按时间分配给不同观测任务，从而最大化观测目标数量或总收益。相比一般的对地观测卫星调度，敏捷卫星调度具有两种显著的时间依赖特性：时间依赖转换时间和时间依赖收益。前者是指卫星在连续观测两个任务时，其所需的姿态转换时间长短取决于这两个任务的具体观测开始时间；后者是指卫星在可见时间窗口内不同时刻观测目标，其收益是不同的。常规的敏捷卫星调度一般只考虑前一种特性，即假设只要可行约束满足，在窗口内任意时刻任意观测角度拍摄图像得到的收益是一样的。然而在现实应用中，采用过大观测角度拍摄的图像，其图像质量往往不能让人满意。因此，在最佳观测目标调度方案中考虑观测角度的优化，是实现精细化调度的重要一步，同时也会极大地增大解空间和求解难度。
本书主要研究了两种敏捷卫星调度问题：考虑时间依赖转换时间的敏捷卫星调度问题和考虑时间依赖收益的调度问题。前一种问题是常规性质的敏捷卫星调度问题，已经有了一定的研究基础，而后一种问题是在前一种问题的基础上，额外考虑了时间依赖收益特性，属于全新的问题模型。本书最大的特点是对这两种问题模型分别提出了启发式算法和精确算法，启发式算法能高效求解大规模优化问题，有利于工程化实现，但求解质量没有理论保证，而精确算法可以在中等规模的算例上提供最优解来验证启发式算法的求解效果，且具有较高的理论深度，但难以应用于大规模算例上。两种算法发挥各自优势，弥补不足，相辅相成，互相验证。在文献调查中发现，国内对卫星调度问题的建模研究较少，对其与经典组合优化问题的模型相似性和联系缺少深刻的认识。局限于卫星调度这一背景，而忽略优化模型在其他应用领域所具有的普适性，就容易导致求解方法与问题模型的无关性，研究成果难以获得学术界的普遍认可和推广。此外，敏捷卫星理论研究可比较性差，这既有卫星具体能力的不同、数据不公开等原因，也因为缺乏对问题特性的梳理，缺少由浅至深、由基本模型到变种模型的统一的研究框架。
本书将敏捷卫星调度问题与一类经典组合优化——定向问题联系到一起，探讨其相似性与联系，在进行少量模型转换与调整的基础上，借用已有的、成熟的经典问题的算法求解，得到超越以往算法的求解效果。而在此基础上衍生的变种优化模型，针对其问题特性在基础算法上做出适量调整，就能得到效果优异的求解方法。全书共包含6章，第1章为绪论，讨论了敏捷卫星调度问题的研究背景、研究意义，以及两种时间依赖型敏捷卫星调度问题的国内外研究现状；第2章介绍了两种时间依赖型敏捷卫星调度的问题描述和数学模型，验证了时间依赖转换时间的两种规则，从而简化转换时间和快速预处理；第3章介绍了求解两种敏捷卫星调度问题的启发式算法，其基本框架是迭代局部搜索，算法特点在于能应对时间窗口约束、可用于解可行性快速检查的插入算子，针对时间依赖收益特性提出双向动态规划用于任务序列的收益评估，从而指引启发式搜索；第4章提出了求解两种敏捷卫星调度问题的精确算法，算法框架为分支定价算法，引入割平面、原始启发式、拉格朗日松弛等方法提高求解效率，针对时间依赖收益特性设计了累积权重函数和相应的加速策略；第5章展示了上述两种模型四种算法的数值实验结果，既包括与敏捷卫星调度现有算法的对比，也有与经典定向问题最新算法的对比，以及与商业求解器的对比。第6章为结论与展望。
本书由邢立宁制定提纲，由彭观胜撰写主要内容。衷心感谢比利时荷语鲁汶大学Pieter Vansteewegen教授、Reginald Dewil教授，法国EDHEC商学院C\'edric Verbeeck教授，新加坡管理大学Aldy Gunawan教授，国防科技大学刘晓路、王建江、宋国鹏对本书所作研究的直接参与和指导。感谢课题组陈英武教授、贺仁杰教授及其他教师的指导和帮助，感谢参与研究的课题组全体博士和硕士研究生。感谢清华大学出版社的大力支持。
由于作者水平有限，本书许多内容还有待完善和深入研究。不足之处，诚请批评指正。

作者
2021年12月
 

随着光学敏捷卫星的应用和发展，航天侦察需求日益增多，如何利用有限的卫星资源，提高卫星任务规划的效能，已经成为了一个亟待解决的重要问题。本书围绕考虑时间依赖特性的敏捷卫星调度问题展开了深入的研究，内容包括： 第一章进行了背景阐述与文献综述。 第二章建立了敏捷卫星调度问题的数学模型。 第三章提出了基于迭代局部搜索的启发式求解算法。 第四章设计了基于分支定价的精确求解算法。 第五章开展了敏捷卫星调度算法的数值对比实验。 第六章总结了全文。 主要特色和创新点： 1. 建模分析了敏捷卫星调度的时间依赖特性，验证其内在属性。 2. 针对时间依赖转换时间特性，提出了具备快速可行性检验和全局松弛的启发式算法，性能****算法，提出了分支定价割平面精确算法，求解质量有理论保证。 3. 针对时间依赖收益特性，提出了嵌入双向动态规划的启发式算法，能快速准确地评估和优化解的收益，提出了分支定价算法，能精确求解一类特殊的资源约束最短路问题。 读者对象： 从事航天调度业务的技术员，高校与科研院所的研究员。

彭观胜,于2020年获国防科技大学管理科学与工程专业博士学位，于2017-2019年比利时荷语鲁汶大学联合培养，主要研究方向为运筹优化、整数规划、智能优化算法等。以第一作者发表SCI论文5篇，EI论文1篇，成果发表在运筹与管理权威期刊Computers and Operations Research和系统科学领域权威期刊IEEE Transaction on SMC。

本书本书围绕考虑时间依赖特性的敏捷卫星调度问题展开了深入的研究，填补了精确算法的理论空白，提高了智能优化算法的求解效能，具备较高的理论价值和应用价值。