最短路径算法在组播路由和物流配送中的应用研究

论文摘要

最短路径算法已经得到了广泛的应用,尤其是Dijkstra算法是作为路径优化的核心基础算法而广被使用,本文分别研究了改进的Dijkstra算法在满足时延和时延抖动约束的组播路由和物流配送线路优化中的应用。本文介绍了图论的一些基本概念,包括图、有向无向图的概念,图的搜索遍历算法等,这些概念都是研究最短路径算法的基础。然后介绍了组播路由的相关概念和扩展的Dijkstra算法。针对物流配送网络中交通节点与图顶点的相似性,交通路线与图中边的可类比性,把地理交通网络模拟成计算机容易操作的数据结构-图,使用图中经常应用的Dijkstra算法来解决物流配送线路优化问题。近年来多播技术得到了很大的发展,尤其是多播支持的数字音频和视频应用日益广泛,这些应用往往对服务质量（QoS）有严格的要求。考虑到时延抖动是服务质量的重要因素,本文提出了满足时延和时延抖动约束的多播路由算法,此算法是对Dijkstra最短路径算法的扩展,使得扩展后的Dijkstra不仅可以找到多播源到各接收端的时延最小路径,还可以找到时延介于某一区间段的路径。实验表明,改进的算法与DVMA（delay variation multicast algorithm）算法相比,提高了求解成功率。我们选择堆排序对地理网络中没有标记节点进行排序来改进Dijkstra算法以提高算法的执行效率。同时对物流配送线路中有路障和无路障的路径优化问提供了基于Dijkstra算法的解决方法,并且最后对于诸如车载能力、天气因素的考虑,提供了修正的Dijkstra算法。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 本文选题目的与选题背景
• 1.2 本文的结构
• 1.3 本文所做的主要工作
• 第二章 图论基础及最短路径算法
• 2.1 图的一些基本概念及属性
• 2.2 图的搜索算法
• 2.2.1 图的遍历
• 2.2.2 图的广度优先搜索遍历算法
• 2.3 最小生成树（MST）及Prim 算法
• 2.3.1 最小生成树
• 2.3.2 Prim 算法
• 2.4 最短路径及Dijkstra 最短路径算法
• 2.4.1 最短路径
• 2.4.2 基本原则
• 2.4.3 Dijkstra 算法
• 第三章 最短路径算法在时延及抖动约束的多播路由中的应用
• 3.1 多播技术概述
• 3.2 多播技术基本原理
• 3.2.1 多播地址分配
• 3.2.2 因特网组管理协议
• 3.2.3 组播转发
• 3.2.4 多播路由协议
• 3.3 多播技术研究现状
• 3.3.1 QoS 约束
• 3.3.2 保证服务质量的路由目标
• 3.4 多播路由算法介绍
• 3.4.1 源路由算法
• 3.4.2 分布式路由算法
• 3.4.3 分级路由算法
• 3.5 时延抖动约束的多播路由算法
• 3.5.1 服务质量中的时延要求
• 3.5.2 带有时延和抖动约束的多播路由问题
• 3.5.3 算法描述
• 3.5.4 算法分析
• 3.6 模拟实验
• 3.6.1 算法求解成功率比较
• 3.6.2 网络费用的比较
• 3.7 小结
• 第四章 最短路径算法在物流配送线路优化中的应用
• 4.1 物流配送的概念、现状及意义
• 4.1.1 物流配送的概念
• 4.1.2 物流配送的现状
• 4.1.3 物流配送的意义及作用
• 4.2 车辆路径问题
• 4.2.1 车辆路径问题的定义
• 4.2.2 路径特性（The Characteristics of Route）
• 4.2.3 常用到的基本问题
• 4.2.4 车辆路径问题的求解方法
• 4.3 Dijkstra 算法在物流配送线路中的应用
• 4.3.1 最短路径算法在无路障的配送线路中的应用
• 4.3.2 当配送线路中有路障的情况下路径的优化
• 4.4 在一个实际案例中的应用
• 第五章 结论
• 致谢
• 参考文献
• 研究成果