学位论文 > 优秀研究生学位论文题录展示

时变网络有向中国邮路问题的割平面算法研究

作　者: 王金香
导　师: 谭国真
学　校: 大连理工大学
专　业: 计算机应用技术
关键词: 时变网络中国邮路问题整数线性规划割平面算法启发式
分类号: F618
类　型: 硕士论文
年　份: 2010年
下　载: 56次
引　用: 2次
阅　读: 论文下载

内容摘要

中国邮路问题是著名的图论问题,也是组合优化、运筹规划领域经典的问题之一在通信系统、交通管理、机器人探测、交互式系统分析、网站可用性和软件测试等领域有着重要的应用。然而,随着通信技术与分布式系统的发展,混合系统测试和智能交通等复杂领域的应用都在关注实际问题中的时间特性,即网络中弧的权值依赖于时间变化而变化,我们称具有这种性质的网络为时变网络。在以往中国邮路问题的研究中,都是假设网络中的权值是静态的、确定的,而实际问题中网络往往是动态的,比如现实交通网络中,交通事故和天气变化等偶然事件都有可能造成道路交通状况的变化,那么邮递员送信沿途所经过街道的旅行时间也会随之变化。中国邮路问题的传统模型和算法只能求解固定弧权条件下的问题,在时变网络中应用传统算法求得的解根本不符合实际情况的要求。因此,研究时变网络中国邮路问题的模型和优化算法具有更为重要的现实意义。然而,引入时间因素后新问题的求解变得非常困难,时变网络有向中国邮路问题已被证明是NP难的,直接求解最优解往往是不实际的。本文从数学规划优化方法的角度出发研究时变网络有向中国邮路问题,首先借鉴时变网络旅行商问题的建模思想结合圈覆盖相关理论建立了时变网络有向中国邮路问题的一个整数规划模型。并根据时间依赖旅行时间函数的阶梯特性,对模型进行了线性化,而且通过分析模型的上界优化了模型。然后基于整数线性规划模型,本文提出了一个启发式割平面求解算法。此外,根据旅行时间的特性,本文还提出了两类强有效不等式并作为割平面约束条件添加到了算法的迭代过程中。文章最后结合一些测试实例对模型和算法进行了测试和分析。本文所提的割平面启发式算法,是在割平面精确算法的框架中添加了一些新的启发式规则,实验结果表明,该算法虽然不是最优化算法,但对于小于15条弧的小规模问题算法能求出67%实例的最优解,对中等规模问题求得的解的上下界的差值平均不超过20%,其中,两类强有效不等式将问题解的质量提高了28%左右。启发式割平面算法快速和求解质量高的特点,扩展了数学规划优化算法和启发式算法的应用领域。此外,本文提出的新模型,对时变网络的其他弧路由问题有着很好的借鉴意义。

全文目录

摘要  4-5
Abstract  5-9
1 绪论  9-18
  1.1 研究背景和意义  9-10
  1.2 国内外研究现状  10-16
    1.2.1 中国邮路问题及其变体的研究现状  11-14
    1.2.2 受时间窗约束的中国邮路问题研究现状  14-15
    1.2.3 时变网络中国邮路问题的研究现状  15-16
  1.3 本文的主要工作  16-17
  1.4 本文的组织结构  17-18
2 路由问题相关算法  18-27
  2.1 静态网络中国邮路问题算法  18-20
    2.1.1 精确优化算法  18-19
    2.1.2 算法在时变网络中的适用性  19-20
  2.2 时变网络中国邮路问题算法  20-25
    2.2.1 图论优化方法  20-22
    2.2.2 数学规划方法  22-24
    2.2.3 启发式求解法  24-25
  2.3 时变网络旅行商问题算法  25-26
    2.3.1 数学规划方法  25
    2.3.2 算法的适用性  25-26
  2.4 本章小结  26-27
3 时变网络有向中国邮路问题(TDDCPP)  27-40
  3.1 TDDCPP问题描述  27
  3.2 TDDCPP整数线性规划模型  27-36
    3.2.1 建模理论  27-31
    3.2.2 符号说明  31-32
    3.2.3 整数非线性模型  32-33
    3.2.4 整数线性模型  33-35
    3.2.5 模型举例  35-36
  3.3 TDDCPP模型分析  36-39
    3.3.1 模型上界分析  36-38
    3.3.2 与静态网络CPP模型相比  38-39
    3.3.3 与以往时变网络CPP模型相比  39
  3.4 本章小结  39-40
4 TDDCPP的割平面算法  40-49
  4.1 启发式割平面算法的提出  40-41
  4.2 TDDCPP模型预处理  41-43
  4.3 基于TDDCPP模型的启发式割平面算法  43-48
    4.3.1 算法设计  43-45
    4.3.2 上界启发式  45-46
    4.3.3 关键部分实现  46-47
    4.3.4 算法分析  47-48
  4.4 本章小结  48-49
5 实验结果  49-54
  5.1 实验平台  49
  5.2 测试实例  49-50
  5.3 计算结果及分析  50-53
  5.4 本章小结  53-54
结论  54-55
参考文献  55-59
攻读硕士学位期间发表学术论文情况  59-60
致谢  60-62

时变网络有向中国邮路问题的割平面算法研究

内容摘要

全文目录

相似论文