（计算机应用技术专业论文）车辆监控导航系统中最短路径的实时性研究.pdf

莉北师范大学硕士学位论文 摘要 求解最短路径是车辆监控导航系统的主要功能之一，随着全球导航定位技 术的广泛应用人们对求解最短路径问题的要求也闩趋迫切。国内外大量专家 学者对最短路径问题进行过深入研究，提出了多种解决最短路径问题的算法。 采用哪种最短路径算法以及怎样优化算法以提高算法运行效率是本文的研究重 点之一。 车辆监控导航系统中，最短路径的有效实现离不开实时的交通信息系统。 道路交通网中，路况信息是随时间动态变化的，寻求从源点到终点的最短路径 有很高的时限要求。因此，必须建立实时的交通信息系统，为求解最短路径提 供实时、准确的路况信息，使算法求得的最短路径能够真正符合实际的交通状 况，以提高路径分析的实时性和实用性，此为本文的另一研究重点，也是研究 车辆监控导航系统中最短路径的最终目的所在。 本文的创新点：l 设计了一种基于d i j k s t r a 算法的最优路径搜索方法，该 方法提出了新的区域限定模型，并在此限定区域内实现存储结构的优化和含有 启发式信息的搜索策略；2 提出了更加符合交通路网的权值确定方法。 论文首先概述了车辆监控导航系统的组成和原理，对涉及到的关键技术进 行了婀述。详细分析和讨论了最短路径搜索策略和常见的最短路径算法。在深 入研究d i j k s t r a 算法的基础上，针对该算法在应甩中存在的不足，综合区域限 定、存储结构、启发式搜索策略这三方面进行优化，设计了一种基于d i j k s t r a 算法的最优路径搜索方法。其中，区域限定是前提，通过限定区域可以直接减 少不必要的结点参与运算；在限定区域的基础上对存储结构进行优化可以有效 地减少存储空白j ；大量实验表明，应用启发式搜索策略在搜索的路径结点总数 和计算时间方面有明显减少。 在实际的交通路网中各种交通信息对路径搜索有很大影响要得到最优 的出行路线必须综合考虑影响出行效率的众多因素。本文在讨论已有路网权值 河北师范大学硕士学位论文 确定方法的基础上，设计了更加符合实际的权值确定方法。 最后阐述了实时交通信息系统的系统结构，分析了实时信息的采集、处理 与发布方案。 关键字：最短路径，o i j k s t r a 算法。启发式信息，路网权值，实时交通信息 l l 河北师范大学硕，j - 学位论文 a b s t r a c t r o u t eg u i d a n c ei so n eo ft h em o s ti m p o r t a n tf u n c t i o n si nt h ev e h i c l e s m o m t o r i n ga n dn a v i g a t i o ns y s t e m w i t ht h ew i d ea p p l i c a t i o no f # o b a ln a v i g a t i o n a n dl o c a t i o nt e c h n o l o g y ，p e o p l eh a v eg r o w i n gd e m a n d so fs o l v i n gt h es h o r t e s tp a t h p r o b l e m m a n ye x p e r t sd o m e s t i ca n do v e r s e a sh a v es t u d i e do nt h es h o r t e s tp a t h p r o b l e ma n dh a v ep r o p o s e ds e v e r a lk i n d so fm e t h o d so fs o l v i n gt h es h o r t e s tp a t h p r o b l e m w i t hw h i c ha l g o r i t h ma sw e l la sh o wt oo p t i m i z et h ea l g o r i t h mt oi m p r o v e t h ee f f i c i e n c ya r eo n eo f t h ef o c u s e so f t h i sp a p e r i nt h ev e h i c l e sm o n i t o r i n ga n dn a v i g a t i o ns y s t e m ，r e a l i z a t i o no ft h es h o r t e s t p a t hc a nn o tb es e p a r a t e df r o mr e a l - t i m et r a f f i ci n f o r m a t i o ns y s t e m r o a dc o n d i t i o n i sc h a n g i n gc o n s t a n t l yi nt r a f f i cn e t w o r k ，a n di td e m a n d sh i g ht i m el i m i tt of i n dt h e s h o r t e s tp a t hf r o ms o u r o 。t od e s t i n a t i o n s ow em u s td e s i g nr e a l - t i m et r a f f i c i n f o r m a t i o ns y s t e mi no r d e rt op r o v i d er e a l t i m e ，a c c u r a t ea n da c t u a lr o a dc o n d i t i o n f o rt h es h o r t e s tp a t h t h i si sa n o t h e rf o c u so f t h i sp a p e ra n da l s oi st h eu l t i m a t eg o a l o f s t u d y i n gt h es h o r t e s tp a t hi nt h ev e h i c l e sm o n i t o r i n ga n dn a v i g a t i o ns y s t e m t h ei n n o v a t i o n so f t h i sp a p e ra r ea sf o l l o w s ： 1am e t h o da b o u to p t i m a lp a t hs e a r c h i n gb a s e do nd i j k s u aa l g o r i t h mi s d e s i g n e d am o d e lo f r e s t r i c t e ds e a r c h i n ga r e ai sp r o p o s e d ，a n di nt h i sr e s t r i c t e da r e a a l lo p t i m a lm e m o r ys t r u c t u r ea n ds e a r c h i n gs t r a t e g yw i t l lh e u r i s t i ci n f o r m a t i o na l e r e a l i z e d 2aw e i g h td e t e r m i n i n gm o d e lw h i c hi sm o r ei na c c o r dw i t hr o a dn e t w o r ki s p r o p o s e d t h ep a p e rf i r s ts u n u n a r i z e st h ec o m p o s i t i o na n dt h e o r yo ft h ev e h i c l e s m o n i t o r i n ga n dn a v i g a t i o ns y s t e m s e v e r a lk e yt e c h n i c a lt o p i c s a g ee x p l a i n e d s e a r c h i n gs t r a t e g ya n df a m i l i a rs h o r t e s tp a t ha l g o r i t h m sa r ea n a l y z e da n dd i s c u s s e d i nd e t a i l a i m e da tt h ed e f i c i e n c yo f t r a d i t i o n a ld i j k s t r aa l g o r i t h mi nt h ea p p l i c a t i o n ， t h i sp a p e rd e s i g n sak i n do f m e t h o da b o u to p t i m a lp a t hs e a r c h i n gb a s e d0 1 1d i j k s t r a a l g o r i t h m t h i so p t i m a la l g o r i t h ms y n t h e s i z e st h r e ea s p e c t s ：a r e ar e s t r i c t e d ，m e m o r y s t r u c t u r ea n ds e a r c h i n gs t r a t e g yw i t hh e u r i s t i ci n f o r m a t i o n l i m i t i n gt h ea r e ai st h e 1 1 1 塑韭堕型j 大兰堡：! 兰堡丝塞 p r e c o n d i t i o n ，t h r o u g hw h i c h w ec a l ld i r e c t l yr e d u c eu n n e c e s s a r yo p e r a t i o n s ；o nt h e b a s eo fr e s t r i c t e da r e a ，s t o r a g es t r u c t u r ei so p t i m i z e d ，a n di ta l s oc a nr e d u c et h e m e r a o r ys p a c e ；t h et e s ts h o w st h a tt h en u m b e ro fn o d e ss e a r c h e da n dt h et i m es p e n t o nc a l c u l a t i o nh a v ed e c r e a s e do b v i o u s l y i nt h er e a lt r a f f i cn e t w o r k a l lk i n d so fi r a f i i ci n f o r m a t i o nh a v eg r e a t l y i n f l u e n c e dp a t hs e a r c h i n g t h e r e f o r e ，w em u s tc o n s i d e rm a n yf a c t o r ss y n t h e t i c a l l y w h i c hm a yi n f l u e n c er u n n i n ge f f i c i e n c y o nt h eb a s i so fd i s c u s s i n gt h em e t h o do f w e i g h td e t e r m i n i n g ，an e wm e t h o do f w e i g h td e t e r m i n i n g i sd e s i g n e d f i n a l l y ，t h es t r n g t u r eo f r e a l - t i m et r a f f i ci n f o r m a t i o ns y s t e mi sa n a l y z e da sw e l l a st h ec o l l e c t i o n ，p r o c e s sa n dr e l e a s ep r o j e c to f r e a l - t i m ei n f o r m a t i o n k e y w o r d s ：s h o r t e s tp a t h ，d i j k s t r a a l g o r i t h m ，h e u r i s t i ci n f o r m a t i o n ， n e t w o r kw e i g h t ，r e a l t i m et r a f f i ci n f o r m a t i o n i v 学位论文原创性声明 本人所提交的学位论文车辆监控导航系统中最短路径的实时性 研究，是在导师的指导下，独立进行研究工作所取得的原创性成果。 除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已 经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集 体，均已在文中标明。 本声明的法律后果由本人承担。 论文作者( 签名) ：商诱 岬年y , e l 扣日 学位论文原创性确认书 学生j 瞳所提交的学位论文车辆监控导航系统中最短路径的 实时性研究，是在本人的指导下，由其独立进行研究工作所取得的 原创性成果。除文中已经注明引用的内容外，该论文不包含任何其他 个人或集体已经发表或撰写过的研究成果。 河北师范人学硕士学位论文 第一章绪论 网络分析是g i s ( 地理信息系统) 空刚分析的重要组成部分，是依据网络 拓扑关系( 线性实体之刚、线性实体与结点之问、结点与结点之间的连接、连 通关系) 。并通过考察网络元素的空问、属性数据对网络的性能特征进行多方面 的分析计算。网络分析作为g i s 的重要功能，在电子导航、交通旅游、城市规 划以及电力、通讯等各种管网、管线的布局设计中发挥了重要的作用。常规的 网络分析包括路径分析、资源分配、连通分析、流分析、选址分析等。其中， 最短路径问题是网络分析中最基本最关键的问题，以最短路径为主的最优路径 问题一直是计算机科学、运筹学、交通工程学、地理信息科学等学科的一个研 究热点，也是资源分配、路线设计及分析等优化问题的基础。 近年来，随着社会经济的飞速发展和人们生活水平的不断提高，汽车越来 越成为人们不可或缺的交通工具。汽车数量的急剧增加使得城市道路交通日益 复杂，而交通设施的建设远远落后于汽车数量的增加，因此交通堵塞现象十分 严重，交通事故也愈发频繁。将最短路径算法应用于车辆监控导航系统，将会 提高行车效率，有效避免交通堵塞以及交通事故的发生，无疑是解决交通问题 的利器，也是智能交通的具体表现。在交通路网图中，用顶点表示城市，边表 示各城市之间的交通路线，边的权表示交通路线的长度或花费代价。对于这样 的交通网络，我们常常关心：在从a 城市到b 城市有若干条通路的情况下，哪 一条通路的路程最短或所花费的代价最低。这些问题就是在图中求最短路径的 问题。 基于车辆监控导航系统的最短路径研究，需要做以下一系列工作，包括对 最短路径算法的改进及实现、构造能够反映真实路况的路况信息模型、提高交 通信息系统的实时性等等。 国内外大量专家学者对最短路径问题进行过深入研究，提出了多种解决最 短路径问题的算法以及针对不同算法的优化方法，并能通过加入道路的属性信 息、统计车流量随时问的变化规律等方法来提高算法的实用性。然而，路况信 息是随时问而不断变化的，是一个随机的过程，这些统计数据只能从宏观上体 现路况的总体特征，而不能得到实时动态数据进行计算，所以这种研究归根到 底属于静念最短路径的范畴。 塑韭堡蔓占堂堡_ 兰篁堡塞 实时性是车辆监控导航的灵魂，现实生活中交通状况复杂多变，必须研究 实时的交通信息系统，为车辆提供实时的最短路径，实现动态的车辆导航，否 则就失去了导航的意义。g p s ( 全球定位系统) 技术的出现，为实现实时性的车 辆导航提供了技术保障，利用g p s 技术可获取实对的定位数据，近年来已经广 泛地应用于车辆监控导航系统中。 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 最大的消费市场。因美国和其盟国民用商业用户呼吁要求 更高精度的导航定位服务，美国国防部于2 0 0 0 年5 月1 日起取消了g p s 中的 s a 技术( 种干扰措旌) ，此举极大地加速了g p s 技术的民用化。现在可以把 单点定位的水平精度提高到1 5 米；差分定位水平精度提高到5 米( 9 5 时间内) ， 授时误差不大于0 1 秒，授时精度优于0 0 0 0 0 0 1 秒。 卫星导航产业在车辆应用方面的发展基本上有两大类：一类是以日本为代 表的自主导航类，由于日本的特殊环境与需求，政府资源与大财团的资金巧妙 结合以及车辆道路信息系统的实施，大大促进了自主导航产业的发展；另一类 是欧美和中国为代表的监控跟踪类，服务于安全防范、车队管理、物流调度。 近几年来，两大类有合二为一的发展倾向，进一步体现了卫星导航车辆终端的 服务特征，为增值服务奠定了基础。 从系统的通讯方式来看，最早的系统大都采用专业网，实现系统及系统的 营运费用都比较高，对g p s 定位的盲区也要采用专门的软硬件方案来解决。随 着短信平台的推广应用，利用短信息在车载终端和监控中心之恻进行通汛的方 式迅速被采用和推广。目前国内的相关产品，其通讯方式大多采用短消息平台， 2 河北师范大学硕上学位论立 这种短信息服务( s m s ) 使信息传输更加方便快捷，使g p s 系统的组建费用大幅 度降低，营运费用也有了较大幅度的下降。 1 1 1 国外车辆监控导航系统研究现状 目前，车辆导航技术最发达的地区是美国、日本和欧洲地区，其导航技术 的现状代表了本领域研究和应用的发展方向，尤其是r 本导航技术的发展更是 处于领先地位。在日本，由于其城市路网稠密而且布局不合理，改造费用又比 较高，所以对导航系统研究的比较早，并得到了政府和有关部门的支持，再加 上其雄厚的经济和科技实力以及出色的制造技术，使日本在车辆导航装置方面 的研究开发和生产处于世界领先水平。8 0 年代市场上就出现了带有彩色显示器 并以光盘驱动器作为数字地图存储介质的自主导航系统，此后，融入许多诸如 地图匹配、g p s 、声音引导等新技术的各式各样的导航产品应运丽生。目前，日 本的车辆导航系统已经成为极其普通的车载设备。车载设备的年销售量维持在 几百万套，超过6 0 的新车出厂时已安装了车辆导航系统，还形成了一批著名 的导航器生产厂商，如松下、阿尔派、先锋等。为了迸一步提高汽车导航和定 位的应用技术和促进汽车导航系统的发展，日本采用修正式d - g p s 技术，利用 f m 频道进行误差修正，大大提高了汽车的定位精度，可达到1 0 1 4 精度的定位等 级。它再辅以道路交通通信技术及自导式电子地图光盘，其覆盖率已达8 0 的 日本地区。 在欧洲，以德国为代表，法国、英国和荷兰等国紧跟其后。德国已经能够 批量生产与汽车导航设备配套的光盘交通图，由飞利浦、西门子、宝马等公司 开发的车辆导航系统在欧洲已经得到了广泛的应用。 在美国，自从军方宣布开发一部分g p s 时，就开始了民用汽车导航的研究。 1 9 9 5 年时，其研制的城市道路交通管理系统就开始投入使用，为城市道路交通 管理起到了重要的作用。2 0 0 5 年美国汽车导航仪市场规模达到1 5 0 月台。 在亚洲除同本外，韩国和我国的台湾地区在导航技术上的研究和应用也比 较先进。韩国研制的h n s - - 2 0 0 0 卫星导航系统在1 9 9 8 年就投入商业使用，该系 统在c d - - r o m 光碟上储存着韩国的全国公路交通网及服务设施有关资料，可供 驾车者随时查阅。 3 扣i 北师范大学硕上学位论文 1 1 2 国内车辆监控导航系统研究现状 g p s 车辆监控系统在我国的发展主要是从9 0 年代初期开始的，至今有十 几年的时自j ，在1 9 9 4 1 9 9 5 年期日j ，就有上百家公司研究车辆监控导航系统， 但由于市场尚未形成，技术还不完善大多数产品并没有被推广使用。1 9 9 6 1 9 9 8 年期间，在对原有系统改造的同时，新的系统相继出现，并有多个具有一定水 平的集群系统出现。从1 9 9 9 年开始，随着采用g s m ( g l o b a ls y s t e mo fm o b i l e c o m m u n i c a t i o n s ) 短消息业务作为无线通信手段，系统的瓶颈通信问题得 以解决，g p s 车辆监控系统找到了新的出路并得到长足的发展。从2 0 0 4 年开 始，随着g s m 网络的g p r s 功能的逐步成熟与完善，基于g p s g i s g p r s 的车 辆定位监控系统得到了应用。 中国g p s 导航的市场潜力巨大。2 0 0 7 年，全球导航市场产品将达到7 5 0 万 台，其中，日本3 4 0 万台，欧洲2 8 0 万台、美国7 0 万台，中国6 0 万台。2 0 0 7 年到2 0 0 8 年将是中国导航产业市场迅猛成长的时期，当导航产品如同手机一样 携带方便、使用便捷、由奢侈品变为日用消费品时，中国导航产业将迅速发展， 并日趋成熟。此外，随着消费者对导航产品的认知度逐步提升，导航电子地图 产品的不断完善，第三代移动电话技术的普及，导航市场必将进入一个全面开 花的辉煌时代。 1 2 最短路径算法研究背景与现状 最短路径算法是图论中的一个经典问题，它的研究起源于2 0 世纪5 0 年代 末期，至今已有近5 0 年的历史，大约有两千多篇文献讨论此问题。最短路径不 仅仅指一般地理意义上的距离最短，还可以引申到其他的度量，如时间、费用， 线路容量等，以满足不同系统的不同需求。无论是距离最短、时间最快还是费 用最低，它们的核心算法都是最短路径算法。 1 2 1 单源最短路径 最短路径问题可分为单源最短路径和全源最短路径两大类问题，单源最短 路径问题是求图中的一个顶点到其余所有顶点问的最短路径，全源最短路径问 题是求图中所有顶点对之间的最短路径。在实际应用中，单源最短路径问题更 具有普遍意义，它可为全源最短路径问题提供借鉴方案( 可以依次把网络的每 一个顶点作为源点，重复执行单源最短路径算法n 次，即可求得每对顶点之问 4 河北师范丈学硕士学位论文 的最短路径) 。针对不同领域产生了各种单源最短路径算法，比如：d i j k s t r a 算法，动念规划法，神经网络法，遗传算法、优化路径参数的d i j k s t r a 法等。 还有一种基于启发式搜索的a 丰算法，其主要应用于极大规模的网络中，网络中 的结点数量往往达到指数级，但这种情况一般只在计算机网络通讯应用中出现， 而在实际交通路网中不常见。 1 2 2 国内外研究现状 针对不同的网络特征、应用需求及具体的软硬件环境，各种最短路径算法 在空闻复杂度、时间复杂度、易实现性及应用范围等方面各具特色。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 n z 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 eo 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 ) 以 及i k d ( t h eo 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 ) d a 其 中t q q 算法的基础是图增长理论，较适合于计算单源点到其他所有点问的最短 o f 离，后两种算法则是基于o i j k s t r a 的算法，是目前已知理论上最完善的算法， 是多数系统解决最短路径问题采用的理论基础。它更适合于计算两点间的最短 路径问题，目前在交通运输领域有着广泛的应用。 在我国最短路径算法除了应用于计算机网络通讯技术领域之外，主要用于 城市智能交通中车辆监控导航系统以及路径优化系统，其中吉林大学交通学院 i t s 研究实验室、同济大学的i t s 研究中心和清华大学的交通研究所在这方面 取得了一定的研究成果。 1 2 3 研究热点 目前对最短路径算法的研究主要从算法的存储空嘲和计算时间两方面进 行，近年来的研究热点主要有以下几方面： ( 1 ) 限定搜索范围或限定搜索方向以减少计算量，提高系统效率； ( 2 ) 充分利用启发式信息提高搜索速度： ( 3 ) 路网权值的确定方法，使算法更能体现真实的路网信息，以提高系统的 实时性； 5 河北师范丈学硕j ：学位论文 ( 4 ) 实时交通信息系统的研究。 1 2 4 实时交通信息的研究 静态网络中的最短路径问题已经得到了深入的研究，随着智能交通系统、 网络通信等应用领域的快速发展，静态的路径优化方法已经无法满足系统的实 时性要求，迫切需要研究在复杂多变的网络环境中实现系统的实时性。美、欧、 日等发达国家在实施智能交通系统( i t s ) 过程中，始终把道路交通实时动态信 息系统的建设放在十分重要的位置。如日本的车辆信息和通信系统( v e h i c l e i n f o r m a t i o na n dc o m m u n i c a t i o ns y s t e m ，简称v i c s ) ，就是一个十分成功的 i t m s 应用项目。 v i c s 是目前世界上规模较大，实际使用价值较高的道路交通信息系统之一， 是日本一家具有半官方性质的交通信息处理，发布中心。城市道路和高速公路 的道路交通堵塞、驾驶车辆行经道路旅行时间、交通事故、道路施工、车速及 路线限制、停车诱导等交通实时信息通过道路上设置的检测装置分别由警察部 门和高速公路管理部门负责提供。v i c s 将上述收集的信息编辑、处理成为调频 广播、电波信标、光信标等能够发布、便于车载设备接收的交通信息，包括有 文字显示型和以地理信息系统为基础的简易图形型、地图显示型三种可供驾驶 员使用的信息。截止到2 0 0 1 年3 月，v i c s 可向包括东京在内的2 8 个地区6 0 0 多万辆装有车载导航系统的机动车用户提供实时交通信息服务。 在美、欧等发达国家也有类似的交通信息处理中心，但其发布信息的途径 更多的是依靠设置在路边的可变信息情报板( s ) 和互联网、交通电视台等大众 传媒。在欧洲，公共交通运行状况( 包括车站公交车到达显示系统) 、市民出行 信息咨询等也作为交通信息发布的重要内容。 导航电子地图数据的提供、维护与更新对实时交通信息有很大影响，在国 外电子地图已经能精确到门牌号，而且有些交通技术发达的国家已经能够及时 有效地更新导航电子地图。比如，闩本丰田m a p m a s t e r 在2 0 0 4 年1 0 月1 9e 1 丌 幕的“第l l 届i t s 全球会议爱知名古屋2 0 0 4 ”上，首次公开了使用依次接收 车辆行驶状况、搜集道路信息等的“信息车( p r o b e c a r ) ”技术，对新通车道路 进行调查、识别单行线等道路管制情况并能够及时更新车载导航电子地图。1 。 6 河北师范大学硕士学位论文 l - 3 论文的研究内容 车辆监控导航系统中最短路径的实时性研究需要解决两个关键性问题：一 是采用哪种最短路径算法以及怎样优化算法使其更符合实际的路网计算；二是 实时交通信息的采集、传输、发布，以及在算法中的应用。本文主要进行以下 几方面的工作： ( 1 ) 详细分析和讨论了最短路径搜索策略和常见的最短路径算法； ( 2 ) 对d i j k s t r a 算法进行深入分析，针对该算法在应用中存在的不足，设 计了一种基于d i j k s t r a 算法的最优路径搜索方法：提出了新的区域限定模型， 并在此限定区域内实现存储结构的优化和含有启发式信息的搜索策略。其中， 区域限定是路径搜索的前提，它避免了众多无用结点参与计算带来的时间和空 间的浪费；在限定区域的基础上对存储结构进行优化可以有效的减少存储空间： 启发式搜索策略使算法快速趋于目标结点，提高了执行效率。这三方面的优化 是紧密联系，缺一不可的； ( 3 ) 综合三方面的优化于一体进行交通路网试验； ( 4 ) 研究路网权值确定方法，设计了新的路网权值计算模型； ( 5 ) 研究和探讨了实时交通信息系统的系统结构，给出了实时交通信息系统 的采集、传输和发布方案。 1 4 论文的组织结构 第一章绪论，主要介绍了车辆监控导航系统和最短路径算法的国内外研究 现状： 第二章车辆监控导航系统，介绍了车辆监控导航系统的组成原理和关键技 术，包括g p s 技术、无线数据传输技术和g i s 技术： 第三章最短路径算法的研究，阐述了关于最短路径算法的图论基础，讨论 了多种存储结构和搜索策略，详细研究了典型的最短路径算法：胁算法、 d i j k s t r a 算法和f l o y d 算法； 第四章针对传统d i j k s t r a 算法在应用中存在的不足，设计了一种基于 d i j k s t r a 算法的最优路径搜索方法。提出了新的区域限定模型，并在此限定区 域内实现存储结构的优化和含有启发式信息的搜索策略。综合这三方面的优化 于一体进行交通路网试验，试验表明优化方法使程序遍历的结点数目明显减少， 河北师范大学硕士学位论文 使搜索过程快速地趋于目标结点，提高了执行效率。进一步讨论了路网权值的 确定，提出了新的路网权值计算模型； 第血章车辆监控导航系统中实时交通信息系统，围绕实时性设计了实时交 通信息系统的结构框图，给出了实时交通信息系统的采集、传输和发布方案。 8 河北师范大学硕士学位论文 第二章车辆监控导航系统 车辆监控导航系统是在全球卫星定位系统的基础上发展起来的一门新型技 术，是g p s 、g s m 和g i s 集成应用的典型例子，它是将g p s 技术、无线通讯技术、 g i s 技术以及计算机数据处理技术相结合，实现对移动目标的位置、状态的定 位与监控，达到对其进行导航、调度和管理等功能。在该系统中，移动目标的 动态位置( 经度、纬度) 、时间、状态等信息实时地通过无线通信链路传送至监 控中心，而后在以g i s 为平台的电子地图上进行动态显示。g i s 条件下的电子 地图数据库为车辆监控提供了存放和管理监控信息的一个可视化载体。而通信 技术则在6 p s 与g t s 之问建起了一座数据通信的桥梁。 2 1 系统组成及原理 车辆监控导航系统主要包括车载信息处理终端、无线通信数据链路、监控 中一d - - 大部分。图2 一l 是应用g s m 网络的车辆监控导航系统结构。 幽2 1 车辆监控导航系统结构 ( 1 ) 车载信息处理终端：包括单片机、显示单元、6 p s 接收机、g p s 天线、 g s m g p r s 手机模块、报警器( 防盗、超速、抢劫、特殊功能报警等) 。能提供 定位、导航、通话、报警和远程控制等功能。 ( 2 ) 无线通信数据链路：作为监控中心与移动目标进行信息交换的枢纽，是 整个车辆监控导航系统中的重要组成部分，可以选择g s m 或g p r s 的通信方式。 ( 3 ) 中，t l , 数据处理和显示：中心数据处理和显示单元由主监测计算机、数据 库计算机( 用于数据库管理) 、数掘接收控制转换器等组成。其中数掘接收控制 转换器主要用于对接收到的车辆数据进行解码和预处理：数据库计算机用于管 理车辆基本信息和定位信息以及其他相关信息。主监测计算机可直接通过 9 河北师范大学硕上学位论文 t c p i p 套接字埋送命令。数据传送至g s m 网络运营服务中心后，再以短消息形 式发送到指定的车辆，以便接收指定车辆发送的车辆定位和车辆状态数据。 车辆监控导航系统芎弯三! ! 退罂多车载g p s 终端分布在各个移动车辆上， 通过g p s 接收天线接收卫星发出的导航信号，经g p s 接收机解调处理，从中 提取卫星星历，距离和距离变化率、时钟校正、大气校j f 参量等参数解算出载 体所处的经纬度坐标、速度、时问等，并组织成自定义的通信协议格式，迸一 步打包成数据包，再通过车载终端的通信模块，利用g s m 网络，以短消息的形 式将数据包传送到监控中心的局域网服务器上。在监控中心经过处理与计算机 系统上的g i s 电子地图进行匹配，并在地图上动态显示移动目标的正确位置， 使监控中心能清楚、直观、实时地掌握移动目标的动态位置信息，同时把需要 记录的有用信息存储在数据库中以各查询。监控终端可以查询用户的数据库信 息，如车辆信息、驾驶员信息、g i s 地图信息等。还可以对车载终端发出指令， 如信息重传、被盗时关闭车门油门，对车辆进行控制等。 2 2 系统主要功能 ( 1 ) 车载终端的功能 车辆定位：接收g p s 信号，经过处理得到g p s 车载终端的经度、纬度、 海拔高度、时问、车行的速度、方向，对自身进行定位； 数据处理：对有用信息进行采集、打包，组成可以在无线通信网络可以 传输的格式； 接收监控中心指令：配合监控中心的整体调度和管理，接收来自数据服 务中心的一般信息( 如路况信息，天气预报等) ，随时掌握与行车有关的信息； 防盗报警：车载终端通过i o 控制车门和油门的开关，控制车辆不被盗 走。当车辆遇到抢劫、交通事故等紧急状况时，司机可以通过触发报警装置， 自动向监控中心报警： 状态显示和车辆导航：g p s 车载终端显示屏可显示车载的运行状态信息 以及数据服务中心、客户监控中心发给车载终端的各类信息。大屏幕液晶显示 器能显示电子地图，实现对车辆的导航。 ( 2 ) g g m g p r s 网络功能 完成监控中心与车载终端的数据传输，为监控中心反馈车辆的位置和状念 o 河北师范大学硕：l 学位论文 信息，同时接收中心的指挥与调度信息。 ( 3 ) 监控中心功能 车辆实时监控跟踪：车辆信息实时显示，车辆的远程控制、实时调度等 功能： 电子地图服务：为调度指挥人员提供了一系列操作电子地图的功能，包 括一般的地图操作，如：地图放大、缩小、漫游、测距；地图导航( 鹰眼功能) ； 图层控制、位置查询、地图信息查询等； 报警：完成车辆报警提示、报警确认、报警取消、遥控熄火、越界处理 等： 智能路径导航：提供实时交通信息和动态路径规划服务； 数据库管理：完成数据库信息的管理，如：操作人员、车辆等信息管理， 数据的添加、修改、删除、浏览、查找、统计等； 历史轨迹回放：回放当天或者某月某日的历史行驶轨迹。 2 3 车辆监控导航系统关键技术介绍 2 3 1g p s 系统 g p s 是英文n a v i g a t i o ns a t e l li r et i m i n ga n dr a n g i n g g l o b a l p o s i t i o n i n gs y s t e m 的字头缩写词n a v s t a r g p s 的简称。它的含义是：利用 导航卫星进行测时和测距，以构成全球定位系统。它是美国国防部批准的陆海 空三军联合研制而成的新的卫星导航系统，已于1 9 9 4 年进入完全运行状态。该 系统是以卫星为基础的无线电导航定位系统，具有全能性( 陆地、海洋、航天、 航空) 、全球性、全天候、连续性和实时性的导航、定位和定时的功能。能为各 类用户提供精密的三维坐标、速度和时间。近年来，全球卫星定位系统获得了 迅速发展，g p s 定位技术已经渗透到了经济建设和科学技术的许多领域，在发 达国家已被广泛用予军事、经济、科学技术及其他领域，开始形成一种社会化 的服务手段。 全球定位系统的主要用途：( 1 ) 陆地应用，主要包括车辆导航、应急反应、 大气物理观测、地球物理资源勘探、工程测量、变形监测、地壳运动监测、市 政规划控制等；( 2 ) 海洋应用，包括远洋船最佳航程航线测定，船只实时调度与 导航、海洋救援、海洋探宝、水文地质测量以及海洋平台定位、海平面升降监 河北师范大学硕上学位论文 测等；( 3 ) 航空航天应用，包括飞机导航、航空遥感姿态控制、低轨卫星定轨、 导弹制导、航空救援和载人航天器防护探测等。 2 3 1 1g p s 系统组成 g p s 系统包括三部分：空间卫星部分、地面监控部分和用户设备部分。 ( 1 ) 空间卫星部分：由2 7 颗高度约在2 万千米高空的卫星组成，其中有三 颗卫星是备用的。2 4 颗卫星均为近圆形轨道，运行周期约为1 1 小时5 8 分，分 布在6 个轨道面上( 每个轨道面4 颗) ，轨道倾角为5 5 度。卫星的这种分布使 得在全球的任何地方、任何时间都可观测到4 颗以上的卫星，并能保持良好定 位解算精度的几何图形，这就提供了在时间上连续的全球定位导航能力。 g p s 卫星的作用是向广大用户连续不断的发送g p s 导航信号，并用导航电 文报告自己的现时位置以及其他在轨卫星的概略位置；接收地面主控站通过注 入站发送到卫星的调度命令，如：适时地改正运行偏差，或者启用备用时钟等 命令；在飞越注入站上空时，接收由地面站用s 波段发送到卫星的导航电文和 其他相关信息，并通过g p s 信号形成电路适时地发送给广大用户。 ( 2 ) 地面监控部分：太空中卫星上的各种设备是否正常工作，以及卫星是否 一直沿着预定轨道正常运行，都通过地面设备进行监测和控制。地丽监控系统 的另一个重要作用是保持各卫星都处于同一时间标准即g p s 时间系统。这就需 要地面监控站测量出各卫星的时间，求出钟差，然后由地面注入站发送给卫星， 卫星再由导航电文发给用户设备。 监测站的主要任务是给主控站提供卫星的观测数据。每个监测站均用g p s 信号接收机对每颗可见卫星每6 分钟进行一次数据采集。在主控站的遥控下自 动采集定位数据并进行各项改正，每1 5 分钟平滑一次观测数据，依此推算出每 2 分钟间隔的观测值，然后将其发送给主控站。 主控站的任务是收集、处理本站和监测站收到的全部资料，编算出每颗卫 星的星历和g p s 时间系统，将预测的卫星星历、钟差、状态数据以及大气传播 改i f 数据编制成导航电文传送到注入站。主控站还负责纠正卫星的轨道偏离， 必要时调度卫星，让备用卫星取代失效的工作卫星。另外还负责监测整个地面 监测系统的工作，检验注入给卫星的导航电文，监测卫星是否将导航电文发送 给了用户。 1 2 河北师范大学硕士学位论文 注入站的任务是将主控站发来的导航电文注入到相应卫星的存储器。每天 注入三次，每次注入1 4 天的星历。此外，注入站能自动向主控站发射信号，每 分钟报告一次自己的工作状态。 ( 3 ) 用户设备部分：是指g p s 信号接收设备，它是用户与整个g p s 系统的接 口。g p s 卫星发送的导航定位信号，是一种可供无数用户共享的信息资源。对 于陆地，海洋和空间的广大用户，只要拥有能够接收、跟踪、变换和测量g p s 信号的接收设备，就能够接收多颗卫星的信号来算出自身的位置，在任何时候 利用它进行导航定位测量。 完整的g p s 用户接收设备由g p s 信号接收机硬件、机内软件以及g p s 数据 处理软件包构成。g p s 接收机的结构分为天线单元和接收单元两大部分。 2 3 1 2g p s 定位原理 g p s 系统采用“时间同步、单程测距”的原理来实现定位、简单地说就是 用户同时向已知其位置的3 个导航卫星分别进行距离测量，然后再以该卫星为 球心，以所测得的距离为半径，在空间画出3 个球面，则3 个球面的相交点， 就是用户的所在位置。所谓“时间同步”是指卫星上的时钟与用户设备内的时 钟是精确同步的( 譬如说校准到两者之间几万年才差1 秒钟) ：而“单程测距” 则是指从导航卫星上发出的无线电测距信号在传播到用户设备的这一单向行程 中，就可以把它们之间的距离测量出来。 如果卫星钟和用户钟精确同步，那么卫星和用户间的距离是r = f + c ( c 为 光速) ，如果卫星钟和用户钟不能精确同步，则存在钟差国，此时测的距离是伪 距p r = r + 国 c 。实际中，测的距离为伪距豫，对于第i ( i = 1 , 2 ，3 ，4 ) 个卫星 “，咒，毛) ， 伪 距 方 程 为 ； 飓= r i + 国+ c ，其中 r = ( - x ) 2 + ( 咒- y ) 2 + ( 一z ) 2 ，此时的未知数为x ，y ，z 及痨，所以只 需要4 个方程就可解。g p s 卫星组网之所以采用2 4 颗卫星的配置方案，就是为 了保证位于世界任一地点的用户，都可以随时接收到至少4 个导航卫星的信号， 其中3 个卫星的信号来测距定位，第4 个卫星的信号就是用柬计算用户时钟的 误差的。 由于卫星运行轨道、卫星时钟存在误差，大气对流层、电离层对信号的影 3 河北师范大学硕士学位论文 响，以及人为的s a 保护政簧，