（系统工程专业论文）车载导航系统最优路径规划的研究.pdf

北京交通人学硕+ 学位论文 中文摘要 中文摘要 摘要：车载导航系统是智能交通系统的一个重要组成部分，是综合应用车辆 定位技术、地理信息技术、计算机技术、网络技术及现代通信技术等构成的车辆 辅助驾驶系统。使用这种系统后，能够有效防止交通堵塞和减少交通事故的发生， 减少车辆在道路上的逗留时间。它是一种有效的解决城市交通搠挤问题的手段。 车载导航系统的一个基本功能就是路径规划，即帮助驾驶员找到一条从出发 地到目的地的最优路径。为了保证路径规划算法在车辆导航系统中的实用性和技 术可行性，本文研究提出了一种路段权值计算模型，该模型与以往权值函数不同 的是，考虑了交叉口排队长度的影响，使得行程时间部分估计更加准确。 实际的车辆导航系统对路径规划求解的快速性有很高的要求，对求解的最优 性的要求则相对较低。本文结合道路网的特点，采用双向搜索、投影法及二叉树 理论，给出一种快速路径规划算法。通过和d i j k s t r a 算法的实验分析表明，该算法 搜索空间小，搜索速度更快，适用于车辆导航系统。 最后，论文给出了车载导航系统样机研制方案，包括能够安装在公交车、小 汽车或其它相关机动车辆上的车载设备，以及数据中心端的通讯接收软件。并给 出了基于w i n d o w sc e 操作系统下的多线程编程技术、g p s 数据处理和串口通讯技 术的实现过程。 关键词：车辆导航；路权函数；最优路径规划；g p s ；串口通信 分类号： i i i 北京交通人学硕十学位论文 a b s t r a c t a bs t r a c t a b s t r a c t ：v e h i c l en a v i g a t i o n s y s t e mi s a ni m p o r t a n tp a r to fi n t e l l i g e n t t r a n s p o r t a t i o ns y s t e m ，w h i c hi sad r i v e ra s s i s t a n c es y s t e mb yc o m p r e h e n s i v e l ya p p l i e d v e h i c l ep o s i t i o n i n gs y s t e m ，g e o g r a p h i c a li n f o r m a t i o nt e c h n o l o g y , c o m p u t e rt e c h n o l o g y , n e t w o r kt e c h n o l o g ya n dm o d e mc o m m u n i c a t i o nt e c h n o l o g y i ti se f f e c t i v et op r e v e n t t r a f f i cb l o c k a g e ，d e c r e a s et r a f f i ca c c i d e n t sa n dr e d u c ev e h i c l ed e l a y i n gt i m ei nt h er o a d ab a s i cf u n c t i o no fv e h i c l en a v i g a t i o ns y s t e mi sp a t hp l a n n i n g ，w h i c hh e l p sa d r i v e rf i n da no p t i m a lp a t hf r o md e p a r t u r ep l a c et od e s t i n a t i o n i no r d e rt op r o v et h e p a t hp l a n n i n ga l g o r i t h m sp r a c t i c a l i t ya n dt e c h n i c a lf e a s i b i l i t y , t h et h e s i sp u tf o r w a r da c a l c u l a t i o nm o d e lo f r o a ds e c t i o nw e i g h tv a l u e ，w h i c hi sd i f f e r e n tf r o mp r e v i o u sw e i g h t v a l u em o d e l s a st h ee f f e c to fi n t e r s e c t i o nq u e u el e n g t hi st a k e ni n t oa c c o u n t ，i tm a k e s e s t i m a t i o no ft r a v e l i n gt i m em o r ea c c u r a t e a c t u a lv e h i c l en a v i g a t i o ns y s t e mh a sah i g hd e m a n do fp a t hp l a n n i n gs o l u t i o n s r a p i d i t ya n dal o wd e m a n do fi t so p t i m a l i t y b a s e do nc h a r a c t e r i s t i c so fr o a dn e t w o r k ， t h et h e s i sp r o p o s e sar a p i dp a t hp l a n n i n ga l g o r i t h mb yu s i n gb i d i r e c t i o n a ls e a r c h ， p r o j e c t i o nm e t h o da n db i n a r yt r e et h e o r y c o m p a r i n gw i t ht h ee x p e r i m e n t a la n a l y s i so f d i j k s t r aa l g o r i t h m ，t h ea l g o r i t h mh a ss m a l l e rs e a r c h i n gs p a c ea n d f a s t e rs e a r c h i n gs p e e d ， s oi ti sm o r es u i t a b l ef o rv e h i c l en a v i g a t i o ns y s t e m a tl a s t ，i ti sg i v e nt h ed e v e l o p m e n ts c h e m eo fv e h i c l en a v i g a t i o ns y s t e mp r o t o t y p e ， i n c l u d i n gv e h i c l ee q u i p m e n tw h i c hc a nb ei n s t a l l e di nb u s ，c a r sa n do t h e rr e l a t e dm o t o r v e h i c l ea n dc o m m u n i c a t i o nr e c e i v i n gs o f t w a r eo fd a t ac e n t e rt e r m i n a l i ti sa l s og i v e n r e a l i z a t i o np r o c e s so fm u f f t h r e a d i n gp r o g r a m m i n gt e c h n i q u e ，g p sd a t ap r o c e s s i n ga n d s e r i a lp o r tc o m m u n i c a t i o nt e c h n o l o g yb a s eo nw i n d o w sc eo p e r a t i n gs y s t e m k e y w o r d s ：v e h i c l en a v i g a t i o ns y s t e m ；r o a ds e c t i o nw e i g h tv a l u em o d e l ；o p t i m a lp a t h p l a n n i n g ；g p s ；s e r i a lp o r tc o m m u n i c a t i o n c l a s s n o ： i v 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 萄辜霞 签字日期：2 口。7 年石月店日 导师签名： 肄旱 签字蹶矽7 年多月髫日 ， 北京交通人学硕十学佗论文独创性声明 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：签字日期：年月 日 4 5 致谢 本论文的工作是在我的导师毕军教授的悉心指导下完成的，毕军教授严谨的 治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢两年来毕军 老师对我的关心和指导。 在实验室工作及撰写论文期间，王晓华、谢芳、陈石等同学对我论文中的研 究工作给予了热情帮助，在此向他们表达我的感激之情。 另外也感讶十我的父母，他们的理解和支持使我能够在学校专心完成我的学业。 i i 北京交通人学硕十学位论文绪论 1绪论 随着经济的发展和汽车拥有量的增加，交通拥堵问题r 益严重，不断恶化的 交通状况越来越网扰着世界各国的大城市，美国德州运输研究所研究美国3 9 个 主要城市，估算美国每年因交通阻塞而造成的经济损失约为4 1 0 亿元，其中1 2 个大城市每年的损失超过1 0 亿美元，预测到2 0 2 0 年，因事故造成的经济损失每 年将超过1 5 0 0 亿美元。在同本，仅首都圈，严重拥挤地点就有2 1 9 处，在首都 高速道路拥挤严重的路段，其拥挤时间长达1 7 小时，拥挤长度达9 8 7 千米。东 京每年因交通拥挤造成的交通时i 、h j 损失约为1 2 3 0 0 0 亿同元。国内如北京、上 海等城市，交通拥堵也比较严重。虽然政府部门和相关科研单位投入大量人力物 力进行研究，但是问题仍然未得到彻底解决，部分城市部分道路拥堵依然很严重。 交通拥堵具有明显的时空特性，具体表现在一定的时间、一定的路段经常发 生交通拥堵。随着新建道路和交通基础设施的增加，单行线、交叉口转向控制等 交通管理措施被越来越多的采用。对于出行者来说，增大了出行路线选择的空问， 但同时也带来了出行的复杂性。由于缺乏良好的导航和路线诱导，实际交通行为 中存在大量的无效出行，使得交通拥堵和交通事故发生的机率增加，针对这种情 况，广大科研工作者一直致力于解决交通拥堵问题的研究，而车载导航系统正为 解决此问题提供了一个崭新的思路。其作为切实可行的解决交通拥堵问题的方案 之一，正日益受到社会的重视。 车辆导航就是在电子地图的基础上，运用g p s ( g l o b a lp o s i t i o n i n gs y s t e m ) 等 定位技术进行车辆定位，确定最优行驶路线，为出行者提供静态的或实时的最优 出行路线信息，并在出行过程中对驾驶员适时地做出路线指导。车辆导航系统是 i t s 的重要组成部分，它不仅极大地方便了出行者，使他们可以按照自己选定的 最优目标获得最优路线信息，而且还会对优化交通流在整个路网的分配方面产生 积极的影响【2 】【3 l 。 1 1 车载导航系统国内外研究与发展 世界上，现代车辆导航方面的研究己经有3 0 多年的历史。自1 9 9 4 年由美国 国防部发布全球定位系统( g p s ) 以来，g p s 导航技术在民用市场发展迅速，它融 合了汽车、交通、计算机、通信、系统科学等领域的技术，一直是众多高科技公 司和各个大学研究的热点。早期的导航系统主要是利用惯性导航设备如陀螺、罗 盘等实现车辆定位、航位推算等功能。由于该系统使用局限性很大，一直没有得 北京交通人学硕+ 学位沦文绪论 到很好的推广。随着微电子技术的迅速发展和g p s 的芯片制造成本的迅速下降， g p s 导航技术的应用己经扩展到各个领域。进入9 0 年代后期，以g p s 导肮和地 图数据匹配技术为基础的汽车导航产品开始进入市场，并高速增长，目前己成为 g p s 最大的消费市场。 当f j 用于i t s 中的汽车导航系统包括两部分：全球定位系统和车辆自动导航 系统。汽车导航系统中的g p s 信号接收器接收卫星发送的信号，如果地面接收 机同时收到4 颗以上的卫星信号，就能根据卫星的精确位置及发送信号的时刻， 通过计算以求得当前地点的位置。汽车导航系统通过车轮传感器、地磁传感器和 偏航传感器等三种传感器获取数据，确定汽车的速度和位置。车轮传感器记录车 轮的速度，产生的脉冲信号用于定时计算行驶距离和方向变化。地磁传感器通过 励磁绕组感应出电压脉冲，测量出沿途地磁场水平分量的大小与起始点磁场的比 较，为车载电脑提供补偿数据。电子地图存储容量能够存储汽车运行区域的所有 数据，车载电脑与存储道路网络数据不断比较判断，更正定位误差从而确定最佳 行驶路径。驾车者只要将目的地输入汽车导航系统，系统就会根据电子地图自动 计算出最合适的路线，并在车辆行驶过程中( 例如转弯前) 提醒驾驶员按照计算的 路线行驶。在整个行驶过程中，驾车者根本不用考虑该走哪条路线就能快捷地到 达目的地。 在导航系统中，能够提供必要信息并能时刻提供最佳行车路线指引的汽车导 航系统开始成为汽车消费新热点。输入目的地的方式多样，可以帮助驾驶员在最 短的时间内找到目的地，其中的多路径选择，推荐道路，高速优先，距离优先等 形式协助司机选择最佳路线开始行程。导航中，即使错过方向，导航器仍然可以 重新计算路径，确保万无一失。即使在完全陌生的城市穿行，也能以最快速度到 达目的地。 目前先进的汽车导航系统多用单片机结构，嵌入式操作系统，软件代码存储 于r o m 中，代码简洁，运行可靠，启动及关闭迅速，具有几乎完整的p c 组件 和输入输出端口，适应汽车恶劣的工作环境，在高温或低温以及剧烈振动环境下 工作可靠性高。 卫星导航产业在车辆应用方面的发展基本上有两大类：一类是以日本为代表 的自主导航类，由于同本的特殊环境与需求，政府资源与大财团的资金巧妙结合 以及车辆道路信息系统的实施，大大促进了自主导航产业的发展；另一类是欧美 和中国为代表的监控跟踪类，服务于安全防范、车队管理、物流调度。 近几年来，两大类有合二为一的发展倾向，进一步体现了卫星导航车辆终端 的服务特征，为增值服务奠定了基础。从系统的通讯方式来看，最早的系统大都 采用专业网，实现系统及系统的营运费用都比较高，对g p s 定位的盲区也要采 2 北京交通人学硕十学位论文绪论 用专门的软硬件方案来解决。随着短信平台的推广应用，利用短信息在车载终端 和监控中心之间进行通讯的方式迅速被采用和推广。目前国内的相关产品，其通 讯方式大多采用短消息平台，这种短信息服务( s m s ) 使信息传输更加方便快捷， 使g p s 系统的组建费用大幅度降低，营运费用也有了较大幅度的下降。 1 1 1国外车载导航系统研究现状 目前，车辆导航技术最发达的地区是美国、同本和欧洲地区，其导航技术的 现状代表了本领域研究和应用的发展方向，尤其是同本导航技术的发展更是处于 领先地位。在同本，由于其城市路网稠密而且布局不合理，改造费用又比较高， 所以对导航系统研究的比较早，并得到了政府和有关部门的支持，再加上其雄厚 的经济和科技实力以及出色的制造技术，使同本在车辆导航装置方面的研究开发 和生产处于世界领先水平。8 0 年代市场上就出现了带有彩色显示器并以光盘驱 动器作为数字地图存储介质的自主导航系统，此后，融入许多诸如地图匹配、g p s 、 声音引导等新技术的各式各样的导航产品应运而生。目前，同本的车辆导航系统 已经成为极其普通的车载设备。车载设备的年销售量维持在几百力- 套，超过6 0 的新车出厂时己安装了车辆导航系统，还形成了一批著名的导航器生产厂商，如 建伍、歌乐、松下、阿尔派、先锋等。为了进一步提高汽车导航和定位的应用技 术和促进汽车导航系统的发展，同本采用修正式d - g p s 技术，利用f m 频道进行 误差修正，大大提高了汽车的定位精度，可达到1 0 m 精度的定位等级。它再辅以 道路交通通信技术及自导式电子地图光盘，其覆盖率已达8 0 的同本地区。在欧 洲，以德国为代表，法国、英国和荷兰等国紧跟其后。德国己经能够批量生产与 汽车导航设备配套的光盘交通图，由飞利浦、西门子、宝马等公司开发的车辆导 航系统在欧洲己经得到了广泛的应用。在美国，自从军方宣布开发一部分g p s 时，就开始了民用汽车导航的研究h 1 。 1 9 9 5 年时，其研制的城市道路交通管理系统就开始投入使用，为城市道路 交通管理起到了重要的作用。2 0 0 5 年美国汽车导航仪市场规模达到1 5 0 万台。 在亚洲除同本外，韩国和我国的台湾地区在导航技术上的研究和应用也比较先 进。韩国研制的h n s 一2 0 0 0 卫星导航系统在1 9 9 8 年就投入商业使用，该系统在 c 卜r o m 光碟上储存着韩国的全国公路交通网及服务设施有关资料，可供驾车者 随时查阅。 1 1 2 国内车载导航系统研究现状 8 0 年代后期，我国开始了自主导航基础性的研究和开发工作，包括优化道 路交通管理、交通信号采集、驾驶员考试系统、车辆动态识别等；9 0 年代开始 北京交通人学硕+ 。学位论文绪论 建设交通控制中心或交通指挥中心，并开展了驾驶员信号系统、城市交通管理的 诱导技术等方面研究，但一直没有成熟的车辆自主导航产品。近年来越来越多的 国内厂商进入到车辆导航产品的研究领域，已有近百家的国内专业生产商推出了 汽车用g p s 产品。在北京，市内的部分出租车已经配置了基于p d a 的导航系统， 但产品功能比较单一，定位精度较差而只能起到一定的过渡作用。 2 0 0 8 年北京奥运会确定的十大科技重点项目，其中之一就是北京智能交通 规划及实施项目。在2 0 0 4 年7 月2 1 同，上海市质量技术监督局发布了“2 0 0 4 上海国际工业博览会科技论坛一一世博与智能交通标准化国际研讨会一通知， 其中议题之一就是“上海世博会大环境下，城市与长三角区域智能交通i t s 发 展”。这些都表明，我国的各大城市己经开始重视了i t s 的发展和应用晦1 。 2 l 世纪的中国将成为全球最大的信息技术市场，中国的手机用户和互联网 用户将成为世界上最大的用户群。随着宽带网和移动网的普及应用，g p s g i s 无线通信技术的综合应用必将迅速推广，属于i t s 核心技术之，的车辆自主导航 系统将有更多机会开辟新的更为广阔的国内市场。我国i t s 的现实市场已初现端 倪，潜在市场蕴含丰富。随着技术的发展以及更多厂商的介入，我国的车辆自主 导航产品必将进入广大人民的生活，给人们出行真正带来便利。 导航技术虽然现在m ；i n 起步，但是该产业在国内的发展是必然的，是不可缺 少的，它作为一种新的产业将具有非常现实而又重大的意义。 1 2 最短路径算法研究背景与现状 最短路径算法是图论中的一个经典问题，它的研究起源于2 0 世纪5 0 年代来 期，至今己有近5 0 年的历史，大约有两干多篇文献讨论此问题。最短路径不仅 仅指一般地理意义上的距离最短，还可以引申到其他的度量，如时间、费用、线 路容量等，以满足不同系统的不同需求。无论是距离最短、时间最快还是费用最 低，它们的核心算法都是最短路径算法。 1 2 1国内外研究现状 针对不同的网络特征、应用需求及具体的软硬件环境，各种最短路径算法在 空间复杂度、时间复杂度、易实现性及应用范围等方面各具特色。1 9 9 3 年， c h e r k a s s k y 等人在随机平面网络中从己有的最短路径算法中选择了比较有代表 性的1 7 种最短路径算法进行测试，测试结果表明：没有哪一个算法能够适应所 有类型的网络。1 9 9 6 年，f b a n j a m i nz h a n 等人用实际交通网络进行了测试，结 果显示有3 种算法比较好，它们分别是：t q q ( g r a p hg r o w t hw i t ht w oq u e u e s ) ， d k a ( t h en i j k s t r a sa l g o r i t h mi m p l e m e n t e dw i t ha p p r o x i m a t eb u c k e t s ) 以 4 北京交通人学硕+ 学位论文绪论 及d k d ( t h ed i j k s t r a sa l g o r i t h mi m p l e m e n t e dw i t hd o u b l eb u c k e t s ) 哺1 。其 中t q q 算法的基础是图增长理论，较适合于计算单源点到其他所有点i 、日j 的最短路 径，后两种算法则是基于d i j k s t r a 的算法，是目前已知理论上最完善的算法， 是多数系统解决最短路径问题采用的理论基础。它更适合于计算两点i 日j 的最短路 径问题，目前在交通运输领域有着广泛的应用。在我国最短路径算法除了应用于 计算机网络通讯技术领域之外，主要用于城市智能交通中车辆监控导航系统以及 路径优化系统，其中吉林大学交通学院i t s 研究实验室、同济大学的i t s 研究中 心和清华大学的交通研究所在这方面取得了一定的研究成果。 1 2 2研究热点 目前对最短路径算法的研究主要从算法的存储空间和计算时i 、日j 两方面进行， 近年来的研究热点主要有以下几方面： ( 1 ) 限定搜索范围或限定搜索方向以减少计算量，提高系统效率； ( 2 ) 充分利用启发式信息提高搜索速度； ( 3 ) 路网权值的确定方法，使算法更能体现真实的路网信息，以提高系统 的实时性； ( 4 ) 实时交通信息系统的研究。 1 3 论文的研究内容和组织结构 最优路径规划是车辆定位导航系统的一个基本应用，要求能够按照存储在其 内部的电子地图的拓扑信息，实时准确地规划出一条最优路径用于车辆导航，其 目的是帮助车辆驾驶人员或调度人员在车辆出发地和目的地确定的情况下按照 某种策略选定一条最优路径。根据实际应用目的的不同，在路径规划中可以采用 的最优标准有很多，如最短行车距离、最少行车时间、最低费用等。无论采用何 种标准，最优路径规划最终都可以归结为在特定道路网中寻找具有最小代价的最 短路径问题，即图论中的最短路径问题。 1 3 1 研究内容 本文主要进行以下几方面的工作： ( 1 ) 详细分析和讨论了最短路径搜索策略和常见的最短路径算法； ( 2 ) 研究路网权值确定方法，通过分析以往权值计算模型发现，在计算路 段部分行驶时间时，模型并没有考虑交叉口的排队长度，只是用路段长度除以平 北京交通人学硕士学位论文绪论 均速度来获得该路段的行程时间，参考动态交通分配中路段阻抗的研究成果，为 了提高车载导航路径规划的实时性和有效性，有必要考虑路段排队长度，因为在 很多大中型城市中，交叉口排队现象很明显，排队长度较长。同时考虑交通管制、 道路等级及其他因素的影响，构造了更加符合实际的车辆导航路段权值计算模 型。 ( 3 ) 结合道路网的特点，采用双向搜索、投影法及二叉树理论，提出一种 快速路径规划算法。通过和d i j k s t r a 算法的实验分析表明，该算法搜索空间更小， 搜索速度更快，满足车辆定位与导航系统的要求，有很强的实用性； ( 4 ) 研究和探讨了车载导航系统样机的设计开发，给出了导航系统软硬件 设计方案。对软件设计中的一些关键技术进行详细介绍，包括g p s 、串口、g p r s 技术等。 1 3 2组织结构 第一章绪论，主要介绍了车辆导航系统和最短路径算法的国内外研究现状以 及论文研究内容、结构安排。 第二章讨论了导航系统路径规划中路段权值的确定方法，构造了更加符合实 际的车辆导航路段权值计算模型。 第三章最短路径算法的研究，阐述了关于最短路径算法的图论基础，对 d i j k s t r a 算法进行了深入分析。 第四章设计了一种基于双向搜索、投影法和二叉树理论的的快速路径搜索方 法。通过与传统d i j k s t r a 算法的对比实验表明，该算法搜索空间更小，运行时 间更短，搜索过程快速地趋于目标结点，执行效率较高，满足导航系统快速路径 规划的特点。 第五章给出了车辆导航系统样机的软硬件研发方案。 6 北京交通人学硕十学t ：7 ：论文最优路径规划中路段权值的确定 2 最优路径规划中路段权值的确定 最优路径的评判标准很多，主要包括行车距离最短，行程时间最短、道路质 量最优以及某些特定要求，( 如沿途经过的交叉口最少，风景点最多、能见度最 高等) 。要查找最优路径，必须确定路阻权值。如果搜索距离最短的静念路径， 则权值为路段长度；而如果是搜索时间最短的动态路径，则权值必须综合考虑各 种影响行车效率的因素，由于各种静念交通规则信息的p i l l 0 以及动态交通流量信 息的变化，使得搜索车辆的最佳行驶路径变成了一个非常复杂的问题，但它又是 车辆监控导航系统以及智能交通系统中必须要解决的基本问题。 影向行车效率的因素主要有： ( 1 ) 路段上的速度和密度 在机动车的行车过程中，路段速度是影响行车效率的一个最重要的指标，速 度快，才能节省时间。车流密度也是衡量路段交通量的一个重要指标，而密度和 速度又有一定得相关性，简单来说就是密度大车速小，密度小车速慢n 1 。 ( 2 ) 交叉口的延误时问 车辆在交叉口遇到红灯必须停车等待，这会造成延误。城市中，交叉口比较 多，在交叉口的延误时问占整个行程的比例比较高，所以交叉口的延误是影响行 车效率的一个重要因素。 ( 3 ) 交通管制信息 为了通行顺畅，缓解交通压力，并出于人身安全等因素的考虑，交通管理部 f l l j 订了一系列的交通规则。如限制速度、限制单行、限制拐弯、限时通行等， 这些交通规则都影响着行车效率。 ( 4 ) 道路等级 道路级别分为高速公路、国道、环城公路、一般公路，其中一般公路也分成 不同的级别，如一级公路二级公路。道路等级不同，其路面质量不同，允许的最 大车速不同。如果行程跨越省或市，一般只走高速公路或国道，因此不同级别的 道路其行车效率不同。 ( 5 ) 其他因素的影响 还有一些其他因素会影响行车效率，如施工、交通事故、路段检修、迎宾车 队等，这些路况信息的影响可能持续几十分钟、几个小时、几天或者更长的一段 时间，都会造成一定的时间延误，影响行车效率。 7 北京交通人学硕十学位论文最优路径规划中路段权值的确定 2 1 现有路权确定方案 路网权值直接影响了最短路径的搜索结果，近年来，越来越多的交通最短路 径算法和i t s 领域以及其他相关领域的专家学者都充分意识到交通信息对最优 行车路线的影响，并投入很大精力来研究路网权值的问题，己经提出了多种路网 权值的确定方法。对于路网权值的确定，其最终目标只有一个，就是尽可能地充 分利用各种交通信息，模拟真实的道路状况，以便提供实时可靠的交通路况信息。 按照交通信息更新频率的高低，可将交通信息分为静态信息和实时信息两 类，静念交通信息是指相当一段时f u j 内不会改变的交通状况，如交通管制信息、 道路等级、路面宽度等都是静念路况信息；实时信息是指即时路况信息，如在某 一时刻某条道路的堵塞程度如何。无论是静态信息还是实时信息，均可以采取等 价的方法描述路段的权值，例如可以把各种交通信息等价为路段的距离，也可等 价为路段的通行时间。 文献 5 建立了分时动态交通路网模型，采取实际统计数据和交通流预测模 型结合计算得到车辆通过某一路段的通行时间。该方案对时间作离散化处理，将 系统工作时间按照一定的时问分辨率划分为若干时段，认为单个时间内交通状态 稳定、行程时间固定，不同时段的行程时间可能不同。由于交通流是连续变化的， 因此对数据作插值拟合处理，得到反应交通流连续变化趋势的动态通行时间曲 线。此方案存在的不足之处： ( 1 ) 主要针对交通状况随时问变化较大的城市交通网络，如果交通状况随 时间变化不是很明显，则该方案就失去了意义。因为如果交通状况随时间变化不 明显，则各个时间段的车流量相差不大，也就是说交通拥挤状况变化不大，这时 路段的通行时间与路段长度成正比，仅需考虑路段长度作为权值即可，没有必要 研究车辆在不同路段的通行时间； ( 2 ) 车辆流是连续变化的，该方案循环利用一天2 4 小时内的数据，即使将 时间段离散化，对结果拟合也难以保证数据的实时性。 文献 6 设计了最短时间代价函数，其表达式如下： f g o 。，( f ，d ) = a x l o k + b r k + 呶 ( 2 1 ) 其中，k 表示第k 条路径，t 表示路段流量等级，表示道路等级，d 表示路 段长度，口，d ，c 分别表示权值系数，可根据具体情况设置。以几何距离、道路质 量为路阻计算的最短路径属于静念最优路径，没有考虑动态的交通信息，而且此 代价函数仅能反映极其有限的道路属性信息，不能体现变化多端的路况信息，目 前车辆导航系统动态交通分配研究中多采用该类路径，计算结果与真实最短路径 存在较大差异。 文献 7 设计的权值函数为： 北京交通人学硕十学位论文 最优路径规划中路段权值的确定 巩。：j 呜+ ( 以，+ 以，) 2 + 6 t ；允许通行 ( 2 2 ) 9 io 。禁止通行 f 为路段v 的通行时间，利用了交通部门发布的实时交通信息获得的车辆 平 均速度计算得来。叱和嘭为两交叉口的延误时问，取其平均值；函是实时 路况的延误时l 日j ，它代表了所有的其他影响因素。该文献指出，“其他因素产生 的行车时间延误一般难以准确确定，如交通事故，严重的情况会造成塞车，时间 延误达几个小时，轻的只影响行车速度，延误时问可能只有几秒钟。因此，这项 延误与实际情况关系很大，只能根据实际情况来定，在这里该延误时间暂且用所 来表示。 文献 8 对车辆导航系统的路权赋值方案进行了较深入研究，对常用路阻函 数进行了参数标定，得出新的阻抗函数模型。但是文章所采用的数据量较旧，数 据较少，标定的模型准确性不高，不具有通用性。 文献 4 中给出的路权函数 一竿+ 警埘阙帕允许通行 汜3 ， io o ；禁止通行 其中i 是交叉口，v 可是当前到f 的对应路段平均行驶速度，1 ，f d 为从f 到终点 d 的预估行驶速度，t ，为在交叉口i 的延时，g 表示转化成行驶时间的道路等级 信息，为调整系数，丁表示其他的实时路况信息。此函数也未考虑交叉口排队 长度对行使时间的影响。 综上，以往研究的路段权值确定方法中，一类只是考虑静态交通信息，另一 类是基于动态交通信息的路段权值，但在计算路段部分行驶时间时，并没有考虑 交叉口的排队长度，只是用路段长度除以平均速度来获得该路段的行程时间，参 考动态交通分配中路段阻抗的研究成果，为了提高车载导航路径规划的实时性和 有效性，有必要考虑路段排队长度，因为在很多大中型城市中，交叉口排队现象 很明显，排队长度较长，不能忽略。 2 2 考虑交叉口排队长度的路权确定模型 由影响行车效率的因素可知，建立符合实际的路权权值计算公式，必须考虑 各种交通信息的影响，同时兼顾车载导航系统硬件平台的限制。最佳路径的权值 计算： 假设搜索最佳路径的网络矩阵为d t e d t u 】。，则车辆从f 交叉路口行驶到歹 交叉路口的行驶时间，即权值，由车辆在路段i 一_ ，的行驶时问和交叉口的延误 9 北京交通人学硕十学位论文 最优路径规划中路段权值的确定 时间以及交通管制措施等其他因素的影响等束决定。 要事先得到车辆在路段f 寸，的准确的行驶时间是不可能的，因此，只能利 用交通部门发布的实时交通信息获得车辆在该路段的空间平均速度y ，再根据车 辆在此路段的行驶长度估计该行驶时间，车辆的行驶长度为路段长度z ，减去交 叉口的排队长度g 设行驶时间为出则： 织：堑旦 ( 2 4 ) 。 k 交叉路口的延误，路段f 专，的交叉口延误时间设为巩，和出，。由于车辆通 过交叉口是从一个路段进入另一个路段，因此该交叉口的延误时问应近似均分在 两条路段上，而每一路段均有两个路口，所以交叉路口的延误时间应为 = ( d t i + 叱) 2 ( 2 5 ) 对于交通管制措施必须根据具体的措施来区分它们对行车时间的影响。如： 通行权的管制，可分解为允许通行和禁止通行。如果为允许通行，则权值为上述 两项之和；如果为禁止通行，则权值为无穷大。 路段等级也是影响行车效率的一个重要指标，道路等级不同，路面质量不同， 限速就不同，通行效率就不一样。因此，通过给不同级别的道路赋不同的数值， 再加上参数的调整，使之转化成等效的路段通行时间，可以使算法优先选择高等 级的道路，从而提高通行效率。 其他因素产生的行车时间延误一般难以准确确定，如交通事故，严重的情况 会造成塞车，时间延误达几个小时，轻的只影响行车速度，延误时间可能只有几 秒钟。因此，这项延误与实际情况关系很大，只能根据实际情况来定，在这里该 延误时间暂且用出来表示。 综上，最优路径权值为 ：j ( 办一劬) 7 k + ( 以+ 叱) 7 2 + 口g ! f ，+ 出；允许通行 ( 2 6 ) “ l0 0 禁止通行 其中，w , j 表示路段f 专所对应的路段权值，4 ，表示路段长度，g f ，表示交 叉i ：i 排队长度，屹表示路段平均行驶速度，以和西，为节点f ，分别对应的交叉 口延误时间，q ，为转化为道路等级的行驶时间信息，a 为调整系数。出为其他 因素产生的行车时间延误时间。 2 3 本章小结 本章讨论了时间最短最优路径规划中路段权值的确定方法；分析了出行车在 行车过程中影响行车效率的各种因素；通过分析以往车载导航系统路段权值模型 发现，计算路段行程时间时用路段长度代表行驶长度，这不符合大多数路段的实 际情况，因此，我们考虑了交叉口排队长度对路段部分行驶时i b j 的影响，同时兼 1 0 北京交通人学硕十学位论文 最优路径规划中路段权值的确定 顾车辆导航系统的硬件限制，构造了新的权值计算函数。 北京交通人学硕十学位论文 基1 - d i j k s t r a 算法的最优路径规划 3 基于d i j k s t r a 算法的最优路径规划 路径规划足车辆导航领域的一个基本问题，是车辆在行驶中从给定的道路网 中寻找出从起点到目标点之问的理想行驶路线的过程【i0 1 。其原型是图论中的最短 路径问题，随着自身不断的发展，路径问题从建立在图论上的抽象网络上的模型 的算法研究，逐步向现实生活中的实际模型的算法研究进行转变，使得最优路径 算法广泛应用于互联网的寻址计算、智能交通系统( i t s ) 、城市地理信息系统 以及军事地理信息系统中。根据实际应用目的的不同，在最优路径规划中可以采 用的优化标准有很多，如最短行车距离、最少行车时间、最低费用等，无论采用 何种标准，最优路径规划最终都可以归结为在特定道路网中寻找具有最小代价的 最短路径问题，即图论中的最短路径问题。若采用最少行车时f u j 为优化标准，则 求出来的最短路径实际上为最少行车时间路径。对于最短路径问题，最经典的算 法是d i j k s t r a 算法，1 9 5 9 年，由迪杰斯特拉( d i j k s t r a ) 提出的d i j k s t r a 算法是目前 图论中典型的求解最短路径的方法【i l 】。d i j k s t r a 算法建立在抽象的网络拓扑基础 上，把路线抽象为网络中的边，算法能确定网络中从某点到所有其他节点的具有 最小权值总和的路径。如果一个图中所有弧的权非负，贝, l j d i j k s t r a 算法按路径长 度递增的次序来求出从指定顶点到图中其他所有顶点的最短路径。车辆导航系统 最优路径的规划实质都要归结为图论中的最短路径求解问题。 本章将探讨d i j k s t r a 算法在车辆导航系统最优路径规划中的实现与应用。首 先分析d i j s k t r a 算法的基本原理，然后对其时间复杂度进行了分析。 3 1 数字道路网的模型与存储 车载导航系统中的最优路径规划属于图论中的最短路径问题。为说明其数学 描述和求解原理，以下介绍图论中的基本概念。 3 1 1 图的定义和术语 图论是研究与图相关的理论和算法的- i - j 学科，在数据结构、网络设计等方 面有重要的作用。图论中所研究的图并非是指普通意义上的图形，它表示的是定 义在顶点集上的二元关系。从计算机科学的观点来看，图是一种数据结构，它的 定义为【1 2 】： g = ( y ，e ) ( 3 1 ) 其中， v = 1 ，lv d a t a e l e m e n t ) e = ( y ，r ) 1 2 北京交通人学硕十学位论文 基丁d i j k s t r a 算法的最优路径规划 v = 1 ，ly d a t a e l e m e n t e = v r ) v r = l ( x ，y y ) 尸( x ，y ) ) 在图中，基本的数据元素y 称为顶点( v e r t e x ) ，v 是顶点的有限非空集合；v r 是两个顶点之间的关系的集合；p ( x ，y ) 定义了 的意义或信息；若 v r ，则 表示从x 到y 的一条弧，且称x 为弧尾或初始点，称y 为 弧头或终端点，此时的图称为有向图。若 v r 必有 v r ，即职是 对称的，则以无序对( x ，y ) 代替这两个有序对，表示工和y 之i 、日j 的一条边，此时 的图称为无向图。除了上述定义外，其他的一些与图相关的重要术语有： ( 1 ) 相邻接和相关联：对于无向图g = ，若有边( 1 ，1 ，i ) e ，则称顶 点y 和，互为邻接点，即v 和v 相邻接。边 依附于顶点v 和，或者说 y ，) 和顶点1 ，和，相关联。对于有向图g = ( v ，e ) ，如果弧 e ，则称顶 点y 邻接到顶点，顶点1 ，邻接自顶点v 。弧 和顶点v ，相关联。 ( 2 ) 度：在无向图g = ( v ，e ) 中，顶点1 ，的度是和v 相关联的边的数目。在 有向图中，顶点v 的度是指与顶点v 相关联的弧的数目，其中以v 为头的弧的数 目称为v 的入度；以y 为尾的弧的数目称为y 的出度；顶点v 的度是1 ，的入度和出 度之和。 ( 3 ) 路径：在无向图g = ( y ，e ) 中，从顶点1 ，到顶点1 ，的路径是一个顶点序 列y = ( 0 ，v ，k ，。= y - ) ，其中( _ , j - l k ，) e ，1 j m 。如果g 是有向图，则 路径也是有向的，顶点序列应满足 e ，l j m 。第一个顶点和最 后一个顶点相同的路径称为回路或环。序列中顶点不重复出现的路径称为简单路 径。 ( 4 ) 连通：在无向图g 中，如果从顶点，到顶点y 有路径，则称，和y 是连 通的。如果对于图中任意两个顶点，v j ，v ，和都是连通的，则称g 是连通 图。在有向图g 中，从顶点v 到顶点v 有路径存在，则称v 相对于v 是可达的； 如果对于每一对v ，m ，从m 到和从到h 都存在路径，则称和 是连通的。图中的每一对顶点都连通的有向图称为强连通图。 ( 5 ) 子图：设有两个图g = ( v ，e ) 和g t - ( v ，e t ) ，如果v v 且e e ，则 称图g 是图g 的子图。 ( 6 ) 权与网：如果图的边和弧具有与之相关的数，则这种数就称为边或弧 的权。权可用来描述从一个顶点到另一个顶点的距离和耗费。带权的图就称为网， 其中的顶点称为节点。 北京交通人学硕十学位论文 基丁d i j k s t r a 算法的最优路径规划 3 1 2数字道路网的模型 纵横交织、错综复杂的城市交通网主要由众多街道相交、相连而构成，一条 街道可能与若干条街道相交、相连，并且相交、相连的模式复杂。为了避免过多 地考虑街道i 日j 的拓扑关系，以交叉路口作为分析对象，将包含交叉路口的道路拆 分成最基本的路段，一条路段只在其端点处与其他路段相交。在数字地图中，定 义一条道路的交叉点或端点作为道路网的节点，节点有相对的经度、纬度地理坐 标；两节点间的路段定义为网络的边，路段的距离定义为边的权值。根据城市交 通网的特点，有以下合理的分析假设【1 3 】： ( 1 ) 所有的边都是直线。对于弯曲弧度数较大的路段，可在路段上插入一 系列节点，于是该路段由一些弧度较小的路段构成，弧度较小的路段可认为是一 条边。如图5 1 所示，节点l 、2 之间路段的弧度较大，在路段上加入节点3 、4 ， 把原来的路段分割成三个弧度相对较小的路段。 ( 2 ) 边通常是双向可通的，边的权值为正值。 ( 3 ) 网络中有较多的节点和边。 ( 4 ) 和节点相关联的边数为常数，且远小于网络中总的节点数。 节点1 节点3 节点2 图3 1 弧度较大的路段处理 f i g3 1d e a l i n gw i t ht h er o a dw i t hh i g ha r c 3 1 3数字道路网的计算机存储 计算机存储的是矢量化的道路网图，图的存储结构是影响路径规划算法搜索 速度和时间复杂度的一个重要因素。一个简单直观的存储方法是对道路网图中的 每一个节点进行编号，采用邻接表的链式存储结构【