第1章 问题的定义、研究背景及意义 1
1.1 时变网络研究的科学依据与理论意义 1
1.2 时变网络中国邮路问题的定义及其应用背景与意义 2
第2章 问题的发展历史和现状分析 4
2.1 中国邮路问题的研究现状和发展趋势 4
2.2 时变网络优化理论的研究现状和发展趋势 9
2.3 问题的提出和本书的主要贡献 12
2.3.1 存在的问题 12
2.3.2 本书的主要贡献 13
2.3.3 本书的组织结构 17
第3章 时变网络中国邮路问题的基本性质和精确算法 18
3.1 问题的提出 18
3.2 TDCPP问题的计算复杂性理论研究 19
3.2.1 非FIFO网络TDCPP是NP困难问题 19
3.2.2 FIFO网络TDCPP是NP困难问题 21
3.2.3 TDCPP问题的近似算法研究 24
3.3 传统算法不适用于时间依赖网络 26
3.3.1 二阶段算法不适用于时间依赖网络 26
3.3.2 传统弧路由转换方法的局限性 28
3.4 FIFO网络TDCPP最优解的性质 30
3.5 FIFO网络TDCPP的分支限界算法 31
3.6 FIFO网络TDCPP问题的动态规划算法 33
3.7 实验结果 35
3.7.1 支配关系D的剪枝效果 35
3.7.2 时间阶段数对算法计算时间无明显影响 37
3.7.3 问题的求解规模 37
3.8 总结与展望 39
第4章 时间依赖网络中国邮路问题的多面体理论 40
4.1 问题的提出 40
4.2 TDCPP的圈变量整数规划模型 41
4.3 圈排列多面体 43
4.3.1 CA多面体中的仿射无关TDCPP邮路 44
4.3.2 CA多面体的维数 45
4.3.3 CA多面体中的极大诱导不等式 45
4.4 TDCPP的时间相关不等式 47
4.4.1 时间相关不等式的线性松弛 47
4.4.2 更有效的时间相关不等式 48
4.5 实验结果 49
4.6 小结 53
第5章 时变网络中国邮路问题的其他几类整数规划模型 55
5.1 问题的提出 55
5.2 转换方法求解TDCPP的一般算例 55
5.2.1 TDCPP一般算例的转换算法 55
5.2.2 转换算法的实例说明及正确性证明 56
5.2.3 改进的圈变量整数规划模型 58
5.3 TDCPP扩展的圈变量整数线性规划模型 59
5.3.1 交错圈变量整数规划模型 60
5.3.2 改进的K值上界 61
5.3.3 算例与正确性验证 62
5.4 TDCPP的弧变量整数线性规划模型 63
5.4.1 模型描述 63
5.4.2 实验结果 66
5.5 小结 67
第6章 时间依赖网络乡村邮路问题的多面体理论 69
6.1 问题的提出 69
6.2 TDRPP的交错弧-路径变量整数规划模型 69
6.3 弧-路径交错序列多面体APAS 72
6.3.1 X中仿射无关的弧序 72
6.3.2 Y（x）中仿射无关的衔接路径 74
6.3.3 F中仿射无关的TDRPP邮路及一些多面体结果 77
6.4 TDRPP的时间约束不等式 78
6.4.1 时间约束不等式的线性化 78
6.4.2 更有效的时间约束不等式 80
6.5 实验结果 80
6.6 小结 84
第7章 时变网络中国邮路问题的时间自动机模型和统一求解框架 85
7.1 问题的提出 85
7.2 时变网络中国邮路问题 86
7.3 基于时间自动机理论的建模方法 87
7.3.1 传统中国邮路问题的时间自动机模型 88
7.3.2 时变网络中国邮路问题的时间自动机系统模型 90
7.4 基于时间自动机系统模型的时变网络CPP问题的求解方法 92
7.5 TAS模型中的时间自动机合并策略 96
7.6 实验结果 99
7.7 结束语 100
参考文献 102