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

车辆导航中多路径推荐算法研究

作 者: 叶金平
导 师: 朱征宇
学 校: 重庆大学
专 业: 计算机软件与理论
关键词: 多路径 合理性 混合算法 时间划分
分类号: TP391.3
类 型: 硕士论文
年 份: 2011年
下 载: 37次
引 用: 0次
阅 读: 论文下载
 

内容摘要


随着社会经济的发展和综合国力的增强,如何降低交通堵塞所带来的负面影响成为了我国目前迫切需要解决的问题。本文从实用的角度出发,提出了一种基于遗传算法的能够求解多条准最优路径的混合算法(Hybrid Algorithm, HA)。并在此基础上对它进行改进和提高,以使其更加适应实际的交通现状。由于本文提出的算法给司机提供了多条较优的导航路径,这提高了司机选择路径的主观性,避免了都走同一路径而可能导致的路段堵塞,从而使得司机尽量在预计的时间内到达目的地。本文的主要贡献主要有以下几个方面:①在对多路径问题(Multi-Route Problem, MRP)的数学模型进行分析和研究的基础上,确定了本文中多路径问题所采用的数学模型。同时,对于交通路径诱导系统中的多条准最短路径问题(Multi- Quasi-Shortest Route Problem, MQSRP),介绍并分析了当前主要算法的优缺点,包括Dijkstra算法、Floyd算法、K最短路径算法、A*算法和遗传算法等。②对于交通路径诱导系统中的MQSRP问题,提出了混合算法。此算法主要结合了Floyd算法和A*算法的优点,能有效的解决遗传算法应用于最短路径问题的搜索空间大而导致的瓶颈问题。③为了把本文提出的混合算法应用到实际的交通路网,引入了一种时间划分的路网模型(Time-division Road Network Model, TDRNM)。为了使混合算法能更好以解决实际的交通情况,对引入的模型上增加了一个矩阵变量(S)。④针对MQSRP问题的合理性提出了一种考虑了合理性的混合算法(Considered Rationality Hybrid Algorithm , CRHA)。当前的求解多条导航路线的算法虽然很多,但它们并没有考虑多条路径的合理性,针对这个问题本文提出了CRHA。⑤分别用静态的和基于TDRNM模型对本文提出的混合算法的有效性和效率进行了测试,取得了较好的效果。同时也对CRHA算法的有效性进行了实验,取得了比较满意的结果。

全文目录


中文摘要  3-4
英文摘要  4-7
1 绪论  7-15
  1.1 研究背景及意义  7-9
  1.2 国内外研究现状  9-12
  1.3 论文研究内容  12-13
  1.4 论文组织结构  13-14
  1.5 本章小结  14-15
2 多条准最短路径问题  15-21
  2.1 问题的研究内容  15-17
  2.2 MQSRP 问题的数学模型  17-18
  2.3 MQSRP 问题求解的策略和方法  18-20
    2.3.1 Dijkstra 算法  18-19
    2.3.2 A*算法  19
    2.3.3 K 最短路径算法  19
    2.3.4 Floyd 算法  19
    2.3.5 遗传算法  19-20
  2.4 本章小结  20-21
3 多路径问题的混合算法  21-28
  3.1 混合算法原理  21-22
  3.2 遗传算法  22-26
    3.2.1 染色体编码  23-24
    3.2.2 种群初始化  24-25
    3.2.3 自然选择  25
    3.2.4 进化算子  25
    3.2.5 染色体替换策略  25-26
    3.2.6 适应度函数  26
  3.3 遗传算法演化过程  26-27
  3.4 本章小结  27-28
4 基于时间划分的路网模型  28-33
  4.1 时间划分的依据  28-30
  4.2 TDRNM 模型  30-32
  4.3 本章小结  32-33
5 多路径的合理性及其混合算法  33-41
  5.1 多路径的合理性分析  33-35
  5.2 合理MQSRP 的方法  35-36
  5.3 考虑合理性的混合算法  36-39
    5.3.1 路段数据结构  36
    5.3.2 种群初始化  36-38
    5.3.3 染色体替换策略及数据更新  38-39
  5.4 适应度函数  39
  5.5 CRHA 算法演化过程  39-40
  5.6 本章小结  40-41
6 实验及分析  41-50
  6.1 主要开发工具与运行环境  41
    6.1.1 主要开发工具  41
    6.1.2 实验平台  41
  6.2 混合算法在静态路网中的实验与分析  41-46
    6.2.1 λ的取值与能获得染色体个数的关系  41-43
    6.2.2 λ的取值与算法的计算时间关系  43
    6.2.3 算法对比实验  43-46
  6.3 基于TDRNM 模型的实验与分析  46-48
    6.3.1 模拟交通数据的产生及说明  46-47
    6.3.2 正常和拥挤状态下的效率实验  47-48
  6.4 CRHA 算法的实验与分析  48-49
  6.5 本章小结  49-50
7 总结与展望  50-52
  7.1 研究总结  50-51
  7.2 展望  51-52
致谢  52-53
参考文献  53-57
附录  57
  A. 作者在攻读学位期间发表的论文目录  57
  B. 作者在攻读学位期间取得的科研成果目录  57

相似论文

  1. 基于遗传—牛顿算法的公交优化调度,TP18
  2. 经济领域中的博弈逻辑推理问题探析,B812
  3. 论库恩科学合理性思想,N02
  4. 民事能动司法探究,D926
  5. 基于能量均衡的无线传感器网络多路径路由算法的研究,TP212.9
  6. SCTP多路径传输性能研究,TN915.04
  7. 电力系统无功优化的混合算法研究,TM714.3
  8. 从合理性走向合法性:上海市私人轿车牌照额度拍卖政策的研究,F426.471
  9. 面向无线传感器网络的多路径路由协议研究,TN915.04
  10. 基于路预测访问的低功耗高速缓存设计研究,TP333
  11. 多核系统中实时任务调度算法的研究,TP332
  12. 基于动态网络编码的高速移动自组网多径组播技术研究,TN929.5
  13. 基于液晶空间光调制器的激光束整形,TN24
  14. 珠三角公路运输网络规模的合理性和发展规律研究,U491.13
  15. 不纯正不作为犯之作为义务研究,D914
  16. 商业秘密反向工程问题研究,D923.4
  17. 医院挂号费法律问题研究,D922.16
  18. 人工萤火虫群优化算法改进及应用研究,TP18
  19. 基于混合算法的研究生招生考试考场座位编排系统研究及应用,TP391.6
  20. 萤火虫群算法的改进及其应用,TP301.6

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机的应用 > 信息处理(信息加工) > 检索机
© 2012 www.xueweilunwen.com