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

运用贪婪算法构建物流网络的方法与应用研究

作　者: 任文轩
导　师: 刘贵全
学　校: 中国科学技术大学
专　业: 计算机应用技术
关键词: 物流网络 Dijkstra算法 Prim算法
分类号: TP301.6
类　型: 硕士论文
年　份: 2011年
下　载: 94次
引　用: 0次
阅　读: 论文下载

内容摘要

贪婪技术就是在每一步操作中,“贪婪”地选择最佳操作,并希望通过一系列局部的最优选择进而对全局问题产生一个最优解。他的特点是一步一步的进行操作,每一步都采用某个优化测度作最优选择从而对目前构造的部分解做一个扩展,直到获得问题的完整解为止。贪婪算法作为一种改进了的分级处理方法,其能否真正解决问题的关键还在于其能否找到合适的量度标准。在一个给定的问题上面,通常都会有好几种不同的量度标准。并且这些量度标准仿佛都是可取的,然而在实际情况中我们如果采用其中大多数的量度标准作处理,我们所得到的“最优解”并不是真正的问题最优解。所以决定一个贪婪算法的效用往往是看其能否选择出产生问题最优解的最优量度标准。本文提出了一种计算物流成本的量度标准,并以该标准作为后面判断的依据。在现代社会中物流产业已经成为国民经济发展的动脉,其发展程度可以说是衡量一国现代化程度和综合国力的重要标志之一。但是目前我国物流成本占GDP比例较高,下降速度也较为缓慢,这反映出我国物流效益整体水平仍然较低。而要改善现状就要提高我们的物流服务,减少物流成本。而运用贪婪算法来处理实际物流中所遇到的物流中心选址和路径选择问题已经成为一个研究方向被人们所关注。本文以舟山海洋经济新区的发展规划为背景,主要工作如下:1)介绍了贪婪算法的概念以及研究现状,并对几种经典的算法(Dijkstra算法和Prim算法)进行了简要介绍和分析。2)研究了贪婪算法在物流中心选址问题上的应用。包括选址问题是如何产生的,以及目前所用的几种解决方法,并着重介绍了运用贪婪算法解决这一问题时的基本原理和计算方法。3)研究了贪婪算法在解决物流路径问题上的应用,并分析所用的基本原理和存在的不足,进而提出一种新的并行计算方法来加以解决。4)运用上述算法对舟山市的物流网络进行分析,并进行了技术实现。

全文目录

摘要  4-5
ABSTRACT  5-10
第一章绪论  10-16
  1.1 贪婪算法介绍  10-11
  1.2 经典贪婪算法简介  11-13
    1.2.1 Prim 算法简介  11-12
    1.2.2 Kruskal 算法简介  12-13
    1.2.3 Dijkstra 算法简介  13
  1.3 本文研究的目的和研究背景  13-14
    1.3.1 研究目的  13-14
    1.3.2 研究背景  14
  1.4 本文的组织结构  14-16
第二章贪婪算法在物流中心选址问题上的应用  16-26
  2.1 选址问题研究应用综述  16-17
    2.1.1 选址分配问题的研究应用现状综述  16-17
    2.1.2 带有中转运输即物流中心的选址分配问题的研究应用现状综述  17
  2.2 物流拓扑图的制定  17-18
  2.3 用多重双向链表的方式来优化图的存储结构  18-20
    2.3.1 无向图G 的邻接矩阵存储  18-19
    2.3.2 无向图G 采用不同数据结构的影响  19
    2.3.3 无向图G 采用多重双向链表的方式存储的数据结构  19-20
  2.4 用 Dijkstra 算法来确定物流中心  20-24
    2.4.1 Dijkstra 算法的运行流程  20-21
    2.4.2 Dijkstra 算法的运行流程图  21-24
    2.4.3 用Dijkstra 算法计算物流中心  24
  2.5 本章小结  24-26
第三章用改进的 Prim 算法来计算最佳路径  26-40
  3.1 Prim 算法的具体实现  26-29
    3.1.1 Prim 算法的具体流程  26
    3.1.2 用Prim 算法计算物流网络的流程图  26-29
  3.2 并行的 Prim 算法  29-34
    3.2.1 提出并行Prim 算法的必要性  29
    3.2.2 本文所提出并行Prim 算法分析  29-31
    3.2.3 本文所提出的并行Prim 算法流程图  31-34
  3.3 本文所提出并行 Prim 算法的先进性分析  34-38
    3.3.1 目前国内对物流路径选择的研究现状  34-35
    3.3.2 本算法的先进性与不足之处  35-38
  3.4 本章小结  38-40
第四章运用本算法验证舟山市物流网络的规划  40-50
  4.1 舟山概况以及物流运输路线介绍  40-41
  4.2 舟山物流拓扑图的制定  41-44
    4.2.1 舟山物流网络拓扑图结点的制定  41-42
    4.2.2 舟山物流拓扑图边的权值的制定  42-44
    4.2.3 舟山物流拓扑图的制定  44
  4.3 运用本算法制定舟山本岛物流网络中心  44-46
  4.4 运用本算法制定舟山本岛物流网络的最优物流线路  46-48
  4.5 本章小结  48-50
第五章贪婪算法的工程应用以及技术实现  50-60
  5.1 介绍 ActionScript3.0  50
  5.2 以 ActionScript3.0 技术为支持建立一个虚拟物流网络平台  50-57
    5.2.1 介绍目前国内交通以及物流现状提出设计虚拟物流网络平台的必要性  50-51
    5.2.2 介绍如何使用 ActionScript3.0 技术实现车辆控制  51-52
    5.2.3 介绍如何使用 ActionScript3.0 技术实现交通地图的载入  52-53
    5.2.4 介绍如何进行碰撞设置  53-54
    5.2.5 介绍如何在平台内部运用Dijksrta 算法来计算物流中心  54-55
    5.2.6 介绍如何在平台内部运用并行Prim 算法来计算最佳物流路径  55-57
  5.3 如何推广应用该平台以及该平台的不足之处  57
  5.4 本章小结  57-60
第六章总结和展望  60-62
  6.1 本文工作总结  60-61
  6.2 本文的不足之处以及未来的工作方向  61-62
参考文献  62-68
致谢  68-69
在读期间发表的学术论文与取得的研究成果  69

运用贪婪算法构建物流网络的方法与应用研究

内容摘要

全文目录

相似论文