时间依赖中国邮路问题的智能算法研究

论文摘要

中国邮路问题是管梅谷教授在1960年第一次提出来的。它描述了一个极具现实意义的问题:一个邮递员负责一个地区的信件投递,每天从邮局出发,走遍该地区的所有街道再返回邮局,问应该怎样安排送信路线可以使所走的路程最短。该问题得到了深入研究并产生了许多新的分类。近年来,人们日益关注网络中的时变特性,研究时间依赖网络中的问题更具有现实意义。时间依赖最短路径问题、时间依赖旅行商问题和时间依赖车路由问题都得到了深入的研究,旅行商问题和车路由问题都是点路由问题,而作为重要的边路由问题——中国邮路问题与时间依赖网络的结合在国际上还没有相关研究。传统的静态中国邮路算法无法求解时间依赖中国邮路问题,本文提出时间依赖网络中国邮路问题的模型,并借鉴时间依赖网络车路由问题算法思想给出适合于时间依赖网络中国邮路问题的高效求解算法。本文的研究丰富了时间依赖网络的理论。本文首先总结了中国邮路问题各个分支的研究成果,并详细介绍了时间依赖网络车路由问题的研究成果;然后详细介绍了传统中国邮路问题及算法;之后介绍了时间依赖网络的基本概念和性质,通过研究时间依赖中国邮路问题的性质,对时间依赖网络和静态网络中的中国邮路问题进行了比较;之后,证明了时间依赖中国邮路问题是NP-hard问题;最后,给出了求解大规模时间依赖中国邮路问题的二层SA/GA算法,对随机产生的实例进行了测试,并根据问题下界对算法结果进行了分析。实验结果表明,此算法在解决时间依赖网络中的中国邮路问题上是有效的。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 研究背景及意义
• 1.2 研究现状
• 1.2.1 中国邮路问题研究现状
• 1.2.2 时间依赖最短路径问题研究现状
• 1.2.3 时间依赖车路由问题研究现状
• 1.2.4 智能算法研究现状
• 1.3 本文的研究方法及主要工作
• 1.4 本文的组织结构
• 2 传统中国邮路问题
• 2.1 邮路问题基本定义
• 2.2 欧拉图的寻迹算法
• 2.2.1 弗罗莱算法
• 2.2.2 End-pairing算法
• 2.3 无向中国邮路问题
• 2.3.1 无向中国邮路问题的提出
• 2.3.2 整数线性规划定义
• 2.3.3 无向中国邮路问题求解算法
• 2.4 有向中国邮路问题
• 2.4.1 有向中国邮路问题的提出
• 2.4.2 整数线性规划定义
• 2.4.3 有向中国邮路问题算法
• 2.5 混合中国邮路问题
• 2.6 风向邮路问题
• 2.7 一般邮路问题
• 2.8 层次邮路问题
• 3 时间依赖网络
• 3.1 时间依赖网络基本定义
• 3.2 FIFO与非FIFO时间依赖网络
• 3.3 时间依赖函数分类讨论
• 4 时间依赖网络无向中国邮路问题
• 4.1 时间依赖网络无向中国邮路问题的定义
• 4.2 TDCPP问题的性质
• 4.2.1 TDCPP的基本性质
• 4.2.2 TDCPP的NP-hard性质
• 4.2.3 一类可以用传统算法解决的TDCPP网络
• 5 TDCPP的二层SA/GA算法
• 5.1 智能算法简介
• 5.1.1 模拟退火
• 5.1.2 遗传算法
• 5.1.3 蚁群算法
• 5.1.4 禁忌搜索算法
• 5.2 二层SA/CA算法
• 5.2.1 外层模拟退火算法
• 5.2.2 内层遗传算法
• 5.3 算法测试及分析
• 5.3.1 测试问题产生
• 5.3.2 问题下界生成策略
• 5.3.3 计算结果
• 5.3.4 计算结果分析
• 结论
• 参考文献
• 攻读硕士学位期间发表学术论文情况
• 致谢