时变网络中国邮路问题研究

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

随着信息技术的发展，不同学科领域对网络中的时间约束和时变特性日益关注，于是能够充分反映时间特性的时变网络优化应运而生。时变网络优化突破了传统理论的局限性，产生了许多挑战性问题。这些问题有些已经得到解决，有些虽然在应用中已经遇到，但是尚未解决。《时变网络中国邮路问题研究》正是针对这些尚未解决的网络优化问题开展研究：首先系统地提出了时变网络中国邮路问题，并研究其计算复杂性、性质、模型、精确和启发式解法，进一步发展和丰富了时变网络优化的理论体系；然后针对实时系统测试中一个热点问题开展应用研究，为解决实时系统测试序列生成和优化这一重要问题提供了新的技术途径和新的方法。《时变网络中国邮路问题研究》研究的问题是计算机科学、运筹学、通信工程等综合交叉学科研究热点，不同学科的相互交叉、相互渗透、相互促进，极有可能产生新的理论和新的方法。时间依赖网络中国邮路问题是时变网络优化领域的重要组成部分，具有重要的理论意义和应用价值。