路径规划在车辆导航系统中的应用研究.pdf

北京交通大学
硕士学位论文
路径规划在车辆导航系统中的应用研究
姓名:田明星
申请学位级别:硕士
专业:通信与信息系统
指导教师:李兴华
20090601
中文摘要摘要:智能交通系统有助于减少交通堵塞,实现交通流量的合理分配,促进交通路网的有效利用,能够为日益严重的交通问题提供完整的解决方案。车辆导航系统是智能交通系统的重要组成部分,随着定位技术、通信技术、地理信息技术等技术的迅速发展,车辆导航系统逐渐成为研究的热点。路径规划要求车载导航设备可以依据电子地图的拓扑信息,帮助驾驶员采用某种策略快速计算出从始发地到目的地的最优路径,是车辆导航系统的核心技术之一,也是实现准确、实时车辆导航的基础。路径规划对于车辆导航系统的研究和实现具有极其重要的作用。本文主要研究车辆导航系统中的路径规划部分。首先,在全面分析车辆导航系统组成模块基础上,介绍了路径规划的概念,发展现状以及基本原理,并结合图论的相关理论,对影响路径规划算法效率的交通路网结构以及电子地图做了详细的阐述。然后分析了常见的路径规划算法原理,实现方法以及优缺点,并详细研究了启发式搜索算法。本文以嫠惴ㄎ;∩杓聘慕惴ǎ訟幸算法的基本原理和实现步骤都做了全面的分析,提出了对节点采用最小堆的排序方法进行姿惴ǖ挠呕⒔岷纤向搜索和分层搜索策略,完成了基于最小堆的双向分层搜索姿惴ǖ母慕惴ā在引入双向搜索策略的算法中,对双向搜索的停止条件以及切换标准做了初步的探讨。在比较了常见的7⒎椒ê螅范ú捎眉啥慰7⒌⒐ぞ遃为开发平台进行应用开发,在灵图版电子地图上实现了改进后的路径规划算法,并得出实验结果。最后,以各种算法搜索得到的路径长度和算法运行时间为衡量标准,分析比较了传统樗惴ǎ蛩阉鰽宰算法,基于最小堆的双向搜索钏惴ê突谧钚《训双向分层搜索仕惴ǖ氖笛榻峁⒌贸鼋崧郏慕惴ǖ穆肪端阉魉俣扔辛嗣显提高,从而验证了本文中改进算法的可行性和合理性。图幅,表觯慰嘉南!关键词:车辆导航系统;路径规划;舅惴ǎ蛔钚《眩凰蛩阉鳎环植闼阉分类号:.;
..襛.,甋琾琲...琣:.甈—瑃綼譨琤瓵...瓸,,,
;:,襛,耡,耡譨,;黙;;篣籘,;
图图盗镜己较低车淖槌赡?椤图邢蛲己臀尴蛲肌图ㄓ邢蛲嫉牧诮泳卣蟊硎痉ā图ㄓ邢蛲嫉牧诮颖肀硎痉ā舅惴ㄋ阉鞴獭图菜惴鞒掏肌图阉骺占涫疽馔肌图谧钚《训乃蛩阉鰽木算法流程图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图分层搜索示意图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.图植闼阉髁鞒掏肌图肪豆婊低辰峁雇肌图肪豆婊低辰缑嫱肌图谧钚《训乃蛩阉餍菜惴ㄊ迪滞肌图谧钚《训乃蚍植闼阉鰽木算法实现图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图
表表缆返燃丁表各种存储结构比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯表四种路径规划算法比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯
啁蠼签字吼朋年⋯伯独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果,除了文中特别加以标注和致谢之处外,论文中不包含其他人已经发表或撰写过的研究成果,也不包含为获得北京交通大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。学位论文作者签名:
:殉叼年拢学位论文版权使用授权书本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索,并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。C艿难宦畚脑诮饷芎笫视帽臼谌ㄋ得.
致谢本论文的工作是在我的导师李兴华副教授的悉心指导下完成的,李兴华副教授严谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢两年来李兴华老师对我的关心和指导。李兴华副教授悉心指导我们完成了实验室的科研工作,在学习上和生活上都给予了我很大的关心和帮助,在此向李兴华老师表示衷心的谢意。荆涛教授对于我的科研工作和论文都提出了许多的宝贵意见,在此表示衷心的感谢。在实验室工作及撰写论文期间,李云强、张耀兰、胡卓、孙静、牛相潮、夏州、熊菲、武夏冰、王迎春等同学对我论文中的研究工作给予了热情帮助,在此向他们表达我的感激之情。另外也感谢家人,他们的理解和支持使我能够在学校专心完成我的学业。
髀的联系在一起,形成了人一车一路三者有机结合的智能交通系统,所以车辆导航随着社会经济的发展,城市化进程的加快以及汽车的逐渐普及,交通拥挤、交通事故、环境污染、能源短缺等问题已经成为了困扰世界各国共同问题。无论是发达国家,还是发展中国家,都毫不例外的承受着不断加剧的交通问题的困扰。解决交通问题的传统办法是修