（通信与信息系统专业论文）智能车辆导航系统及带限条件下最优路径算法的研究和实现.pdf

摘要 摘要 路线优化子系统是车辆导航系统研究的核心内容，它通过接收交通信息服务 子系统发布的动态交通信息，结合车辆定位子系统所确定的车辆在路网中所处的 位置，向出行者提供符合最优目标的路线行驶方案，良达到安全、迅速、舒适和 经济的出行目的。 论文对最优路径规划算法进行了深入地研究和描述。在分橱了各种常用算法 的时间复杂度和空间复杂度的基础上，采用前向关联边的邻接表存储结构和直线 启发实现了对d i k s l 终算法和蚁群算法的优化，理论分析和实际运行的结果表明， 这些改进大大提高了算法的计算速度，有效的减小了存储空间。然后，对有必经节 点序列、避开节点序列及节点权重等限制条件下的最优路径搜索问题，以西安市 的典型路网为研究对象进行了测试，结果证明，带限制条件下的最优路径搜索算 法能够规划出符合用户要求的最优路径。 关键词：智能车辆导航系统数字电子地图路网模型路线规戈j j 最优路径 a b s t r a c r 3 a b s t r a c t i ni n t e l l i g e n tv e h i c l en a v i g a t i o ns y s t e m ( i v n s ) ，t h er o u t ep l a n n i n gm o d u l e ( r p m ) i sa ni m p o r t a n ta n dc r i t i c a lc o m p o n e n t s ，w h i c hr e c e i v e sd y n a m i ct r a f f i c i n f o r m a t i o nv i at r a f f i ci n f o r m a t i o ns e r v i c ec e n t e r , a n da l s oa c q u i r e st h el o c a t i o no f t h ev e h i c l ev i ap o s i t i o n i n gm o d u l e w i t ht h e s ei n f o r m a t i o n ，r p mp l a n sa no p t i m a l r o u t ef o rt h et r a v e l e r sw h i c hm a k e st h et r a v e ls a f e r , l e s st i m ec o n s u m i n g , m o r e c o m f o r t a b l e ，a n dm o r ee c o n o m i c t h eo p t i m a lr o u t ep l a n n i n gt h e o r ya n dt e c h n o l o g yi s o b t a i n e da l li n - d e p t h r e s e a r c ha n dd e s c r i p t i o ni n t h i sp a p e r b a s e d o nt h ea n a l y s i so ft h et e m p o r a l c o m p l i c a c ya n ds p a t i a lc o m p l i c a c yo ft h ec o m m o n l y u s e da l g o r i t h m s ，t h ew r i t e ra d o p t s f o r w a r d p o i n t e da r c sm e t h o d s ，w h i c hi sak i n do fa d j a c e n c yl i s t ，a st h ed a t as t r u c t u r e f o rd i j k s t r aa n da n tc o l o n ya l g o r i t h m sa n da d d st h eb e e l i n e - h e r i s t i c d i r e c t i o n i n f o r m a t i o nt ot h e m 。t h e o r e t i c a la n a l y s i sa n dp r a c t i c a li m p l e m e n t a t i o np r o v e t h a tt h e s e a l g o r i t h m si m p r o v eg r e a t l yt h ec o m p u t a t i o n a le f f i c i e n c ya n dd e c r e a s ee f f e c t i v e l yt h e s t o r a g es p a c e 。a f t e r w a r d s ，t h ew r i t e rc o n c e n t r a t e do nc o n s i d e r i n gt h eo p t i m a lr o u t e s e a r c h i n gu n d e rc o n s t r a i n tc o n d i t i o n s ，s u c ha st h en o d a ls e q u e n c eo fn e c e s s a r yo r a v o i d e d ，a n dt h en o d a lw e i g h t 。t h i sp a p e rm a k e st e s t si n at y p i c a lr o a dn e t w o r ki n x i a n t h et e s t sp r o v et h a tt h ea l g o r i t h m sc a np r o v i d ea no p t i m a lr o u t er e q u i r e db y u s e ru n d e rv a r i o u sp r o h i b i t i o n sc o n d i t i o n s 。 k e y w o r d s ：i n t e l l i g e n tv e h i c l en a v i g a t i o n r o a dn e t w o r km o d e l r o m e s y s t e m ( i v n s ) e l e c t r o n i cd i g i t a lm a p p l a n n i n go p t i m a lr o u t e 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中 不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学 或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：煎遗壹 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。 ( 保密的论文在解密后遵守此规定) 本人签名：邀益丛 导师签名：主亟 日期竺! ：兰：里 第一章绪论 第一章绪论弟一早三百了匕 1 1 智能交通系统( i t s ) 的发展概况 i t s ( i n t e l l i g e n tt r a n s p o r t a t i o ns y s t e m 卜由日本道路交通车辆智能化推进协 会( v e h i c l e ，r o a da n dt r a f f i ci n t e l l i g e n c es o c i e t y , v e r t i s ) 于1 9 9 4 年筹办在法国巴黎 召开的第一次智能运输系统世界大会时正式提出，从此交通规划和交通控制领域 的研究都统称为智能交通系统的研究。 交通是国家的经济命脉，智能交通系统的产生和发展是经济发展、社会进步 的必然产物和需要： 交通阻塞问题现代城市规模不断扩大，城市居民的生活更加依赖于先 进的交通工具，从而导致城市内汽车数量急剧增长，城市交通阻塞问题越来越严 重。不管是发展中国家还是发达国家，交通问题都是令人困扰的严重问题。 能源浪费问题为适应交通运输问题的快速增长，各大城市不断的加修 道路、增加车辆数量，这是解决交通运输需求日益增长问题的最直接、最简单的 方法，但是土地资源和石油资源r 益紧张是我们必须要重视的事实，因此发展节 约型交通系统是解决能源浪费问题的唯一办法。 环境污染问题城市车辆数量的增多，大量的汽车尾气严重污染环境， 给城市居民的健康带来了极大的威胁。 上述种种问题严重制约了城市交通的运作效率，也限制了城市经济的快速发 展。智能交通系统作为先进的信息技术、数据通信传输技术、电子控制技术以及 计算机处理技术等的有效整合，能够建立起一种在大范围内全方位发挥作用的， 使人、车、路密切配合、和谐统一的，实时、准确、高效的运输综合管理体系， 它是解决交通拥挤、能源紧张、环境污染的最有效的方法，为此智能交通系统引 起了世界各国的重视。在2 1 世纪，智能交通系统将成为现代化地面交通运输体系 的模式和发展方向，是交通运输进入信息时代的重要标志。 1 1 1 国外的发展概况 美国i t s 的前身是智能车辆公路系统( i n t e l l i g e n tv e h i c l ea n dh i g h w a ys y s t e m ， i v h s ) ，从1 9 91 年的综合地面运输效率方案( t l l ei n t e r m o d e ls u r f a c et r a n s p o r t a t i o n e f f i c i e n c y a c t ，i s t e a ，又称“冰茶法案 ) 至i j l 9 9 8 年的面向2 1 世纪运输权益法 案( n a t i o n a le c o n o m i cc r o s s r o a dt r a n s p o r t a t i o ne f f i c i e n c ya c t ，n e x t e a ，又称“续 茶法案) 【，美国i t s 由i s t e a 实施期间的研究开发为主转变为n e x t e a 实施期间 2 智能车辆导航系统及带限条件下最优路径算法的研究和实现 的i t s 基础设施实施和集成，尤其是i t s 集成项目、关键标准的开发、i t s 框架的一 致性、i t s 标准的一致性。2 0 0 2 年，美国智能交通协会组织制定了美国十年i t s 项目计划( n a t i o n a li t sp r o g r a mp l a n ：a t e n y e a rv i s i o n ) 【2 l ，该计划展望了i t s 的发展蓝图、制定了美国i t s 的确切目标。美国依靠雄厚的经济实力和有效的推动 机制，以n e x t e a $ t 定的四大项目领域( 城市i t s 基础设施、乡村i t s 基础设施【3 j 、商 用车辆i t s 基础设施、智能车辆行动计划) 为发展目标，通过国家的统一规划和充 分的资金投入，推动了美国i t s 的迅速发展。其中，商用车辆i t s 基础设施实施的 重点在于商用车辆信息系统和网络( c o m m e r c i a lv e h i c l ei n f o r m a t i o ns y s t e m sa n d n e t w o r k s ，简称c v i s n ) 的实施，目前美国大部分州已经完成此目标。受“9 1 1 事件的影响，美国i t s 今后建设趋势之一就是研究i t s 在美国安全体系中维护地面 交通安全作用，重点集中在安全防御、用户服务、系统性能和交通安全管理方面1 4 j 。 欧盟在推动和导向欧洲i t s 协调实施中具有不可替代的作用，2 0 0 1 年9 月欧盟 制定了 2 0 0 1 - 2 0 0 6 各年指示性计划( 简称m i p ) 来加大实现跨欧交通网络的投资 力度1 5 j ，道路交通i t s 和大型基础设施项目、空中交通管理、伽l 利略卫星导航定位 系统计划( g a l i l e op r o g r a m m e ) 为其优先投资部分，其中的t e m p o ( t r a n s e u r o p e a n i n t e l l i g e n tt r a n s p o r ts y s t e m sp r o j e c t s ) 计划明确指出在2 0 0 1 2 0 0 6 年间欧盟将投入 1 9 2 亿欧元来资助“欧洲一区域 实施项目，这些资金的8 8 投入到道路交通监控 基础设施、交通控制中心、交通管理和控制、交通信息服务；2 0 0 2 年，伽利略计 划由欧盟1 5 国交通部长会议正式启动，其第一颗试验卫星g i o v e - a 于2 0 0 5 年底发 射成功，中国成为参与此计划的第一个非欧盟成员国，目前该计划正如期进行， 预计2 0 0 8 年北京奥运会投入使用。协调一致的欧洲i t s 系统是欧盟及其各成员国积 极研究和建设的方向，日前，正在全面应用开发远程信息处理技术( t e l e m a t i c ) ，并 计划在全欧洲建立专门交通( 以道路交通为主) 无线数据通信网，i t s 的主要功能和 交通管理、导航和电子收费等都围绕t e l e m a t i c 技术及全欧洲无线数据通信网来实 现。 日本在四省一厅( 即警察厅、通产省、运输省、邮政省、建设省) 联合推动 i t s 研发活动后，一直在加速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 l c s ) 、电子收费系统( e l e c t r o n i ct o l l c o l l e c t i o n ，e t c ) 的应用，目前f v l c s 系统和e t c 系统已进入国家范围内实施阶段并迅 速扩展【6 j 。日本注重i t s 诱导设施建设，建设省组织以丰田公司为首的2 5 家公司联 合研发自动公路系统( a u t o m a t e dh i g h w a ys y s t e m s a h s ) 7 l 。同本定义其a h s 系统支 持7 项服务： 防止与前方障碍物碰撞： 防止弯道处事故； 防止车道偏离； 第一章绪论 3 防止交叉口碰撞； 防止右转弯碰撞： 防止与过人行道的行人的碰撞； 提供保持车距等服务的道路路况信息。 至今为止，日本企业已经实现了高速公路驾驶辅助系统、减轻追尾的制动系 统、智能电子导航系统等多项先进安全系统的实用化，并在防碰撞领域取得了实 质性的进展，先进的自动公路系统( a h s ) 将进一步实验演示并朝着实用阶段迈 进。 1 1 2 我国智能交通的发展状况 近年来，随着交通问题的日益突出，我国政府越来越高度重视i t s 建设，国家 已经将i t s 作为未来交通建设与发展的优先领域予以重点支持，并在国民经济和 社会发展“十五 计划纲要中明确提出“加快智能型交通的发展 。2 0 0 0 年2 月， 国家成立了全国智能运输系统协调指导小组及办公室来具体负责i t s 项目开发应 用的组织协调工作。2 0 0 3 年9 月，国家标准化管理委员会批准正式成立全国智能运 输系统标准化技术委员会，标志着我国智能运输系统标准化工作进入了新的阶段， 向管理科学化、市场规范化迈出了坚实的一步。2 0 0 5 年，由国家智能交通系统工 程技术研究中心修订完成的中国i t s 体系框架( 第二版) 1 8 l ，将中国i t s 体系框 架分为用户服务、逻辑框架、物理框架和应用系统四部分。 用户服务就是从i t s 用户主体的角度，根据用户需求，确定系统应当为其 提供什么服务。用户服务分为三个层次：服务领域( 9 个) 、服务( 4 7 个) 、子服务 ( 1 7 9 个) 。 逻辑框架就是从系统设计的角度，为提供上述用户服务，i t s 应实现什么 功能，以及如何组织这些功能间的逻辑关系，分为功能领域( 1 0 个) 、功能( 5 7 个) 、 子功能( 1 0 1 个) 、过程( 4 0 6 个) 、数据流图( 1 6 1 张) 。功能域与服务领域相对应， 功能大致与服务相对应，但功能与服务之间不是一一对应的，功能应当是服务或 服务的组合。功能还可以细分为不同的层次，功能不可再细分时，即称为过程。 物理框架就是从系统实施的角度，将逻辑框架中的功能实体化、模型化， 将相近的逻辑功能组合，归结成直观的物理系统、子系统等实体，分为系统( 1 0 个) ：子系统( 3 8 个) 、系统模块( 1 5 0 个) 、物理框架流图( 5 1 张) 。系统与功能域 大致对应，子系统与功能大致对应，但它们之间并非一一对应的关系，必须有一 个重新组合的过程。 应用系统：目前共提出了5 8 个应用系统。 为了进一步推动i t s 在中国的发展，加速i t s 的工程化应用和产业化进程， 4 智能车辆导航系统及带限条件下最优路径算法的研究和实现 “十五 期间，科技部在“十五 国家科技攻关重大专项中安排了“智能交通系 统关键技术开发和示范工程”项引9 1 ，该项目以中心城市和高速公路相关应用项 目为龙头，在城市智能化交通管理、公共交通系统、交通信息服务、跨省市高速 公路联网收费、高速公路智能化管理以及智能交通系统的产业化和基础性工作等 方面开展科技攻关和应用示范，截止2 0 0 6 年，部分研究项目己通过国家验收。另 一方面，设立试点城市，根据各试点城市的需求和特点安排不同的示范内容，进 入实际开发和建设阶段，如北京进行公共交通区域运营组织与调度系统示范，上 海进行快速道路交通管理系统示范等。 2 0 0 6 年，新颁布的国家、交通行业标准1 1 0 】，规定了道路交通信息采集、智能 运输系统、电子收费、道路交通信号灯设置、系统框架模型等方面的内容。日益 完善的i t s 体系框架及行业标准、为我国i t s 建设规范、健康、可持续的发展提供 了有利条件。 1 2 智能交通系统的研究内容 由以上世界各国及我国智能交通系统发展概况的叙述中，可以把i t s 的研究内 容概括为以下五类【1 l l ： 先进的交通管理系统 该系统依靠先进的传感器技术、计算机技术、信息技术全面掌握和分析道路 网上详尽的、实时的道路交通信息，预测将要发生的交通信息和事件等情报，在 监控中心进行加工处理，来用于交通的控制、诱导和管理，并及时向各类道路使 用者发送诱导信息，从而达到有效地管理交通，实现动态交通分配，减少交通阻 塞等目的。 智能车辆信息服务系统 该系统给出车辆的地理定位，针对用户需求提供信息服务，包括路线引导服 务、旅行者信息服务、出行信息服务、驾驶员信息服务等。利用智能车辆信息服 务系统，驾驶员可以通过车载路径诱导系统，在与控制中心的双向信息传递中使 自己始终行驶在最短路上，从而缩短旅行时间、降低燃料消耗和减少废气排放， 使交通拥挤状况得到缓解。 智能交通运输管理系统 该系统充分利用智能交通系统其它服务功能所提供的信息( 如交通路况信息) 以及运输企业的有关信息，进行合理调度和跟踪指挥，使运输企业发挥出最大效 益。包括商用车辆运营系统、郊区运输系统、自动调度系统、公共交通运营系统 盘蟹 1 to 第一章绪论 5 交通安全保障系统 该系统是对交通运行基本的和必要的支撑，保证交通正常运行时驾驶人员的 安全与舒适以及发生交通异常时进行有效的援助。包括紧急车辆的支援、事故报 警、对行人的帮助、行车安全警报服务、纵向横向防撞、自动驾驶等。 电子收费系统 该系统研究高速公路、收费站等站点的先进收费方式。其保证通行费收取的 同时，通过采用不停车收费的收费方式，减少甚至完全消除收费过程对交通产生 的阻碍。 1 3 现代车辆导航系统 现代车辆导航系统作为智能交通系统的核心部分，在全世界范围内得到了飞 速的发展。许多发达国家如美国、德国、日本都把它列入国家研究计划，投入了 大量的人力、物力和财力进行研究、试验和开发。车辆导航系统发展过程中的标 志性系统如下表所示1 1 2 1 1 1 3 j ： 表1 1 车辆导航系统发展概况 美国 自治导航系统n a v i g a t o r 数字地图数据库，地图显示 欧洲 自治导航系统( c a r i n 、e v a ) 第一个将光驱作为地图存储介质， 八 提供图象显示及合成声音输出 十 日本路车间通信系统 带有彩色显示监视器，并以光驱作 年 ( r o a d a u t o m o b i l e 为数字地图存储介质 代 c o m m u n i c a t i o n s y s t e m ，r a c s ) 1 9 9 4 年美国自治导航系统g u i d e s t a r加入g p s 接收机 九 十 1 9 9 6 年日本 车辆信息通信系统( v i c s ) 发布实时交通信息，动态引导 年 中国，“播调频副载波车辆导航系利用调频副载波传送筹分g p s 信 代 以 统号，供午载接收机修止自身位置实 后 现定位 研究中美国 汽车与道路设施的集成获取实时交通信息，动态路径规划 ( v e h i c l e i n f r a s t r u c t u r e 与诱导 i n t e g r a t i o n ，v i i ) 日本 自动公路系统( p a - i s ) 安全的智能导航系统 由上表可以看出，按照所依据路网信息种类及其路线选择和诱导方法的不同， 车辆导航系统可以分为两种类型： 静态路径导航系统采用车载的全球卫星定位系统( g p s ) 装置来获取 车辆的行驶位置，然后通过与预先描绘好的电子地图数据库实行地图匹配，得出 6 智能车辆导航系统及带限条件下最优路径算法的研究和实现 车辆在路网结构中的位置，从而给出车辆到达目的地的行驶路径以及到达相应路 段后的路径选择。 动态路径导航系统在静态路径诱导的基础上加入了道路网的实时交 通信息( 交通拥挤情况、行程时间、交通事故、临时交通管制以及气象信息等) ， 作为路径选择的依据进行导航。动态路径导航一般采取的是中心式导航系统，即 由交通控制中心向车辆发出实时交通信息来进行路径引导。 1 4 现有的车辆导航软件产品 车辆导航系统各功能模块的实现，除了需要先进的硬件设施作为基础外，还 需要强大的软件产品给予支持。在g p s 导航软件领域，有很多品牌和厂商，国外的 代表有m a p k i n g 、p a p a g o 、t o m t o m 、m i c r o s o f t 等，国内有名的有北京灵图天行者、 城际通、凯立德、诺基亚r o u t e 6 6 等。在此，我们介绍国内两个有代表性的导航软 件：天行者系列( 天行者3 5 、天行者4 、天行者5 ) 和城际通系列( 城际通易达、 锐思、旺达、坤达等) 。 ( 1 ) 灵图天行者4 灵图天行者4 是一套安装在汽车电脑内的自导航软件，它以大比例尺的城市导 航地图为展示平台，内含丰富的灵图天行者的点位信息查询，根据用户不同需求 智能的设计出多种最佳行车路线，并提供实时的语音提示导航功能。 主要功能特点： 路径规划功能 最短路线、最快路线、不走高速路线，根据用户具体需要可以自由设定，系 统通过多种路线算法规划出不同路线引导用户到需要的目的地；智能的路线纠错 能力，能够及时调整新路线。 全国高精度定位导航地图 全国各大中城市地图，跨城际、动态图幅拼接、无缝地图漫游，快速查找信 息并全国导航，9 b 级别的道路网，包含完备的交通规则信息。 道路行车智能显示，精确路口距离，每个路口放大提示 形象生动的路口放大图( 精确度达2 5 米) 可以方便直观地提前告诉驾驶者该 行车的方向和路段信息，对各种需要转弯或者出口、入口、桥梁等都有箭头标出， 一目了然。 兴趣点详细信息查询 丰富的信息点方便用户在陌生的地区查找到各种类型的兴趣点，如宾馆、饭 店、银行、小到w c 以及a t m 取款机等。 第一章绪论 7 自动的轨迹记录功能，方便用户对所走路线的记录 用户可以通过路线的轨迹把走过的路线直观的在地图上显示出来，并且可以 对轨迹进行修改，如对轨迹进行换色，编辑轨迹的名称等，不同用户可以对轨迹 进行共享。 智能语音随行，语音提示播报路段路名 稳定的长时间语音导航，语音播报分录音播报、文本语音( t e x tt os p e e c h ， t t s ) 播报、混音播报，根据用户自己的习惯和需要可以自己设定；另外对语音播 报的声音的大小可以随意调节：用户还可以根据自己要求设定语音提示的频度： 低频、中频、高频。 目的地履历、地址簿、路线履历，方便您对保存的信息点和历史路线的查 找 用户每设定一个目的地，天行者系统都会自动把所设的目的地自动保存到目 的地履历罩面，还可以把经常去的或者比较感兴趣的信息点添加到地址簿里面， 跑了很多路，如果用户想了解一下跑过路的信息，可以在路线履历里面清晰的看 到。 产品优点：地图细致，信息咨询功能强大 产品缺点：地图更新慢、路径优化不能考虑具体的交通信息( 如道路限速、 交叉口延误等) ( 2 ) 城际通旺达 城际通旺达是北京城际高科信息技术有限公司研制出品的一系列汽车导航类 产品之一。 主要功能特点： 全国范围内城市及乡村地图浏览查询； 全国范围内任意两地之间的引路导航，系统对主干路快速车道有速度概念、 对于交叉路口有红绿灯的概念、路线规划最大限度的贴切用户的要求，可以按推 荐路线、多走高速、最短路径等不同方式进行路径规划 立交桥、高速出入口、环岛及复杂交叉路自动放大指示，地图精度为1 0 0 米； 专业g p s 功能，在没有公路的地方，如草原、沙漠、戈壁定位导航，按照已 存轨迹直接引导返航； 行车途中随时知晓当前所在位置( 包括经度、纬度、高度、剩余里程、剩余 时问、所在省份、所在地市、所在区县) ； t i s i n 时语音提示，导航过程中稳定的提示准确的语音指令。 产品优点：非常优秀的路径规划和r r s 即时语音提示功能。 产品缺点：软件运行效率低，速度很慢，用户操作界面复杂。 8 智能车辆导航系统及带限条件下最优路径算法的研究和实现 1 5 论文主要研究内容及章节安排 车辆导航系统是智能交通系统研究中的重点部分，对以驾驶员为主的交通用 户来 兑，i t s 的作用集中体现在它的集成信息服务功能，即道路信息、实时交通信 息、出行路线选择、动态路线引导、旅游信息查询等，所有这些功能的实现都需 要车辆导航系统直接完成或提供支持，因此车辆导航系统的研究成为智能交通系 统的集中体现。 本论文以现有车辆导航系统的薄弱环节路线优化子系统为核心，重点研 究适于车辆导航的各种路线优化算法，以及作为其基础的路网表达方法与存储结 构、道路权重的标定方法等。 具体工作体现在以下几方面： 国内外智能交通系统和车辆导航系统的研究现状； 现有车辆导航产品的功能和特点； 智能导航系统的组成部分及各部分的功能； 交通路网中的空间数据和属性数据的表达方法和存储方式； 以距离最短为最优目标，带限制条件下( 路段单行限制、必经节点、避开节 点等) 最优路径搜索算法的研究； 以时间最短为最优目标，交叉口延误带来的节点权重问题的路径优化算法的 研究。 论文以概括总结、重点介绍、逐层递进的方法，向读者描述了智能交通系统 涵盖的广泛技术研究领域、详细介绍了作者课题研究的关键技术。整个论文的章 节安排如下： 第一章为绪论。主要介绍智能交通系统的研究背景、研究意义、国内外的发 展概况及智能交通系统中重点研究领域车辆导航系统的发展概况、分类、系 统组成等；最后对现有的车辆导航类软件产品进行了简单的概括，并对其中两款 有代表性的导航软件进行了详细的功能介绍及特点分析。 第二章为智能车辆导航系统的关键技术。作者以智能车辆导航系统的组成部 分为基础，对各部分的功能和作用进行了概括性的介绍；以智能车辆导航系统的 系统框图为核心，对与课题研究相关的几个关键技术进行了详细地介绍：g p s 系 统( 组成、特点、用途) ；电子地图的组织结构、表示方法( 图层、图元) 、电子 地图的操作：最后，对课题研究的系统给出其组成框图，以其为中心，介绍了 m a p x 控件的使用和v b 环境下集成m a p x 控件开发车辆导航系统的过程。 第三章为智能车辆导航系统中路线优化算法的研究与实现。首先根据课题研 究的智能车辆导航系统的实际要求，确定路径优化算法研究所依赖的前提优 化目标；在对经典最短路径算法进行介绍和分析后，总结了路径规划算法的两个 第一章绪论 9 优化方向，并在此前提下详细描述了直线优化d i j k s t r a 和启发式蚁群算法；最后 对实际导航系统中带限制条件的路径规划算法进行了研究，并给出了实现方法及 路径规划结果。 第四章为论文工作总结及学习体会，研究工作的进一步展望。 论文重点为第二章和第三章，第二章是第三章的前提与基础；全文力求条理 清晰、描述清楚、突出重点。 第二章智能车辆导航系统的关键技术 第二章智能车辆导航系统的关键技术 2 1 智能车辆导航系统的组成 智能车辆导航系统( i n t e l l i g e n tv e h i c l en a v i g a t i o ns y s t e m ，i v n s ) 诞生于2 0 世 纪8 0 年代，它是智能交通系统( i t s ) 的中心部件，是其他各种功能应用的基础， 因此有极大的应用价值，在全世界范围内得到了广泛的关注。早期的车辆导航系 统，采用磁罗盘测试仪、环状感性天线、航位推算等技术进行车辆的定位，由于 定位精度不高、不能实现实时定位、定位地理范围有限等原因，这类系统没有得 到很好的发展。9 0 年代初期，由于美国全球卫星定位系统( g l o b a lp o s i t i o n i n g s y s t e m ，g p s ) 的研制成功，给智能车辆导航系统的研究注入了新的活力，随着g p s 系统民用领域的开放，以g p s 为定位基础的车辆导航系统显示出了强大的生命力 1 1 4 - 1 6 。经过交通、电子、计算机、通信等相关领域研究机构、企业单位、高等院 校人士的不懈努力，智能车辆导航系统已经形成了功能完备、分工明确、紧密联 系的六大功能模块，如图2 1 。 图2 1 车辆导航系统通用框图 路网数据库是现代车辆导航系统必不可少的组成部分，它包含预先定义好 存储格式的数字地图信息和实时的交通路况信息，为系统提供诸如地理特征、道 路等级、交通规则、兴趣点信息等多种重要信息。为了方便车辆导航功能的设计 和实现，数字地图数据库采用矢量编码方法，其中路网的组织和处理方法是数字 1 2 智能车辆导航系统及带限条件下最优路径算法的研究和实现 地图数据库设计的重点和难点。路网数据库是整个车辆导航系统的基础。 g p s 车辆定位模块和地图匹配模块是整个系统工作的基础，它的主要功能 是：实时的接收g p s 信号，并运用地图匹配技术，将车辆定位模块输出的轨迹与数 字地图中的路网信息联系起来，通过模式识别过程确定车辆最可能的行驶路段以 及车辆在该路段最大可能的准确位置，以使系统能够正确辨别车辆当前的行驶路 段和正在接近的交叉路口，从而为路线引导提供可靠依据。 路线规划是实现导航功能的前提，它的主要功能是：在己知路网上根据选 定的目标、数字地图数据库中的路网信息及无线通信网络接收到的实时交通信息， 帮助驾驶员在行驶前或行驶中选择路线。 路线引导模块则是将路径规划模块输出的最优路径转化为驾驶员能够识 别的信息，实时的指挥驾驶员沿着预定路线行驶从而顺利达到目的地的过程。该 模块根据车辆当前位置、走向及行驶的道路信息，产生转弯等行驶指令，并且适 时地以图文或者语音的方式提供给驾驶员。 无线通信模块进一步改进系统的性能和增加系统的功能，通过无线通信网 络，车载系统和交通管理系统之间能够互相交换实时交通信息，从而促使车载系 统和道路网络的工作更加安全和有效。 人机界面模块是车辆导航系统必不可少的部分，它提供用户与导航设备的 交互，地图与车辆位置显示、路线规划的结果、路线引导的实时进行和其它各种 不同要求都必须通过人机接口传送到计算机，再反馈给用户。 2 2 1g p s 的组成 2 2g p s 概述 全球卫星定位系统( g l o b a lp o s i t i o n i n gs y s t e m ，g p s ) 是2 0 世纪航天史上最成功、 最有意义的工程之一，它是美国国防部耗资3 0 0 多亿美元建立的第二代卫星导航系 统。g p s 具有全球、全天候、连续、实时提供高精度的三维位置、三维速度和时间 信息等一系列的功能，是实现全球导航定位的高新技术。 该系统由三部分构成：g p s 卫星星座( 空间部分) ，地面控制部分( 控制部分) 和g p s 信号接收机( 用户设备部分) ，三者关系如图2 2 。 g p s 卫星星座 g p s 空间部分由2 4 颗卫星组成，分布在互成6 0 度的6 个椭圆形轨道面上，轨道 倾角为5 5 度，每个轨道面上布设4 颗卫星。g p s 卫星的作用是向广大用户连续不断 地发送导航信号( 又称g p s 信号) ，并用导航电文报告自己的现时位置以及其他在 轨卫星的概略位置；接收地面主控站通过注入站发送卫星的调度命令如适时地改 第二章智能车辆导航系统的关键技术1 3 正运行偏差，或者启用备用时钟等命令；在飞越注入站上空时，接收由地面注入 站用s 波段发送到卫星的导航电文和其他相关信息，并通过g p s 信号形成电路适时 地发送给广大用户。 图2 2g p s ，i ! 星全球定位系统的三大组成 地面控制系统 g p s 地面控制系统主要用来测量和计算每颗卫星的星历，编辑成电文发送给卫 星，即卫星所提供的广播星历，由1 个主控站、3 个注入站和5 个监控站组成。 监控站是数据采集中心，其任务是对每颗卫星进行连续不断的观测，并在主 控站的控制下定时将观测数据送往主控站。5 个监控站提供的观测数据形成了 g p s 卫星实时发布的广播星历，主控站的任务是提供g p s 的时间基准，控制地面 部分和卫星的正常工作，包括处理由各监控站送来的数据，编制各卫星星历，计 算各卫星钟的钟差和电离校正等参数，并将这些导航信息送给注入站；控制卫星 运行轨道、启用备用卫星。注入站的任务是在卫星通过其上空时，把导航信息注 入卫星，并负责监控信息的正确性。 g p s 信号接收机 g p s 接收机的作用就是实时地接收空间卫星发射媳g p s 信号，进行分析计算 初步得到目前接收机所在的经纬度坐标、速度等基础信息。g p s 接收机由天线单 元和接收单元两部分组成：天线单元由接收天线和前置放大器组成；接收天线有 定向天线、偶极子天线、微带天线、螺旋天线等。 2 2 2g p s 定位基本原理 g p s 定位以观测站至g p s 卫星问的距离为基本观测量【1 刀。主要采用两种观测方 法：一是测量g p s 卫星发射的测距码信号( c a 码和p 码) 到达用户接收机的传播时 间；二是测量接收机接收到的具有多普勒频移的载波信号与接收机产生的参考载 1 4智能车辆导航系统及带限条件下最优路径算法的研究和实现 波信号之间的相位差。 g p s 卫星发射两种伪随机测距码，一是精密测距码p 码，由两个互素的m 码组 成模2 复合码；另一个是粗捕获码c a 码，由两个具有良好互相关特性的同族m 码 序列构成的哥尔德码族。 g p s 卫星定位系统定位的基本原理是时延测距，通过测量4 个已知位置上信号 传播的延迟时间，确定4 个已知位置至用户的距离，根据这4 个量测距离计算出用 户的三维位置和用户与已知位置的时间同步偏差。当卫星发射一伪随机码，而接 收机内也产生( 复制) 一个相同的伪随机码。当卫星信号经过传播距离的延迟z 后 到达接收机，与本地码进行相关处理；移动本地码，使相关函数达到最大值。这 样，本地码所移动的时间延迟值就是卫星信号传播时间f ，乘上光速值得到所测距 离。g p s 有两种定位方式： 单独g p s 定位：就是独立确定待定点在地心坐标系中的绝对位置。 差分g p s 定位( d g p s ) ：就是将一台接收机安置在地面己知点上作为基准 点，并与所有待测点的接收机进行同步观测，基准点根据其精确已知的坐标求出 定位结果的改正数或伪距观测量的改正数，然后通过数据链( 如无线电) 把这些改正 数实时传送给相关用户，用户利用这些改正数对自己的定位结果或伪距观测量进 行改正，从而提高定位精度。 我们以伪距单点定位法来说明g p s 的定位原理。假定t g 和t j 分别表示卫星j 发 射信号时的g p s 时和卫星钟时刻，露和r 分别表示接收机收到该卫星信号时的g p s 时和接收机钟时刻，则卫星信号传播时间为 f = t o t g 但是，实际上我们只能测得f 7 和丁，因此实际测量得的卫星信号传播时间为 e j = t t j 以a t j 和缸分别表示卫星钟和接收机钟时刻的偏差，即 厶t | = tj t 乞 u a t = t 一 l i t 则有 z k ( 一略) + 出一& 再计入信号传播过程中经历的电离层、对流层和多经迟延等误差，得到 f = ( 乙一f 占) + a t a t + 匕+ a t , o + 垃乙 将上式两边同乘以光速c ，得到 p = r + ca t - ca t + c f 乙+ ca t 。j + c ，( 2 1 ) 式中， r tx ( x x j ) 2 + ( y yj ) 2 + ( z z 7 ) 2 为接收机至卫星的几何距离， ( x ，y ，z ) ，o ，y j 。, z 7 ) 为接收机和卫星j 在地心空间直角坐标系中的三维坐标；p 7 是 第二章智能车辆导航系统的关键技术 1 5 实际上可得到的距离观测量，由于不同于真实距离j r ，所以叫做“伪距。式( 2 1 ) 就是g p s 定位的基本观测方程。由于卫星钟差a t j 可由地面监控系统测定并通过 卫星发播的导航电文提供给用户，电离层和对流层传播迟延c & 三。和c a t l 也可用 导航电文提供的电离层和对流层参数模型进行校正，因此方程( 2 1 ) 中有z ，y ，z ，a t 4 个未知量需要求解，当可以对4 颗卫星进行观测时，通过求解矩阵方程得到这4 个未知量。 总之，g p s 定位的原理就是至少接收4 颗卫星的g p s 信号，由卫星到定位点 的伪距和卫星目前的坐标求出待定位点现在的经纬度坐标。 2 2 3g p s 定位的主要误差 通过对g p s 定位原理的分析，我们可以发现影响伪距观测量的主要误差来源 有3 个方面。 空间卫星部分 卫星星历误差：影响定位精度的主要因素。 卫星时钟误差：可以通过人为的校正卫星钟频，利用主控站测定的参数进行 模型改正及差分的方法消除。 信号传播部分 电离层传播迟延：可以通过双频观测、电离层模型修j 下或者差分的方法加以 减弱。 对流层传播延迟：可以利用差分方法消除对流层传播延迟。 多径效应：通过多次取均值、选择屏蔽良好的天线或者将天线安置在反射面 少的地方等办法消除。 用户接收机部分 用户接收机测量误差：通过提高接收机硬件的灵敏度和稳定度来降低接收机 本身对定位精度产生的影响。 以上介绍了伪距定位的误差来源及其相应的改善措施，所有这些误差最终会 对定位精度产生极大的影响( 定位误差将达到1 0 0 m 的数量级) ，在车辆导航系统 中，地图匹配是减小定位误差对车辆导航影响的有效方法。地图匹配将在靳松杰 同学的论文中详细介绍。 2 2 4g p s 导航系统的特点 g p s 与其他导航系统相比具有以下特点： 全球地面连续覆盖。 。 由于g p s 卫星的数目较多且分布合理所以地球上任何地点均可同时观测到至 1 6智能车辆导航系统及带限条件下最优路径算法的研究和实现 少4 颗卫星从而保障了全球全天候连续的三维定位。 多功能高精度 g p s 可为各类用户连续提供动态目标的三维位置、三维速度和时间信息。利用 c a 码单点定位精度可以达至1 1 4 m ( 无s a 影响的情况下) ，测速精度可以达n 0 3 m s ， 测时精度可以达至u 5 0 0 n s 。如果采用差分定位方法，则利用c a 码定位精度可以达 3 1 l j 5 m ，利用p 码定位精度可以达到l m 。 实时定位 利用g p s 导航，可以实时地确定运动目标的三维位置和速度，由此既可保障运 动载体沿预定航线运行，也可实时地监视和修正航行路线并可选择最佳航线。 由上述可知，g p s 在导航方面具有极高的应用价值，它从根本上解决了人类在 地球上和近地空间的导航和定位问题。 2 2 5g p s 在车辆导航领域的主要应用 车载导航的原理主要是利用电子地图和i g p s 接收机的实时定位技术，组成g p s 与电子地图相结合的各种电子导航系统，其应用模式主要有以下两种： g p s 单机定位与矢量电子地图相配合。该系统可根据目标位置( 工作时输 入) 和车辆的现时位置( 由g p s 测定) 自动计算和显示最优路径，引导司机最快地到 达目的地，并可用多媒体方式向驾驶员提示。 g p s 差分定位与矢量电子地图相配合：该系统通过固定站与移动车辆之间 的两台g p s 接收装置获得的信号，利用伪距差分技术，可使定位精度达至0 1 - 3 m ， 当采用双向通讯方式( 如无线通信) 时，则可构成车辆的自导航系统，又可将移 动车辆上的g p s 定位结