时间依赖型敏捷卫星调度模型及方法：航天资源规划与调度

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

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

目 录

第 1 章 绪论 1
1.1 研究背景与意义 1
1.2 研究现状 4
1.2.1 敏捷卫星调度问题 4
1.2.2 分支定价算法 8
1.3 本书研究内容 11
1.4 本书主要框架 13
第 2 章 时间依赖型敏捷卫星调度问题 16
2.1 时间依赖转换时间型调度问题描述与建模 16
2.1.1 问题描述 16
2.1.2 问题建模 18
2.1.3 时间依赖转换时间建模 20
2.1.4 最小转换时间预处理算法 24
2.2 时间依赖收益型调度问题描述与建模 27
2.2.1 问题描述 27
2.2.2 问题建模 28
2.3 本章小结 31
第 3 章 基于迭代局部搜索的启发式算法 33
3.1 求解时间依赖转换时间型调度问题 33
3.1.1 算法基本框架 33
3.1.2 插入算子 36
3.1.3 扰动算子 40
3.2 求解时间依赖收益型调度问题 41
3.2.1 求解思路与算法框架 41
3.2.2 双向动态规划评估 42
3.3 本章小结 48
第 4 章 基于分支定价的精确算法 49
4.1 求解时间依赖转换时间型调度问题 49
4.1.1 基于 Danzig-Wolfe 分解的数学模型 50
4.1.2 定价子问题的求解 52
4.1.3 主问题求解 66
4.1.4 割平面设计 72
4.1.5 分支定价割平面算法框架 76
4.2 求解时间依赖收益型调度问题 78
4.2.1 基于 Dantzig-Wolfe 分解的数学模型 78
4.2.2 定价子问题基本求解算法 79
4.2.3 定价子问题算法改进 82
4.2.4 定价子问题算法框架 90
4.2.5 分支定价算法框架 91
4.3 本章小结 91
第 5 章 实验结果及分析 93
5.1 算例介绍 93
5.2 时间依赖转换时间型调度问题结果 94
5.2.1 评估启发式算法 95
5.2.2 评估精确算法 99
5.2.3 启发式与精确算法的比较 105
5.2.4 TOPTW 标准算例结果 106
5.3 时间依赖收益型调度问题结果 110
5.3.1 评估启发式算法 110
5.3.2 评估精确算法 113
5.3.3 启发式与精确算法的比较 116
5.4 本章小结 119
第 6 章 结论与展望 121
6.1 本书工作总结 121
6.2 进一步的研究 124
参考文献 126
附录 A 缩写词列表 132