（系统理论专业论文）电子导航地图的生成及最优路径研究.pdf

摘要 摘要 电子地图是导航系统的基础和重要组成部分之一，本文重点研究了电子导航 地图的生成和最优路径算法。跟据现有电子地图发展情况和存在问题，本文提出 种新的道路网络模型、建立了道路网络数据库，进而生成了电子导航地图，并 且实现了地图的放大、缩小和漫游还有地图信息和兴趣点的双向查询等基本功 能，最后研究了最优路径搜索技术。 首先，利用a u t o c a d2 0 0 2 矢量化现有的电子地图，得到需要的道路信息。这 时，为了克服现有路网模型中对实际路网描述不够周详、难以表达路段的拓扑关 系等缺陷，有效地描述实际道路网络，提出了一种新的道路网络模型。 然后，在路网模型的基础上，通过建立路网数据库和兴趣点信息数据库来管 理地图上道路的信息和兴趣点信息，解决了现有电子地图的图幅接边问题、难以 管理地图信息、信息量少且难以更新等缺点，使信息查询、最优路径搜索等功能 的实现方便易行。另外，在数据库中除了描述道路几何形状的数据外，还描述了 道路的路况信息，为最优路径搜索时权值的计算带来极大方便。这时可以利用路 网数据库自动生成电子地图，并实现了放大、缩小、漫游还有兴趣点信息与地图 信息的双向查询等功能。 最后，研究了导航系统的关键部分一最优路径搜索，在对最优路径搜索中路 阻权值计算做了详细研究之后，就静念和动态最优路径搜索做了探讨。在基于人 工智能的启发式搜索方法- a , 算法的基础上考虑交通限制条件，提出了一种加 入交通限制条件的a 算法，分别就距离最优和时间最优还有组合查询做了比较， 实验表明，以时间作为路阻权值的最优路径更接近真实路径。 关键词：电子导航地图道路网络模型 道路网络数据库a 算法 最优路径搜索 昆弱理t 大学硕上学位论文 a b s t r a c t d i g i t a lm a pist h eb a s ea n do n eo ft h ei m p o r t a n tp a r t si nn a y i g al io n s y s t e m t h ec o m p o h e n tp a r tsa n dm a i nf u n c t io n so ft h ed i g i t a ln a y i g a t i o n m a pa r ea n a l y z e di nt h isp a p e r b a s e do nd e v e l o p m e n tin s t a n c ea n de x i8 t in g p r o b l e mo ft h ed i g il a lm a pi ne x i s t e n c e ，i nt h isp a p e r ，an e wr o a dn e t w o r k m o d e lisp u tf o r w a r d a f t e r w a r d st h isp a p e rd e s e r i b e st h ep r o d u c t i o no f r o a dn e t w o r kd a t a b a s ea n dh a s i cf u n c t i o n ss u c ha sz o o m i n go u t 、z o o m i n g i n 、r o a m in ginm a pa sw e l la st h eb i d ir e c t i o n a ls e a r c hb e t w e e ni nm a p i n f o r m a t i o na n dp o i n to fi n t e r e s t ( p o i ) t h e nt h ea l g o r i t h mf o rt h eo p t i m a l p a t hiss t u d i e d f i r s t l y t h ed i g i t a lm a pi ne x is t e n c eisv e c t o r e dw it ht h es o f t w a r e a sa u t o c a d2 0 0 2 b e c a u s eo f1 a c k i n go fp a r t ic u l a ri n f o r m a t i o no fr e a lr o a d n e t w o r ka n dt oe f f e c t iv e l yd e s c r i b et h et o p 0 1o g yr e l a t i o no fr o a ds e g m e n t ， an e wr o a dn e t w o r kisc t e a t e d t h e n 、b a s e do nt h e r o a dn e t w o r km o d e l ，t h ed a t a b a s eo f r o a d i n f o r m a t io ha n d p o it h a ta r eo fm u c hb e n e f i tt ot h et e a liz a t io no ft h e s y s t e ma r eb u i l tt om a n a g et h ei n f o r m a t i o no fr o a d sa n dp o i ，w h ic hr e s o l v e t h ed is a d v a n t a g e ss u c ha sb ed i f f ic u l tt om a n a g em a pi n f o r m a t i o na n d1 a c k o fi n f o r m a t i o n ，e t e i na d d i t i o n ，t h ed a t a b a s ed e s c r i b e sr o a dc o n d i t i o n i n f o r m a t i o na sw e l la sg e o m e t r yd a t a t h e nd i g i t a m a pisa u t o m a t i r e l y b u iltw it ht h er o a dn e t w o r kd a t a b a s e f i n a l1yt h eo p t i m a lp a t hs e a r c hm e t h o diss t u d ie di nt h ep a p e r a f t e rt h er o a dw e i g h tf o rt h es e a r c ho ft h eo p t i m a lp a t hisa n a l y z e d ，t h e s t a r ico p t i m a lp a t hs e a r c ha n dd y n a m ico p t i r e a lp a t hs e a r c ha r ed i s c u s s e d an e wa a l g o r i t h mw i t ht r a f f ic r e s t r i c tisp r e s e n t e dt ot a k ea d v a n t a g e o fa $ a l g o r i t h m ( h e u r is t ics e a r c hg r o u n do na r t i f ic i a lin t e l1i g e n c e ) a n d c o m p a r ei nt h eo p t i m a lp a t hi n d is t a n c ew i t h i nt i m e t e s tr e s u ll ss h o w t h eo p t i m a lp a t hi nt i m ei sm o r ec l o s e dt or e a lp a t h k e yw o r d s ：d i g i t a ln a y i g a t i o nm a pr o a dn e t w o r km o d e l r o a dn e t w o r k d a t a b a s ea a l g o r i t h m t h eo p t i m a l p a t hs e a r c h i i 昆明理工大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下( 或 我个人) 进行研究工作所取得的成果。除文中已经注明引用的内 容外，本论文不合任何其他个人或集体已经发表或撰写过的研究成 果。对本文的研究做出重要贡献的个人和集体，均已在论文中作了明 确的说明并表示了谢意。本声明的法律结果由本人承担。 学位论文作者签名： 日 期： 黑斟 硝年f 月，日 关于论文使用授权的说明 本人完全了解昆明理工大学有关保留、使用学位论文的规定，即： 学校有权保留、送交论文的复印件，允许论文被查阅，学校可以公布 论文的全部或部分内容，可以采用影印或其他复制手段保存论文。 ( 保密论文在解密后应遵守) 导师签名：鏊堑寞论文作者签名：墨望 日期：型姜生f 月! = 旦 一兰二兰堕堡 第一章绪论 1 1 电子导航地图的研究背景和必然性 1 。1 1 智能交通系统( it s ) 及其发展概况 近年来，随着经济的发展，科技的进步，城市的机动车数量不断增加，而原 有的道路条件远远不能满足需要，这就导致城市交通流量不断增大，交通拥挤程 度日益加剧。交通拥挤将会导致时间延误、交通事故增多、环境污染加剧、燃油 损耗上升，这些都造成巨大的经济损失。最近的一项研究表明，仅美国的主要都 市每年出了二交通拥挤而造成的浪费就已经超过4 7 5 亿美元，每年因交通拥挤浪费 了多达1 4 3 5 亿升的燃料和2 7 亿工作小时。9 0 年代以来，这些数字以每年5 1 0 的速度继续增长。 为了解决这一共同面临的问题，美国、日本、欧洲等发达国家的交通管理部 门投入了大量的人力和物力，开始大规模地进行道路交通运输智能化的研究， i t s ( ir l t e l l i f f e n c et r a n s p o r ts y s t e r n ) ，即智能交通系统应运而生。i t s 的思想是 从系统的观点出发，把车辆和道路综合起来考虑，并将先进的信息技术、数据通 信传输技术、电子传感技术、电子控制技术及计算机处理技术等有效地集成运用 于整个地面交通管理系统而建立的一种在大范围内、全方位发挥作用的，实时、 准确、高效的综合交通运输管理系统，它由若干个高科技开发项臼组成，这些项 目的开发可加强道路、车辆、驾驶员以及管理人员之间的联系，实现道路交通管 理“自动化”，车辆行驶“智能化”，使管理人员对车辆行驶状况一清二楚，驾 驶员对实时交通状况了如指掌，从而减少道路阻塞，提高行车安全和行车效率。 除了解决交通问题之外，i t s 还将成为继军事应用之后高新技术最大的应用 市场，所以欧、美、日、韩国、新加坡等国家纷纷斥巨资开展i t s 方面的研究与 开发，并己取得了一些成果。主要集中在：实时自动定位系统、车辆安全系统、 车辆控制系统、电子收费系统、公路及车辆管理系统、公共交通系统。研究成功 并已投入使用较多的是汽车定位与导航技术，主要包括：驾驶信息系统、交通管 理系统、车队管理系统等。据调查显示，2 0 0 2 年，欧洲汽车导航仪市场超过1 0 0 万台；在美国，预计2 0 0 5 年汽车导航仪市场规模将达到1 5 0 万台；而在日本， 2 0 0 2 年的汽车导航仪市场超过了2 0 0 万台。目前，美国e t a k i n c 研究的汽车导 航系统( a u t o m o t i v en a v i g a t i o n ) ，可以为用户提供以汽车为中心的不断更新的 地图，它允许用户以某种方式输入目的地，计算机会为用户提供一条最佳路线， 昆明理3 - ( 学硕十学位论文 用户只需按地图的提示就可以到达目的地。日本的丰目汽车公司已经开发出了 实用型的汽车导航定位产品：并有2 0 多万辆汽车装备了车辆交通信息服务装置 一路导器。德国的梅塞德斯一奔驰s 系列车型已选用一种电子导航仪，该装置可 以解决司机在陌生城市星驾驶汽车的困难，可以引导司机沿着最佳路线行驶到达 目的地”j 。 相对欧美日发达国家来讲，我国智能交通系统的发展虽然刚开始不久，但发 展速度很快，其中车载导航产业在理念、技术上都有很大的提高。预计2 0 0 4 年 t 会需求的车载导航系统的新增数量达到2 5 万台到3 0 万台之间。随着汽车前装市场 的蓬勃发展，以及国际市场的开发，我国车载终端的产量在2 0 i o 年有望达到5 0 0 力台“。 综合现在各国进行的i t s 研究，当前i t s 的研究课题可以分为以下六类： 1 ) 先进的交通管理系统a t m s ( a d v a n c e dt r a f f icm a n a g e m e n ts y s t e m ) a t m s 用于监测、控制和管理道路交通，在道路、车辆和驾驶员之间提供通信 联系。它依靠先进的交通监测技术、计算机信息处理技术和现代通信技术获取有 关交通状况的信息并进行实时处理，及时地向道路使用者发出诱导信息，从而达 到有效地管理交通的目的。 2 ) 先进的驾驶员信息系统a dt s ( a d v a n c e dd r iv e rt n f o r m a t i o ns y s t e ) a d i s 足以个体驾驶员为服务对象，对车辆进行导航以及为驾驶员提供路线向 导。驾驶员可以通过车载路径诱导系统，在与控制中心的双向传递中获取信息， 让驾驶员或旅客知道所处的位置以及如何找到相应的服务，使车辆始终在最优路 径 ：以安全、高效和舒适的方式从出发地到达目的地。 3 ) 先进的车辆操控系统a v c s ( a d v a n c e dv e h ic l ec o n t r o ls y s t e m ) a v c s 主要是利用激光技术、电子技术、微波技术、雷达技术和图象处理技术 等先进技术帮助驾驶员实行自动车辆控制，有效地防止碰撞危险，提高道路的流 通量，以保证车辆高效、安全行驶。它与a d i s 的结合，在不远的将来，将发展成 汽车自动驾驶系统。 4 ) 商用车辆调度管理系统c v o m ( c o m m e r c i a lv e h ic l eo p e r a t i o n f 1 e e l m a n a g e m e nt ) c v o m 实质上是运输企业应用智能道路交通管理系统( i v h s ) 技术束谋求最大 效益的一种调度管理系统。该系统利用车辆自动识别技术、车辆跟踪技术、车辆 自动定位技术等来提高车辆的运营效率，增加安全度，改进对突发事件的反应能 力，改善车队的管理和交通状况。 2 笙二皇堡垒 5 ) 先进的公共交通系统a p t s ( a d v a n c e dp u b l ict r a n s p o r t a t i 。ns v s t e r a ) 采用各种智能技术促进公共运输业的发展，如通过个人计算机、闭路电视等 向公众就出行方式和时间、路线及车次选择等提供咨询，在公交车站通过显示器 向候车者提供车辆的实时运行信息。 6 ) 先进的乡间运输系统a r t s ( a d v a n c e dr u r a 】t r a n s f e rs y s t e m ) a r t s 主要包括为驾驶员和事故受害者提供无线紧急呼叫系统，不利道路和交 通环境的实时警告系统以及有关驾驶员的服务设施和旅游路线、景点等的信息系 统。 1 1 。2 电子导航地图研究的必要性和应用前景 在i t s 的研究中，有一个非常重要和关键的问题，那就是驾车者如何随时知 道自己的位置呢? 这里所指的位置不仅仅是车辆所在的坐标位置( 如经度、纬度 等) 。更重要的是指车辆在人们习惯的地图背景上的位置。这恰恰就是导航系统 所要研究的内容，它会根据道路信息实时调整行驶路线，这样既可以减少路程花 费时间，还可以帮助交通管理部门调整交通流量，一举两得。这里面涉及两方面 的技术问题：一是实时定位的问题，二是地图数据库的问题。这些都是导航系统 所需要研究和解决的问题。 1 12 1 全球定位系统( 6 p 8 ) 简介“1 关于移动目标的实时定位问题，现今世界范围内均开始大量使用全球定位系 统，即g p s ( g l o b a lp o s i t i o i l in gs y s t e m ) 。g p s 系统是美国政府从1 9 7 3 年到1 9 9 3 年历经2 0 年耗资3 0 0 亿美元建立的，是继阿波罗登月计划和航天飞机计划后的第 三项庞大的空问计划，这是一套能够实时、全天候、为全球范围内的陆地、海上 和空中的各类用户提供连续实时的三维定位、三维速度及精确时间信息的系统。 g p s _ 定位卫星、地面控制站和用户接收机三个部分组成。定位卫星目前由 2 4 颗卫星组成，其中2 1 颗为工作卫星，3 颗为备用卫星，分布在离地面高度2 0 2 0 0 k m 处的互成6 0 0 角且倾角为5 5 0 的6 个椭圆形轨道面上。每个轨道面卜布设4 颗卫星， 运行周期为l2 4 , 时1 # 。3 颗卫星的覆盖区域超过全球，故使全球各地用户至少同 时可接收到6 颗卫星播发的导航信号，最多的可接收到1 1 颗卫星播发的导航信号。 地面控制站用于测量和预报卫星轨道并对卫星上的设备工作情况进行监控，为用 户接收机提供卫星相对于地面的位置数据。 用户接收机利用接收的、来自于由其星历数据准确获知空间位置的卫星发射 的、以光速传播的信息，测量该信息传播的时间，计算出其与该卫星的相对位置， 即距离。利用距离三角形测量原理，用户g p s 接收机同时接收3 颗卫星的信号，可 昆明理i ：大学硕士学位论文 以计算出用户g p s 接收机所在的三维空间位置；同时，利用对在测量时间内获得 的距离进行时问微分，根据线性速度与多普勒频率，从而计算出自身的运动速度。 由于用户接收机的时钟基准，相对于g p s 的原子钟基准存在误差，因此，将其实 际测量距离称之为“伪距”( p s e u d or a n g e ) ，将在其实际测量时间阳j 隔内对该伪 距离微分所得之速度测量值称之为“差伪距”( d e l t ap s e u d or a n g e ) ，亦称“伪 距率”。为了确定用户6 p s 接收机所在的三维位置并对其时钟误差进行校准，必 须至少同时跟踪接收g p s 定位卫星中的4 颗卫星的信号，才能完成导航计算任务。 若同时跟踪接收g p s 定位卫星中的4 颗以上的卫星，则在使用相同的惯性导航系统 上的导航计算的精度会更高。 g p s 定位卫星中的每颗卫星均装有铯原子钟作为频率标准，保证了所有卫星 能够在一个月或更长的时间内独立工作而无需地面校正，也保证了精密定位的要 求。此外，卫星上还装有传送定位信号的载波发射机，载波信号工作在l 波段的2 个频率：l l 为15 7 5 4 2 m h z ，l 2 为1 2 2 7 6 m h z 。l l 载波信号采用1 0 2 3 m h z 、带宽l m h z 的伪随机噪声编码进行调制。重复调制时间为1 0 2 4 位或1 毫秒，该调制编码称之 为“粗码( c a 码) ”，为全球民用用户提供“标准定位服务”( s p s ) 。l 2 载波信号 采用1 0 2 3 i h z 、带宽1 0 m h z 的伪随机噪声编码进行调制，重复调制间隔时间为7 天，该调制编码称之为“精码( p 码) ”，为美国和其盟国军事用户提供“精密定 位服务”( p p s ) 。卫星播发的导航信号的传输速率为5 0 位秒，l l 和l 2 载波信号除 运载导航信息外，还有描述卫星轨道、时钟校准和其他系统参数的各数据位。 目前除了g p s 之外，用于车辆导航的定位技术还有g l o n a s s 、i n s ( 惯性导航系 统) 、d r ( 航迹推算定位) 、m m ( 地图匹配) 等。与这些导航定位系统相比，g p s 具有 以下的优点： 1 ) 全球地面连续覆盖。由于g p s 卫星的数目较多，且分布合理，所以地球上 任何地点均可同时观测到至少4 颗卫星，从而保障了全球、全天候连续地三维定 位。 2 ) 功能多，精度高。g p s 可为各类用户连续地提供动态目标的三维位置、三 维速度和时间信息。利用c a 码单点定位精度可达1 4 m ( 无s a 影响的情况下) ，测速 精度可达0 3 m s ，测时精度可达5 0 0 n s 。利用p 码的定位精度可达3 m ，测速精度可 达0 1 m s ，测时精度可达1 0 0 n s 。 3 ) 实时定位。利用g p s 导航，可以实时地确定运动目标的三维位置和速度， 由此既可保障运动载体沿预定航线运行，也可实时地监视和修正航行路线，并可 选择最佳航线。 4 第一章绪论 4 ) 抗干扰性好、保密性强。g p s 采用数字通信的特殊编码技术，即伪噪声码 技术，圉而具有良好的抗干扰性和保密性。 5 ) 操作方便。随着g p s 接收机不断改进，自动化程度越来越高，操作也相应 地越来越方便。 现在随着g p s 应用领域的不断扩大和深入它的技术随之被全世界各行各业 所接受。( ；- p s 技术以其独有的延伸力和渗透力进入入类经济发展的各个领域，呈 现出飞速发展、日益成熟的新局面。目前，g p s 技术已经发展成为多领域、多模 式、多用途、多机型的高新技术国际化产业。由此为公安、保险、交通、测量等 行业带来了新的活力，也产生了一批与6 p s 技术有关的新行业。比如在车载导航 系统中，g p s 的实时定位功能正是车载导航的基本要求。现在世界卜已有许多公 司开发出了各种型号、性能优良的6 p s 接收机，并且在车辆、船舶等交通工具的 导航系统中发挥着重要的作用。 1 1 2 2 电子导航地图的应用前景 在导航系统中，仅仅有车辆的坐标位置是不够的，驾车者仍然不能知道自己 的实际位置，还需要有相应的地图才能定位自己的确切位置，这就是所谓的电子 导航地图。例如：在提供交通信息情报时，驾驶员必须依据其车载导航系统，才能 使车辆始终行驶在最优路径上，其使用的车载导航系统就是基于电子地图之上 的。 可见，电子导航地图是研究智能交通系统的各个子系统的基础和重要部分之 一。研究电子地图将象研究智能交通系统一样，对减少和避免交通拥挤和事故， 本质性地提高车辆的行车安全和行车效率，提高生产效率，增强本国企业的国际 竞争力，培育未来新产业，节约能源和减少汽车尾气对环境的污染均有重要的意 义。因此，值得深入研究。 电子导航地图的基本功能就是根据g p s 接收机计算出来的经度、纬度参数在 地图上进行定位：而实际上，现今的电子导航地图系统的功能已经远远超越了这 个基本要求。目前由于g p s 定位速度快、定位精度高以及价格便宜等特点，已被 越来越多的人们所接受，特别是在2 0 0 0 年5 月1 目美国己经暂时取消了“选择可用 性( s a ) ”政策，恢复c a 码伪距定位的1 4 米精度，这无疑为6 p s 用于车辆导航和监 控提供了方便。 最新市场预测研究表明车辆定位导航设备及系统具有巨大潜力。对于全世界 对装有6 p s 接收机的车用导航装置的需求，日本、美国、欧洲的研究机构对各自 地区进行了研究。美困6 p s 产业协会曾经对全球g p s 市场作了估计：1 9 9 4 年8 6 7 亿 昆明理工：人学硕士学位论文 美元，1 9 9 5 年2 0 亿美元，2 0 0 0 年8 5 亿美元。根据美国商业部的数据统计，2 0 0 3 年， 全球g p s 设备的销量达到16 0 亿美元。其中车载导航产品占3 5 左右。预计2 0 0 5 年 可能增长到3 1 0 亿美元，其中民用产品可占9 8 5 ，两且7 5 以h 将主要用于车辆 导航。而r 本1 9 9 5 年己出售汽车导航系统1 2 0 万套，比1 9 9 4 年上升7 3 2 ，一项日 本研究预测到2 0 0 5 年汽车导航装置在日本的总销售量可达3 0 0 万套“1 。在欧洲， 1 9 9 5 年法国推出汽车导航系统，巴黎的公共汽车率先使用车辆调度和导航系统。 美国菲利浦公司和法国的赛尔( 8 e l j 公司正在研究轿车导航系统。法德联合的 c a r m i n t 公司将在他们的轿车导航系统中采用g p s 接收机或g p s 与推算导航、车- 轮 旋转传感器和电子罗盘的组合。 在我臣，不少城市引进国外或采用国产的车辆导航系统装备了公安、部队、 交警、金融、消防、公交及其他部门的车辆，发挥了较大的社会效益。目前北京 市的汽车保有量为l8 0 万辆，广州的汽车保有量为9 0 万辆，按照这一趋势，估计 到2 0 0 5 年，北京市的车载导航系统装机台数为l l o 千台，市场规模约为1 2 亿元， 到2 0 0 8 年，装机台数约为3 0 0 干台，市场规模约为3 5 亿元，到2 0 0 5 年，广州的车 载导航系统装机台数约为5 0 于台，市场规模约为6 亿元，到2 0 0 8 年，装机台数约 为13 0 千台，市场规模约为1 6 亿元。特别是2 0 0 8 年北京奥运会、2 0 1 0 年h 海世博 会的需求，将给我国导航产业的发展带来巨大的商机。 可以看出，今后g p s 用于车辆导航和车辆监控将会成为重要产业，基于g p 8 的电子导航地图系统将具有广泛的应用前景。 1 2 电子导航地图概述 用于导航的电子地图是一种集地理信息和兴趣点信息于一体的信息系统。如 果应用在车辆导航系统上，它能根据导航设备定位的车辆信息显示实时路况信 息、为驾驶员提供信息咨询、并能灵活方便地选择出发地和目的地之间的最佳行 驶路线，解决了车辆的跟踪定位问题。 1 2 1 电子导航地图的组成 电子地图是指用数字形式描述地图要素的属性、定位和关系信息的数据集 合，在车辆导航系统中，电子地图系统硬件主要由计算机和导航设备组成。导航 设备通常都使用g p 8 接收机，用于提供实时的车辆位置信息。计算机用于完成电 子地图显示、所有的信息处理和功能实现。电子导航地图一般具有以下功能： 1 ) 显示道路网地图和实时修改地图信息 电子地图的显示包括以指定的比例尺显示电子地图、无级地改变电子地图的 比例尺( 任意的放大和缩小) 、分层或有选择地显示地图信息、电子地图的漫游等 昆明理太学颀+ 学位论文 美元，1 9 9 5 年2 0 亿美元，2 0 0 0 年8 5 亿美几。根据美国商业部的数据统计，2 0 0 3 年， 全球( ；p s 设备的销量达到16 0 亿美兀，其中车载导航产品占3 5 k 右。预计2 0 0 5 年 i j 能增长到3 10 亿美元，其中民用产品可占9 8 5 ，而且7 5 以上将主要用于车辆 导航。而 t 本1 9 0 5 年己出售汽车导航系统1 2 0 万套，比1 9 9 4 年上升7 3 2 ，一项日 本研究预测到2 0 0 5 年汽车导航装置在f 1 本的总销售量可达3 0 0 万套“1 。在欧洲， 1 9 9 5 年法国推出汽车导航系统，巴黎的公共汽车率先使用车辆调度和导航系统。 美国祚利浦公司和法国的赛尔( s e l ) 公司正在研究轿车导航系统。法德联台的 c a r m i n t 公司将在他们的轿车导航系统丌1 采用6 p s 接收机或6 p s 与推算导航、车轮 旋转传感器和电子罗盘的组台。 在我国，不少城市引进国外或采用国产的车辆导航系统装备了公安、部队、 交警、金融、消防、公交及其他部门的车辆，发挥了较大的社会效益。目前北京 市的汽车保有量为18 0 万辆，广州的汽车保有量为9 0 万辆，按照这一趋势，估计 到2 0 0 5 年，北京市的车载导航系统装机台数为1 1 0 千台，市场规模约为1 2 亿元， 到2 0 0 8 年，装机台数约为3 0 0 千台，市场规模约为3 5 亿元，到2 0 0 5 年，广州的车 载导航系统装机台数约为5 0 千台，市场规模约为6 亿元，到2 0 0 8 年，装机台数约 为l3 0 干台，市场规模约为1 6 亿元。特别是2 0 0 8 年北京奥运会、2 0 1 0 年上海世博 会的需求，将给我国导航产业的发展带来巨大的商机。 可以看出，今后g p s 用于车辆导航和车辆峨控将会成为蓐要产业，基于g p s 的电子导航地图系统将具有广泛的应用前景。 1 2 电子导航地图概述 用于导航的电子地图是一种集地理信息和兴趣点信息于。体的信息系统。如 果应用在车辆导航系统上，它能根据导航设备定位的车辆信息显示实时路况信 息、为驾驶员提供信息咨询、并能灵活方便地选择出发地和目的地之问的最佳行 驶路线，解决了车辆的跟踪定位问题。 1 2 1 电子导航地图的组成 电子地图是指用数字形式描述地图要素的属性、定位和关系信息的数据集 合，在车辆导航系统中，电子地图系统硬件主要由计算机和导航没各组成。导航 设备通常都使用g p s 接收机，用于提供实时的车辆位置信息。订算机用于完成电 予地图显示、所有的信息处理和功能实现。电子导航地图一般具有以下功能： 1 ) 显示道路网地图和实时修改地图信息 电子地图的显示包括以指定的比例尺显示电子地图、无级地改变电子地图的 比例尺( 任意的放大和缩小) 、分层或有选择地显不地图信息、电子地图的漫游等 比例j t ( 任意的放大和缩小) 、分层或有选择地显示地图信息、电子地图的漫游等 第一章绪论 功能。电子地图的实时改证应允许用户根据所获得的信息对电子地图数据库中的 数据进行修改和补充，如某大街交通堵塞、新设的单行道、新增道路、交通管理 规章的变更等等。 2 ) 实现兴趣点和地图信息的双向查询 这一功能能够通过查询兴趣点，如标志物、车站、宾馆、旅游景点等，在地 图l 二显示出具体位置，并能同时从数据库中获取其具体信息。同时，还可根据需 要，利用电子地图上游标的位置显示出兴趣点，以此为关键字在数据库上获取浚 目标的主题信息并显示出来。 3 ) 汽车运行跟踪定位和导航 要求电子地图系统必须同g p s 定位导航设备连接，将传感器探测的车辆轨迹 与已知道路网络进行匹配，精确地定位车辆的实际位置，根据所选择的最佳行车 路线，引导驾驶员按照预设路线行驶，在电子地图上实现汽车的自动跟踪定位。 每当遇到转弯或需要引起驾驶员注意的情况时，系统应以字幕的形式或多媒体的 形式提前给予提示。 4 ) 计算最佳出行路线 能够以行车距离最近、行车时间最短、拥挤程度最低或道路质量最优或者是 这几项的组合查询为目标函数计算交通路网上的任何两节点的最佳行车路线。 1 2 2 现有电子地图存在的问题 虽然近年来用于导航电子地图得到了迅速发展，许多系统已经投入使用，并 取得了良好的经济效益；但是，现有的电子地图还存在有以下问题： 1 ) 图幅接边。 现有电子地图基本上都是从纸质地图数字化得来的，由于对原有纸质地图 或航片的数字化是分幅进行的，各幅图间的接边问题没有得到很好的解决。跨越 图幅的道路，在接边处会出现扭曲错位。虽然可以人工修整，但花费的工作量大， 并且不能从根本上杜绝错位的发生。一旦某条道路发生了错位，当进行地图匹配、 最佳行车路线搜索、路径导航时，得到的必然是错误的结果，严重影响了导航系 统的质量。 2 ) 难以管理地图信息。 现有电子地图大多将所有信息放在图面上，不便于信息的获取。导航定位设 备传来的是坐标，用户需要的是实体信息，即存在坐标值与道路名等信息的关联 问题。若仅仅将道路名写在地图上，虽然可以直接从地图读取信息，但这仅仅是 地图显示，不能实现地图匹配、最佳路径搜索、路径导航等功能。系统不能管理 7 昆明理t 大学硕上学位论文 坐标间、实体问、坐标和实体间各种现实存在的复杂关系，这严重阻碍了导航系 统各种功能的实现。 3 ) 信息量少且难以更新。 将信息固定在图面上，仅仅含有原纸质地图、航片的信息，不能加入诸如路 况信息等内容，而路况信息对于最优路径搜索、路径导航具有重要作用。因为实 际应用中的最佳路径搜索，多是时间最短而非距离最短，而行车时间不仪弓距离 有关，还与道路是否堵塞、车道情况等路况信息有关。在大城市中，路况信息的 重要性更加明显。在图面上是难以保存路况信息等非可视化信息的。此外，现有 电子地图一旦制成，其所含的信息就难以改变，这与现实情况中信息的多态性不 适应，难以从这些过时的信息中得出正确的结论。 可见，目前国内外已投入使用的电子导航地图还不完善，还需要进一步的研 究。 1 2 3 已有的最优路径算法 最优路径搜索是帮助驾驶员在旅行前或旅行中规划行驶线路的过程，是车辆 导航的一个基本问题，也是实现导航功能的前提条件，所以是电子导航地图研究 的关键部分。 目前已经存在的最优路径算法有d p s p 算法( 动态广度优先搜索算法) 、 l - d e q u e u e 算法、d i j k s t r a 算法、a 算法( 启发式搜索算法) ，现在就其中比较经 典的d i j k s t f a t 算法、a 算法做一分析。 1 2 3 1d i jk s tr a 算法 d i j k s t r a 算法是由e w d i j k s t r a 于1 9 5 9 年提出的一个适用于所有弧的权均 为非负的最短路算法，也是目前公认的求解最短路问题的最经典的算法。它可给 出从某指定顶点到图中其它所有顶点的最短路径，时间复杂度小于0 ( n2 ) ，其中n 为节点个数。d i j k s t r a 算法的主要思想是用逐点增长的方法构造一棵路径树，从 而得到从该树的根节点( 即指定节点) 到其它所有节点的最优路径。算法描述为： 1 设初始o p e n 表仅包含原节点，其费用值为0 ( g 值) ，c l o s e d 为空表，设其 他节点的费用为o o 。 2 若o p e n 表为空，则出错；否则，选取o p e n 表中具有最小g 值的节点，设为 最佳节点b e s t ，把b e s t 从o p e n 表移至c l o s e d 表中，然后根据本节点的后续路段牛 成b e s t 的后继节点，对于每一个后继节点n ，进行下列过程： 计算节点n 的费用：g ( i 3 ) = b e s t + 从b e s t 至0 n 的费用。 如果节点n 己与o p e n 表上的任一节点相同，判断n 是否具有较低的g 值，若 第一章绪论 是较低的g 值，用n 的费用代替o p e n 表中相同的节点费用，且将匹配节点的后向指 针指向b f s t 节点。 如果节点n 已与c l o s e d 表上的任一节点相同，判断n 是否具有较低的g 值， 若是较低的g 值，用n 的费用代替c l o s e d 表中相同的节点费用，且将匹配节点的后 向指针指向b e s t 节点，并把该匹配节点移到o p e n 表。 如果n 不在o p e n 表上，也不在c l o s e d 表上，则把n 的后向指针指向b e s t 节点， 并把n 放入o p e n 中。 3 重复操作步骤 2 ，一直到c l o s e d 表为空集结束。由此求得按费用递增次 序排列的从原节点出发到其它各节点的最优路径序列。 d i j k s t r a 算法的优点是：适合于计算两点问的最短路径问题，只要路阻权值 为正，总能找到两点间的最短路径：其缺点是：算法的搜索速度受图的存储结构的 影响，时间复杂度小于0 ( n2 ) ，其中n 表示节点数，搜索速度快，则图的存储空间 就小；反之，图的存储空间大，则会降低搜索速度。 1 2 3 2 启发式搜索( h e uris t ics e ar c h ) 算法a 算法 启发式搜索是一种尽可能基于现有信息的搜索策略，也就是说在搜索过程中 尽量利用目前已知的诸如迭代步数，以及从仞始状态和当前状态到目标状态估计 所需的费用等信息。 目前在路径优化领域，最流行的启发式搜索算法当属由h a r t ，n i ls s o n r a p h a e l 等人首先提出的a 算法。该算法的创新之处在于选择下一个被检查的节 点时引入了已知的全局信息，对当前节点距终点的距离做出估计，作为评价该节 点处于最优路线上的可能性的量度，这样就可以首先搜索可能性较大的节点，从 而提高了搜索过程的效率。 具体地，a 丰算法引入了当前节点j 的估计函数f ，当前节点j 的估计函数定义为 f ( j ) = g ( j ) 十h ( j ) 。其中g ( j ) 是从起点到当前节点j 的实际费用的量度，h ( j ) 是从 当前节点j 到终点的最小费用的估计。我们注意到若h ( j ) = o ，即没有利用任何全 局信息，这时a 算法就变成了普通的d i j k s t r a 算法。这说明普通的d i j k s t r a 算法 可看作a 算法的特殊情形。算法描述为： 1 设初始o p e n 表仅包含原节点，其费用值为0 ( 即f 值) ，c l o s e d 为空表，设 其他节点的费用为o o 。 2 若o p e n 表为空，则出错；否则，选取o p e n 表中具有最小f 值的节点，设为 最佳节点b e s t ，把b e s t 从o p e n 表移至c l o s e d 表，然后根据本节点的后续路段生成 b e s t 的后继节点，对于每一个后继节点n ，进行下列过程： 9 昆明理工大学顾+ 学位论义 计算节点n 的费用： 先计算节点n 的上一个b e s t 节点，设到达b e s t 的费用为x 1 ： 再利用式( 1 ) 计算b e s t 至i 节点n 的费用： f ( n ) - x 1 + 从b e s t 到r l 的时间 如果节点n 已与o p e n 表上的任一节点相同，判断n 是否具有较低的t 值，若 是较低的t 值，用n 的费用代替o p e n 表中相同的节点费用，且将匹配节点的后向指 针指向b e s t 节点。 如果节点n 已与c l o s e d 表上的任一节点相同，判断n 是否具有较低的t 值， 若是较低的t 值，用n 的费用代替c l o s e d 表中相同的节点费用，且将匹配节点的后 向指针指向b e s t 节点，并把该匹配节点移到o p e n 表。 如果n 不在o p e n 表上，也不在c l o s e d 表上，则把n 的后向指针指向b e s t 节点， 并把n 放入o p e n 中，计算节点n 的估价函数： f ( r 1 ) = g ( n ) + h ( n ) ： 重复操作步骤 2 ，一直到c l o s e d 表为空集结束。由此求得按费用递增次 序排列的从原节点出发到其它各节点的最优路径序列。 a 算法占用的存储空间少于d i j k s t r a 算法若将节点的平均出度( 即所有节 点出度的平均值) 记为b ，从起点到终点的最短路径的搜索深度( 即搜索算法为了 寻找最优解而必须遍历的树的层数) 记为d ，则a 十算法的时间复杂度为0 ( b 。) 。因 此，a 十算法是一种较为合理有效的搜索算法。 1 3 本文研究的内容 针对目前电子导航地图中存在的问题，考虑现有的研究条件，主要进行了以 下几个方面的工作： 1 ) 建立显示用的电子地图。 要研究电子导航地图的各种功能，必须首先建立可显示的电子地图，可以利 用已存在的各大中城市的电子地图矢量化提取有用的信息，填充地图数据库。其 中地图数据库是实现电子地图功能的基础和关键。进而利用数据库中的数据自动 生成导航地图。 2 ) 电子地图的道路网络模型、道路网络数据库和兴趣点信息数据库的建立。 为了克服现有电子地图的缺点，方便地实现最优路径搜索和地图匹配、地址 匹配，本文提出一种新的路网模型，采用建立路网数据库和兴趣点信息数据库的 方法，将道路、兴趣点与地图联系起来，使电子地图不仅将信息固定在图面上， 含有原纸质地图、航片的信息，并且更为重要的是，还能加入诸如实时路况信息、 1 0 第一章绪论 交通管制信息等内容，便于实现电子地图的实时改正，这样电子地图所含的信息 就不是固定不变了，而是可以随着实时交通状况信息的变化而变化，使从这些信 息中得出的结论更切合实际。 3 ) 电子地图的功能。 可以按照兴趣点改变电子地图的比例尺显示地图( 即任意地放大和缩小地 图) 、有选择地显示地图信息、电了地图的漫游等。并且还可将必趣点的详细信 息等属性与地图关联起来，使得这些属性与地图上兴趣点的地理位置之间可以实 现双向查询。 4 ) 最优路径搜索。 电子导航地图的主要功能之一就是进行车辆导航，因此，必须能够提供车辆 从出发地到目的地的最优行驶路径。本文将研究最优路径搜索的数学方法和程序 实现，能够以行车距离最近、行车时间最短或者是这几项的组合查询等目标函数 计算交通路网上的任何两节点的最佳行车路线，并且在搜索过程中充分考虑了真 实道路中的交通限制要求，在静态最优路径查询的基础上提出动态搜索方法，更 符合实际情况，通过程序验证了结果的正确性。 ! 塑堡王查兰塑兰堡堡苎 第二章电子导航地图的生成 电子导航地图应具备以f 功能：地图显示、地图匹配、地址匹配、路径导航、 最优路径搜索等。它的制作技术的核心是建立空间数掘与属性数据( 例如：文字、 卢音、符号等) 之间的联系。 空间数据由表达图形结构的若干数据组成，主要是图形数据和关键坐标，反 映了事物地理空间位置的信息。图形数据只有在屏幕上显示出来时才方便操作和 修改，而文字等属性数据则一般表达为关系数据库的形式。这两种数据在表现方 式上有根本的不同，建立起它们之间有效的、准确的联系是构成电子地图信息系 统的基础和关键”】。 电子地图的属性数据的储存、管理、处理同一般信息系统，采用关系型数据 库管理系统如a c c e s s 、d b a s e 等进行储存。电子地图的空间数据库的储存有两种 方式：一种是栅格空间数据模型，另一种是矢量空间数据模型。用计算机处理栅 格空间数据存在两点不足之处：其一是存储量大，其二是放大后图形细节容易失 真。显然，栅格格式不适于做电子地图信息系统。所以矢量模型是目前用于导航 地图的主要空间数据模型。其建立的方式有两种，一是在现有的g i s 平台