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

大规模路网下中心式路径优化方法研究

作　者: 李大伟
导　师: 于德新
学　校: 吉林大学
专　业: 交通运输工程
关键词: 大规模路网路径优化光谱对分递阶式网络分解最优路径并行计算双端队列
分类号: TP301.6
类　型: 硕士论文
年　份: 2011年
下　载: 76次
引　用: 0次
阅　读: 论文下载

内容摘要

动态交通诱导系统是智能交通系统的重要组成部分,其中的中心式路径诱导可以有效避免Braess悖论现象,充分提高路网的利用率,避免分布式路径诱导引起的拥挤漂移现象的出现,因此被公认为是有效解决城市交通拥挤问题的有效方法。目前常规的路径优化串行算法较难以在合理的时间范围内求解大规模路网的最优路径,而并行算法采用将单个任务分解为多个子任务分别处理的方式,可以有效提高求解效率。本文依托国家自然科学基金项目“大规模路网下中心式路径优化理论模型与方法研究”对大规模路网下中心式路径优化方法进行研究。本文分析了进行动态交通诱导研究的背景和意义,回顾了国内外目前对于城市交通诱导系统和路径优化算法的研究现状,提出本文的研究思路和研究内容。研究了路网的表达与存储方法,对两种连通性表达方法进行了对比;分析了中心式路径优化算法对路网分解的要求,介绍了多种路网分解方法和算法并进行对比分析,结合光谱对分法的优点,将其引入到递阶分解方法中,研究基于光谱对分的递阶分解方法;考虑到最优路径算法是影响大规模路网下中心式路径优化实时性的重要因素,在前文路网分解研究的基础上,对一对多(one-to-all),多对多(all-to-all)两种类型算法的并行算法以及并行算法可扩展与效率提高方法进行研究,将数据结构中的双端队列引入最优路径计算,研究了大规模路网下双端队列最优路径并行计算方法,通过搭建并行计算平台对上述研究进行验证均取得较好效果。全文共分五章,各章的研究内容如下:第一章,绪论。介绍本文的研究背景和研究意义,提出针对研究对象的研究价值。分析城市交通诱导系统和路径优化算法两方面的国内外研究现状,在此基础上,介绍本文的主要研究内容及框架;第二章,路网的表达存储与分解方法研究。大规模路网中交叉口转向限制和交叉口延误信息较为庞大,因此如何采用经济可靠的路网结构表达方式和存储结构在计算符合实际道路情况的最优路线的过程中显得尤为重要。本章在分析了路网的基本特点和要求,介绍和分析了常用的路网连通性表达方法和存储方法。之后在考虑适于中心式路径优化的路网分解要求的前提下,对多种分解方法和分解算法进行研究,以能够分割大规模路网的计算域、降低通信时间及后续路径计算复杂度的目的,研究了基于标准矩阵的光谱对分网络分解方法。第三章,中心式最优路径计算方法研究。考虑到大规模路网的交通数据量巨大,路网复杂的特点,分析目前单个计算机处理技术的不足,引入并行计算方法处理大量数据问题,为解决大规模路网的路径优化问题提供了新的思路。本章通过对并行计算进行研究内容、设计思路和过程等方面的介绍,进行一对多(one-to-all),多对多(all-to-all)两种类型算法的并行算法以及并行算法可扩展性方面的研究,将数据结构中的双端队列引入最优路径计算过程,研究大规模路网下双端队列最优路径并行计算方法。第四章,算法验证。本章通过构建并行计算平台,对上文提到的中心式路径优化方法进行试验,针对实际数据和路网信息进行模拟和结果分析,证明该方法的实用性。第五章,总结与展望。本章回顾全文的研究意义与主要研究内容,对全文进行总结并指出未来的研究方向。

全文目录

摘要  4-6
Abstract  6-10
第一章绪论  10-18
  1.1 课题来源  10
  1.2 研究背景与研究意义  10-13
  1.3 研究现状  13-16
  1.4 研究思路  16
  1.5 章节安排  16-17
  1.6 本章小结  17-18
第二章路网的表达存储与分解方法研究  18-31
  2.1 概述  18
  2.2 路网的特点与基本元素  18-20
  2.3 路网的连通性表达与存储方法研究  20-25
    2.3.1 路网的连通性表达方法  20-23
    2.3.2 路网的存储方法  23-25
  2.4 路网分解方法研究  25-28
  2.5 中心式路径优化路网分解方法研究  28-30
    2.5.1 中心式路径优化路网分解要求  28-29
    2.5.2 中心式路径优化路网分解算法  29-30
  2.6 本章小结  30-31
第三章大规模路网最优路径算法研究  31-54
  3.1 概述  31
  3.2 经典的路径优化串行算法  31-37
    3.2.1 Bellman-Ford-Moore 算法  35-36
    3.2.2 Pallottino 算法  36-37
  3.3 并行计算  37-45
    3.3.1 并行计算的研究内容  37-38
    3.3.2 并行算法的性能评估  38-39
    3.3.3 并行计算的设计思路  39
    3.3.4 并行算法的设计过程  39-43
    3.3.5 串行算法的并行化研究  43-45
  3.4 最短路径并行算法  45-50
    3.4.1 一对多类型最短路径并行算法  46-49
    3.4.2 多对多类型最短路径并行算法  49-50
  3.5 终止检测  50-52
  3.6 本章小结  52-54
第四章中心式路径优化方法验证与分析  54-60
  4.1 试验环境  54
  4.2 验证结果及分析  54-59
    4.2.1 路网分解验证结果  54-57
    4.2.2 最短路径并行计算试验结果  57-59
  4.3 本章小结  59-60
第五章总结与展望  60-62
  5.1 全文总结  60
  5.2 论文展望  60-62
参考文献  62-64
攻读硕士学位期间参与的科研项目  64-65
致谢  65

大规模路网下中心式路径优化方法研究

内容摘要

全文目录

相似论文