目   录

第 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