（计算机应用技术专业论文）dijkstra最短路径优化算法在汽车导航的研究及实现.pdf

上海师范大学硕士学位毕业论文 摘要 随着计算机技术、导航定位技术和空间技术的快速发展，车载导航系统正成 为综合技术应用的热门领域之一。而作为汽车导航的核心部分的最短路径成为了 关键问题。本论文对汽车导航中最短路径的实现进行了优化，即对地图拓扑结构 进行处理，减少节点和路径的数目；针对具体的起点和终点，设定了合理的矩形 限制搜索区域，以减少晟短路径算法的搜索范围；利用搜索定向原理，以临时标 志节点到起点的距离与该节点到终点距离之和的最小作为搜索条件。在此基础 上，提出了基于矩形限制区域的二叉排序树的直线优化d i j k s t r a 最短路径算法。 本论文利用上海曙天信息数码科技有限公司的研究平台，设计和实现了汽车 电子导航教学实验系统。改进型d i j k s t r a 最短路径算法在此系统上运行和测试， 结果表明该算法能够提供高效率的搜索速度和较高的精度。此汽车导航教学实验 系统已经获得了专利权。申请号为2 0 0 5 2 0 0 4 7 2 0 1 3 ，申请人：上海曙天信息数 码科技有限公司，实用新型名称：汽车电子导航教学实验系统。 关键词：车辆导航；地理信息系统；全球定位系统；最短路径；d i j k s t r a 算法： s u p e r m a p ；电子地图 i l 圭塑壁蔓奎兰堡主堂些望些堡苎 a b s t r a c t t h ea u t o m o b i l e n a v i g a t i o ns y s t e m i s b e c o m i n g o n eo f t h e m u i t ；_ t e c h n o l o g i e sa p p l i c a t i o na r e a sw i t ht h ef a s td e v e l o p m e n to ft h ec o m p u t e r t e c h n o l o g y , n a v i g a t i o nt e c h n o l o g ya n ds p a c et e c h n o l o g y t h ei s s u eo fs h o r t e s t p a t ha st h ec o r ep a r to fn a v i g a t i o n ，b e c o m e so n eo ft h eh o tt o p i c s t h i st h e s i s d e a l sw i t ht h et o p o l o g yo ft h em a p ，r e d u c e st h en u m b e ro fn o d e sa n dp a t h s 。 a n dp r o v i d e sa na p p r o p r i a t er e c t a n g l eb o u n d a r ya c c o r d i n gt ot h es o u r c ea n d d e s t i n a t i o nt od e c r e a s et h es e a r c h i n ga r e a m a k i n gu s eo fd i r e c t i v es e a r c h i n g ， i tg e t st h er e s u l to ft h ed i s t a n c eb e t w e e nan o d ea n dt h es o u r c ep l u st h e d i s t a n c eb e t w e e nan o d ea n dt h ed e s t i n a t i o n t h e ni tc h o o s e st h em i n i m u m d i s t a n c ea st h er u l e b i n a r ys o r tt r e ei sa d o p t e dt og e n e r a t et h es h o r t e s tp a t h i tp r o p o s e sa no p t i m i z e dd i j k s t r as h o r t e s tp a t ha l g o r i t h mb a s e do nr e c t a n g l e b o u n d a r ya r e aa n db i n a r ys o r tt r e e f u r t h e r m o r e ，t h i sp a p e rp r o p o s e sa n dr e a l i z e st h ea u t o m o b i l en a v i g a t i o n t e a c h i n ge x p e r i m e n t a ls y s t e mb a s e do nr e s e a r c hp l a t f o r ms u p p o r t e db y s h a n g h a is h u w a nd i g i t a lt e c h n o l o g yl i m i t e dc o m p a n va n dt h ei m p r o v e d d i j k s t r as h o r f e s tp a t ha l g o r i t h mi st e s t e di nt h es y s t e m e x p e r i m e n t a lr e s u l t s s h o wt h a tt h ep r o p o s e da l g o r i t h m p r o v i d e s f a s t s e a r c h i n gs p e e d t h e e x p e r i m e n t a ls y s t e mi sp r o t e c t e db yp a t e n td g h tn o2 0 0 5 2 0 0 4 7 2 0 1 3 ，t i t l e d “a u t o m o b i l en a v i g a t i o nt e a c h i n ge x p e r i m e n t a ls y s t e m ”b y “s h a n g h a is h u l l a n d i g i t a lt e c h n o l o g yl i m f f e dc o m p a n y ”d a t e do n2 0 0 5 1 2 - 5 k e y w o r d ：a u t o m o b i l en a v i g a t i o n p o s i t i o n i n gs y s t e m ；s h o r t e s tp a t h ； m a p g e o g r a p h i ci n f o r m a t i o ns y s t e m ；g l o b a l d i j k s t r aa l g o r i t h m ；s u p e r m a p ；e l e c t r o n i c 上海师范大学硕士学位毕业论文 1 1 研究背景 第一章绪论 自1 9 9 4 年由美国国防部发布全球定位系统( g p s ) 以来，g p s 导航技术在民用市 场的应用发展非常迅速。尤其是近年来，随着计算机技术、电子技术、地理信息 技术、集成技术的快速发展，使g p s 导航技术得到了广泛的应用。特别是把g p s 定位的准确性与电子地图的直接性以及计算机的多媒体特性生动形象地结合在 一起的车载定位导航系统的出现，使导航技术进入了一一个全新的领域。“。 车载导航系统是集卫星定位技术( g p s ) 、地理信息系统( o i s ) 、数据库技术、 计算机技术等为一体的综合应用系统。车载导航系统以g p s 接收机作为地面接收 系统，城市电子地图为基础数据库，以可视化开发语言和g i s 软件为开发平台， 只需司机给出目标地址，系统就会实时规划出一条最佳、最短的路线，多条备选 路线。它使汽车由代步、运输工具变成了多功能、智能化的交通工具。汽车导航 系统虽然在我国起步较晚，但发展会相当快，预计2 0 0 6 年我国车载g p s 导航设备 销量近3 5 万台，配置率将超过5 o 。 最短路径是导航的基本功能，是导航实现过程中必须要解决的问题。在实际 生活中，特别是一些应急系统，如公安系统的紧急出警和救助系统等，一般要求 尽快计算出到目的地点的最短路线，在行车过程中还需要实时给出车辆前方的行 驶路线，这就决定了最短路径问题的实现应该是高效率而且是最佳的。最短路径 的实现可以缩短路程，节省时间、人力和物力。 国内外大量专家学者都曾对最短路径问题进行过深入的研究和探讨。最短路 径问题可分为单源最短路径和全源最短路径两种懈1 ，其中单源最短路径问题在汽 车导航中更具有普遍意义。单源最短路径问题的算法有很多种，从早期的基于限 制条件的深度优先搜索算法与基于有向无环图的动态规划法，到后来d i j k s t r a 算法和a 幸算法等1 7 种“。由于这些算法主要诞生于计算机科学及运筹学领域， 在算法的设计过程中只考虑了抽象网络的拓扑特性，力求通过各种新型的计算机 数据结构和运筹学方法，从理论上减少算法的时间复杂度，而忽略了具体的网络 可能具有的空间分布特性臼3 1 。1 9 9 6 年f b e n j a mi nz h a n 等人使用实际交通网 上海师范大学硕士学位毕业论文 络对其中的1 5 种算法进行了测试。结果显示有3 种效果比较好，它们分别是： t q q 、d i ( a 以及d k d ”“。t q q 算法的基础是图增长理论，较适合于计算单源点到其 它所有点间的最短距离；后两种算法则是基于d i j k s t r a 的算法，更适合于计算 两点间的最短路径闯题。总体来说，这些算法采用的数据结构及其实现方法由于 受到当时计算机发展水平的限制，将空间存储问题放到了一个很重要的位置， 以牺牲适当的时间效率来换取空间的节省“。 汽车导航中的最短路径所使用的网络数据是基于电子地图生成的，它具有明 显的空间数据的特性。目前，空间存储问题已不是要考虑的主要问题，因此有必 要对已有的算法重新进行考虑并进行改进，可以用空间换时间来提高最短路径 算法的效率。 由于缺少汽车导航的研究条件，而国内目前还没有厂家推出类似的科研平 台，因此无法对导航系统的关键技术进行研究和探讨，最短路径算法也无法在导 航方面展开深入地研究。考虑到成本、使用对象等方面，本论文利用上海曙天信 息数码科技有限公司的科研环境，参与了设计和实现汽车电子导航教学实验系统 的全部过程。( 专利申请号：2 0 0 5 2 0 0 4 7 2 0 1 3 ) ，并在此系统之上进行了一系列的 研究，提出了一种基于矩形限制区域的二叉排序树直线优化d i j k s t r a 算法来生成 最短路径。由于导航系统的教学实验功能和本论文的主题无关，所以本论文不在 教学实验方面作深入的研究和探讨。 1 2 论文意义 随着经济水平的提高，汽车也越来越贴近人们的生活。但由于城市化的进程 导致道路的复杂度越来越高，交通严重拥挤和堵塞，汽车驾驶也越来越难。而汽 车导航系统的出现就能很大程度避免这种情况发生。汽车导航中的最短路径高性 能的优化可以达到节省时间、人力、物力，缩短路程的目的。 本课题立足于为驾驶员提供可靠、准确、可视化的导航定位和信息服务。使 车辆能够在陌生的地理环境中，随时了解自己所处的位置、环境信息，使驾驶员 能够及时的控制车辆。此外本论文的意义还有以下几个方面： 本论文针对最短路径算法在汽车导航中具体应用，提出一种基于矩形限 制区域的二叉排序树直线优化d i j k s t r a 算法来生成最短路径。论文的实 2 上海师范大学硕士学位毕业论文 验成果将为今后的类似开发提供借鉴； 研究成果可以推广到一般的道路网上面，更深一步可以扩充到其它管网 维护和抢修的最短路径问题； 促进我国汽车导航系统的发展和普及； 汽车电子导航教学实验系统已经申请专利，申请号：2 0 0 5 2 0 0 4 7 2 0 1 3 1 3 本文的研究内容 汽车导航将全球定位系统、地理信息系统、电子技术、计算机技术等有机的 结合起来。它与电子地图是密不可分的。汽车导航中的最短路径使用的网络数据 是直接从地图数据库中提取的。基于电子地图开发的方案有几种，综合考虑成本、 时间以及效率，本论文拟采用集成二次开发。集成二次开发是指利用专业的g i s 工具软件，如超图公司的s u p e r m a p 控件，以通用软件开发工具为开发平台进行 集成开发。这样可以充分利用6 1 s 软件实现对空间数据库的管理、分析，又可以 利用其它可视化开发语言的高效、方便等编程特点，大大提高应用系统的开发效 率。使用可视化软件开发工具开发出来的应用程序具有更好的外观效果，而且可 靠性好、易于移植、便于维护。 本论文主要研究了如下内容： 优化最短路径的实现：用户指定起始点和终点，系统给出最短路径。这是本 文的重点，也是难点。主要从地图的海量数据的处理，优化d i j k s t r a 算法， 数据结构实现上的改进等方面入手，提出了一种基于矩形限制区域的二叉排 序树直线优化d i j k s t r a 最短路径算法。此算法是在不影响用户最短路径需 求的情况下，对地图拓扑结构进行处理，减少节点和路径的数目。并针对具 体的起点，终点，设定合理的矩形限制搜索区域，以减少算法的搜索规模； 利用搜索定向原理，以临时标记节点到起点的距离与该节点到终点距离之和 的最小为搜索条件等等。 汽车电子导航教学实验系统的开发和实现。主要包括g p s 卫星导航数据的接 收和解析；g p s 信号在地图上定位；地图上周边信息的查询等等。 上海师范大学硕士学位毕业论文 1 4 论文的章节安排 第一章绪论，主要概述最短路径算法国内外发展现状，及论文研究内容和 意义等； 第二章g p s 定位原理和方法，主要论述g p s 全球定位系统原理及g p s 集成接 收机的定位原理等； 第三章g i s 地理信息系统，介绍了g i s 的组成，地图的结构等等； 第四章最短路径规划算法，本文的重点，也是难点。主要包括地图的海量 数据的处理，最短路径算法的改进等； 第五章汽车电子导航教学实验系统的设计与实现，主要包括平台的组成、 设计与实现； 第六章实验结果。主要对算法的精度和速度进行测量。 第七章总结，全文小结并对系统设计中不足提出一些改进思路。 4 上海师范大学硕士学位毕业论文 第二章g p s 定位原理和方法 2 1g p s 简介 汽车导航是基于全球定位系统( g l o b a lp o s i t i o n i n gs y s t e m ，简称6 p s ) 的。 g p s 是美国从本世纪7 0 年代开始研制，历时2 0 年，耗资2 0 0 亿美元，于1 9 9 4 年全面 建成，具有在海、陆、空全方位全天候的三维导航与定位能力的新一代卫星导航 与定位系统。这套系统覆盖全世界，整个地面接收系统完全被动接收信号。其基 本思想是由精确定位的卫星系统发布定位信号，而在这个卫星系统覆盖的范围内 的接收用户，将接收到的相关信号经过处理和运算，可以得到接收点的精确位置 坐标信息。这对于卫星、船舶、飞机的动态定位，勘探、大地测量、救援、跟踪 皤方面有重要的作用。 要完成g p s 信号定位功能，则需要全球定位系统的三个部分相互合作： 第一部分是g p s 卫星，由2 7 颗卫星组成，其中有3 颗是备用的。这些卫星均匀 图2 16 p s 卫星分布图 分布在2 0 2 万千米高的6 个轨道平面上，每个轨道 上4 颗卫星。轨道倾角为5 5 度，各个轨道平面之间 相距6 0 度，即轨道的升交点赤经各相差6 0 度。每个 轨道平面内各颗卫星之间的升交角距相差9 0 度，轨 道平面上的卫星比西边相邻轨道平面上的相应卫 星超前3 0 度倒。地球对恒星来说自转一周时，g p s 卫星绕地球运行二周，即绕地球一周的时间为1 2 恒 星时。卫星以1 1 4 , 时5 8 分的周期环绕地球运行，对于地面观测者来说，每天将提 前4 分钟见到同一颗g p s 卫星。位于地平线以上的卫星颗数随着时间和地点的不同 而不同，最少可见到4 颗，最多见至t j l l 颗。在用g p s 信号导航定位时，为了计算观 测点的三维坐标，必须观测4 颗g p s 卫星，称为定位星座。卫星以1 5 7 5 4 2 m h z 和 1 2 2 7 6 m h z 的频率发送导航信号，使得在任意时刻，地面上的任意一点的用户同 时观测到4 颗以上的卫星，并接收这些卫星的信号，可以确定4 个基本的导航参数： 经度、纬度、高度和时间。 第二部分是由一个主监控站、三个注入站和五个监控站组成的地面支撑系 上海师范大学硕士学位毕业论文 统。在导航定位中，首先必须知道卫星的位置。g p s 卫星是一动态已知点。位置 是由卫星星历，即描述卫星运动及其轨道的的参数，计算出来的。地面支撑系统 测量和计算每颗卫星的星历，并编辑成电文发送给卫星，再由卫星实时地播发给 用户。这就是卫星提供的广播星历”1 。卫星上的各种设备是否正常工作，以及卫 星是否一直沿着预定轨道运行，都要由地面设备进行监测和控制。地面监控系统 另一重要作用是保持各颗卫星处于同一时间，即标准g p s 时间系统“。 五个监控站均为无人职守的数据采集中心。监测站的任务是测量每颗卫星的 伪距和距离差，采集气象数据，并将观测数据传送给主控站。 主控站对地面黢测站实行全面的控制，检验注入卫星的导航电文是否正确 以及卫星是否将电文发给了g p s 用户系统。接收各监测站的g p s 卫星观测数据、卫 星工作状态数据、各监测站和注入站自身的工作状态数据。根据上述各类资料， 及时计算每颗卫星的导航电文，星历和卫星钟的改正参数等，并传送给注入站。 词时它还控制和协调监测站和注入站间的工作。 注入站将主控站计算出的卫星星历和卫星钟的改正参数等注入到卫星的内 存中。 第三部分是用户设备部分，目p g p s 信号接收机。它是用户与整个g p s 系统的接 l 1 。它的主要任务是：捕获到一定待测卫星的信号，对所接收到的g p s 信号进行变 换、放大和处理，以便测量出g p s 信号从卫星到接收机天线的传播时间，解译出 g p s 卫星所发送的导航电文，实时地计算出地面目标点的三维位置，甚至三维速 度和时间“。 空间部分和地面控制部分是由美国军方维护，- - 日- f 作，就昼夜不停地发送 导航定位信息，主要是保证卫星正常工作及其发送的信号准确无误。 2 2g p s 定位原理 e g p s 卫星、地面支撑系统和接收机三方面的协作下，地面目标即可定位。 g p s 定位的基本原理主要是根据高速运动的卫星瞬间位置作为已知的起算数据， 采用空间距离后方交会的方法，确定待测点的位置。简单地说，是利用几何与 物理的基本原理。首先假定卫星的位置已知，而且能准确测定目标所在地点a 至 卫星之间的距离，那么a 点一定是位于以卫星为中心、所测得距离为半径的圆球 上海师范大学硕士学位毕业论文 上。进一步，又测得点a 至另卫星的距离，则a 点一定处在前后两个圆球相交的 圆环上。测得与第三个卫星的距离，就可以确定a 点只能是在三个圆球相交的两 个点上。根据些地理知识，可以很容易排除其中一个不合理的位置“3 。以上 所说，要实现精确定位，就要解决两个问题： 其一是确知卫星的准确位置，这是由每颗卫星的星历提供的。所以正确接收 每个卫星的星历，就可确知卫星的准确位置。其二是要准确测定卫星至地球上目 标所在地点的距离。由于时间速度= 距离，卫星传播的信号是电波，电波传播 的速度是每秒钟三十万公里，所以只要知道卫星信号传到目标的时间，就能利用 速度乘时间等于距离这个公式，来求得距离。为了求出信号传播的时间，卫星会 传送一段叫做伪随机码的二进制电码。同时延迟g p s 接收机产生的伪随机码，使 接收机与卫星传来的码字同步，测得的延迟时间也就是卫星信号传n g p s 接收机 的时间。 两个问题都解决了，则a 点的位置信息就可以通过下面的公式获得： ( x 1 - x ) 2 + ( y l - x ) 2 + ( z 1 z ) 2 = d 1 2 ( x r x ) 2 + ( y 2 - y ) 2 + ( z 2 。z ) 2 = d 2 2 ( x r x ) 2 + ( y r y ) 2 + ( z r z ) 2 = d 3 2 x ，y z 是目标点的位置坐标； d 1 ，d 2 ，d 3 分别是3 颗卫星到目标点的距离， 可以通过c 瓦求得。t 【是卫星的信号到达接 收机所经历的时间； ( x l ，y i ，z 0 ( x 2 ，y 2 ，z 2 ) ( x 3 ，y 3 ，t o ) 分别是3 颗卫星的坐标； 通过这一组算式，可以计算出xy - z 匿2 2g p $ 定位图 以上是十分理想的情况，实际情况要复杂得多，例如：电波传播的速度，并 不总是一个常数；在通过电离层中电离子和对流层中水气的时候，会产生一定的 延迟，所以还要采取一些对策。一般可阻根据监测站收集的气象资料，再利用典 型的电离层和对流层模型来进行修正等等。 7 上海师范大学硕士学位毕业论文 2 3g p s 接收机的组成 g p s 接收机是定位系统中不可缺少的一个重要部分，同时也是用户可以直观 接触到的东西。世界各国的公司、研究机构陆续研制出各种类型的接收机。 g p s 接收机主要利用g p s 卫星发送的信号确定卫星在太空中的位置，并根据无 线电波传送的时间来计算它们间的距离。等计算出至少3 4 个卫星的相对位置 后，g p s 接收器就可以用三角学来算出自己的位置。g p s 接收机主要由天线单元和 接收单元两部分组成： 1 ) 天线单元由接收天线和前置放大器组成。前置放大器是关键性部件，要 求具有噪声系数小、增益高和动态范围大的特点。 2 ) 接收单元出信号信道单元、存储单元和计算与显示等单元组成： e t 信号信道单元，用于接收来自天线单元的信号。通常有1 - - 1 2 个信道，每 一信道在某一时刻只能跟踪一颖卫星。当此卫星被锁定后，便占据了这一通道。 b 存储单元，存储实时的各种数据，如原始观测量及计算结果。 c 计算和显示单元，用于根据采集到的卫星星历，伪距观测值计算三维坐标 和速度。 2 4n 舰a - 0 1 8 3 本系统使用的g p s 接收仪是u b l o x 的t i m l c ，属于导航型接收机4 3 。它采用的 是n l d e a - 0 1 8 3 数据格式。大部分的g p s 接收器都具有美国国家海洋电子协会 ( n a t i o n a lm a r i n ee l e c t r o n i c sa s s o c i a t i o n ，n m e a ) 所制定的标准规格，这一 标准规格定了所有航海电子仪器间的通讯标准，包含传输数据的格式以及传输数 据的通讯协议。n m e a 规格有0 1 8 0 、0 1 8 2 及0 1 8 3 - 一种，前两种已快被第三种取代， 因为第三种规格( n m e a - 0 1 8 3 ) 在电子传输的实体接口上，包含了n 她a 一0 1 8 0 与 n m e a 一0 1 8 2 所订定的r s 一2 3 2 接口规格，又多加了e i 肛4 2 2 的工业标准接口。而且在 所传输的数据内容方面，也比n m e a - 0 1 8 0 、n m e a - 0 1 8 2 多吲。 n m e a 格式所传的数据是架构在美国国家标准信息交换码( a s c i i ) 之上，它 是以传输句子的方式传输数据。每一个句子以“$ ”当作开头，紧跟着$ 后的五个 字符解释了信息的基本类型；第二、三个字符为传输设备的识别码，例如“g p ” 8 上海师范大学硕士学位毕业论文 为g p s 接收器；四、五、六个字符为要传输的句子名称，例如“g g a ”为全球定 位系统固定数据( g l o b a lp o s i t i o n i n gs y s t e mf i xd a t a ) 的意思。而以回车换行 为终止，句子长度不定，最长可达8 2 个字符。而句子中的字段以逗号“，”分隔。 n m e a 一0 1 8 3 的信息格式一般如下所示，数据为8 位a s c i i 码1 ： $ x x x ) ( x ，d f i ，d f 2 ， c r l f 比如： $ g p g g a ，0 8 1 2 4 3 ，3 1 1 3 0 5 7 ，n ，1 2 1 2 3 8 6 2 ，e ，2 ，0 7 ，6 6 0 ，1 8 1 ，m 0 8 1 2 4 3 为数据在格林威治时间八点十二分四十三秒传输，北京时问还要加上 8 4 , 对； 3 1 1 3 0 5 7 ，n 为北纬三十一度十三点零五七分； 1 2 1 2 3 8 6 2 ，e 为东经一百二十一度二十三点八六二分； 2 表示带差分定位信息； 0 7 表示可以使用的卫星数； 6 6 0 表示精度百分比； 1 8 1 表示海平面高度。 n m e a 一0 1 8 3 通常采用两种界面，b p r s - 2 3 2 与e i a 一4 2 2 界面，一般个人计算机都 配有双端口m r s 一2 3 2 界面卡，使用者仅需自行撰写界面程序或是利用软件包，就 可以得到接收器传回的数据。 9 上海师范大学硕士学位毕业论文 第三章g i s 地理信息系统 3 1g i s 简介 地理信息系统( g e o g r a p h i ci n f o r m a t i o ns y s t e m ，简称g i s ) 是汽车导航缺一 不可的组成部分，它是- - n 综合的新兴信息科学技术和产业。g i s 是测绘学、地 理学、空间科学、生态环境学、信息学、计算机科学、管理学、人工智能与网络 通讯技术等领域的边缘交叉科学，是以这些学科为基础技术平台，用各种现代化 的方法来采集、存储、管理、分析、显示和应用与蹩个地球表面空间和地理分布 有关的数据信息的信息系统”3 。随着技术的发展和社会需求的增大，g i s 应用日 趋广泛，凡是涉及空间信息分布的地方都可以应用到g i s ，g i s 已经广泛地渗透 到人们的日常生活中。现在它和数据库、信息处理、通信等技术一样，已经成为 信息技术的重要组成部分。 g i s 从总体上可以分为应用型地理信息系统和工具型地理信息系统两种“， 工具型g i s 是指具有图形图像数字化、存储管理、查询检索、分析运算和多种输 出等地理信息系统基本功能的软件包，它常被用作应用型g i s 的系统开发平台。 应用型g i s 是在特定的工具型g i s 基础上，经过二次开发而得到的适合于一定应用 目的的g i s 系统，因此，它基本继承了工具型g i s 所提供的所有基本功能。对于应 用型g i s ，根据其应用领域、使用的数据模型、内容又有不同的分类。1 。 3 2g i s 的组成及功能 g i s 由五个主要的元素所构成：硬件、软件、 数据、人员和方法彻。 硬件是g i s 所操作的计算机。包括中央计算 机服务器，桌面计算机，单片机以及网络环境 等等。 g i s 软件提供所需的存储、分析和显示地理 信息的功能模块和工具。主要的软件部件有： 图3 1 g i s 的组成1 0 上海师范大学硕士学位毕业论文 输入和处理地理信息数据的工具；数据库管理系统( d b m s ) ；支持地理查询、分析 和视觉化的工具；容易使用这些工具的图形化界面( g u i ) 。g i s 软件技术体系主要 指g i s 软件的组织方式。从发展历程看，g i s 软件技术体系可以划分为六个阶段， 即：6 i s 模块、集成式g i s 、模块化g i s 、核心式g i s 、组件式g i s 和万维网g i s 。 目前比较流行的是组件式6 i s 和万维网g i s 。 数据是g i s 系统中最重要的部件。g i s 将把空间数据和其他数据源的数据集成 在一起，并使用数据库管理系统来管理空间数据。 g i s 的人员范围包括设计和维护系统的技术专家，以及使用该系统并完成他 们每天工作的人员。 6 t s 的功能包括空间数据基本处理功能和高级空问分析功能两部分。1 。基本处 理功能包括：数据的输入、数据处 理、图形处理与交互显示、数据 的存储与组织等。高级空间分析 功能是g i s 的核心功能0 1 ，它也是 地理信息系统与其它计算机系统 的根本区别。地理信息系统的空 图3 2g i s 空间拓扑叠加、模型分析 间分析可分为三个不同的层次： 空间检索、空问拓扑叠加分析、空间模型分析。空间检索就是在一定范围内查找 出目标的位置，并标志出来，比如查找上海师范大学的位置。不同数据层的综合 方法叫做叠加，它可以将多个数据集集成在一起。空间模型分析则是对空间的模 型分析可能出现或者发展的情况，比如徐家汇附近有多少上海银行。 3 3 地图 运用地理信息系统( g i s ) 和关系数据库管理系统可以建立电子地图。电子地 图在整个汽车导航应用体系中起到核心的作用，是汽车导航的基本数据库。通常 电子地图由记录实际地物的地理数据和与实际地物相关的标识信息以及各类附 加信息组成。也就是说，电子地图数据主要涉及到空间数据和属性数据两大类， 空间数据又称几何数据，是用来描述空间实体的位置，形态，大小和空间分布等 特征的数据。具体又可以细分为道路形状数据、背景数据、拓扑数据。道路形状 上海师范大学硕士学位毕业论文 数据主要记录与道路相关的精确地理位置、路面形状、道路隔离带、相应的附属 设施等。它必须准确如实地反映真实世界的具体情况，为其它类型的数据提供空 间基础，是电子地图与客观世界和各种导航应用功能相联系的纽带。背景数据既 包括了植被、水系、行政区划等现实意义上的背景信息，也包括各类与智能导航 相关的实时交通信息。背景信息的提供优化了地图的显示，满足了实对网络路径 分析的需要。拓扑数据定义了电子地图中各种地物间的相互关系，包括拓扑联接、 拓扑相邻、拓扑包含等。拓扑数据的定义使电子地图中的各类数据在内涵上有了 关联，使地图数据在语义和概念上更加完整，也更符合客观现实，为电子地图数 据自身完备性检查、网络路径分析和实现交通信息处理提供了便利。”。属性数据 主要包括专题属性数据和时域数据，它是对空间数据的语义描述，是属于一定实 体、描述其特征的定性或定量指标。在移动g i s 中，空间数据主要用于空间信息 的可视化显示，属性数据主要用于信息查询”1 。 电子地图从数据格式上可以分为矢量地图和栅格地图。这里的矢量和栅格之 分主要是针对于道路形状数据和背景数据中与地物相关部分而言，前者用于地图 缩放、路径计算分析等场合，而后者则主要用于固定比例尺地图的显示。同时， 根据电子地图应用场合的不同，也可将其划分为车载导航地图、应用于监控跟踪 的电子地图、用于导游目的的手持式电子地图、用于智能交通全局指挥调度的电 子地图等。这些不同的划分也对应着不同的电子地图数据构成要求和技术要求， 由此延伸出整个导航应用的完整体系。 地图通常要绘制在平面图纸上，由于地球椭球体表面是曲面，因此制图时首 先要把曲面展为平面。所以要采用特殊的方法将曲面展开，这就是地图投影理论。 其基本原理就是：因为球面上一点的位置决定于它的经纬度，所以实际投影时是 先将一些经纬线的交点展绘在平面上，再将相同的经纬度的点连成经线，相同的 纬度的点连成纬线，构成经纬网。有了经纬网以后，就可以将球面上的点，按其 经纬度展绘在平面上相应的位置处。通过特定的数学方程式将经纬坐标( a ，妒) 转 换为平面坐标( x ，y ) 。从三维坐标转换为二维坐标时总会出现扭曲变形，地图投 影就是用来减小这种变形的“。 我国出版的世界地图多采用等差分纬线多圆锥投影，这对于表现我国形状以 及与四邻的对比关系较好，但投影的边缘地区变形较大。对东、西半球地图常选 1 2 上海师范大学硕士学位毕业论文 用横轴方位投影，南、北半球图选用正轴方位投影，水、陆半球图则选用斜轴方 位投影。 本论文采用的地图是按照国家测绘局标准制定的公司购买的，迪圈结构是文 件+ 数据库混合存储方式。包括两个文件，其中扩展名为s d b 的文件存储空间 数据，采用o l e 复合文档技术存储数据的“”；扩展名为s d d 的文件为属性数据库， 采用a c c e s s 的m d b 数据库格式存储属性数据。 上海师范大学硕士学位毕业论文 第四章路线规划之最短路径 4 1 路径规划简介 路径规划问题是汽车导航的一个基本功能，是实现导航功能的前提条件。路 径规划可以分为静态路径规划和动态路径规划“。静态路径规划是以静态道路交 通信息，如行车道路的距离、固定的交通管理信息等，作为路径规划的权，以行 车距离最短作为规划准则的一种最优路径规划方法哳1 。动态路径规划是以动态交 通地理信息来确定路权大小，主要以行驶时间最少作为规划准则的一种路径规划 方法，即需要在静态路径规划基础上考虑路况、道路拥挤等因素。 由于动态路径规划需要以强大的城市交通综合信息系统作为后盾，而目前没 有相应的软硬件设施相配套，实现难度较大。所以本论文主要对静态路径规划的 最短路径进行研究和探讨。 最短路径问题一直是计算机科学、运筹学、交通工程学、地理信息学等学科 的一个研究热点。经典的图论与不断发展完善的计算机数据结构及算法的有效结 合使得新的最短路径算法不断涌现，各具特色”。由于这些算法主要诞生于计算 机科学及运筹学领域，在算法的设计过程中只考虑了抽象网络的拓扑特性，力求 通过各种新型的计算机数据结构和运筹学方法，从理论上减少算法的时间复杂 度，而忽略了具体的网络可能具有的空间分布特性。”。而这一点正是描述交通网 络结构的稀疏图与其它描述拓扑结构的平面图的根本区别所在。由于最短路径的 实现存在以上的一些问题，所以本论文主要从以下几点的处理来有效利用交通网 络空间分布特性对导航最短路径算法进行改进，阻减少算法的搜索规模，提高算 法运行效率。 1 、地图海量数据的处理； 2 、地图数据的选择； 3 、对d i j k s t r a 算法的改进； 4 、数据结构实现的改进。 针对城市道路网进行最短路径分析的研究不仅可以解决实际应用系统的应 1 4 上海师范大学硕士学位毕业论文 用需求，达到节省时间、人力、物力，缩短路程的目的，而且还可以很方便地将 其研究成果推广到一般的道路网上面，更深一步可以扩充到其它管网维护和抢修 的最短路径问题，毕竟它们都是建立在交通道路网上的。 4 2 地图处理 汽车导航是以城市电子地图为基础数据库，通常电子地图由复杂的记录实际 地物的地理数据和与实际地物相关的标识信息以及各类附加信息组成。地图的地 理数据主要是由城市交通枢纽组成，但重点为街道的集合。这些街道纵横交织形 成了错综复杂的城市交通网络。在本文中整个网络图将由交叉路口点和路段组 成，并定义交叉路口点为网络节点，路段为网络边。大部分城市交通网络图具有 以下特点： ( 1 ) 网络中节点和边的数目都远在1 0 0 个以上； ( 2 ) 在城市l ：1 0 0 0 0 ( 或以上) 的地图上，路段是近似直线或弧度数不大的， 特别在经过规划的现代大都市； ( 3 ) 边通常是双向可通的。 从以上城市交通网络的特点可以知道，地图的信息容量较大，在进行路径规 划时需要查找的数量比较多，这样会影响最短路径生成的速度。所以在用户容许 的范围内，应当对海量数据进行适当的处理，以减少最短路径搜索的节点和路径 的数量。对地图数据进行拓扑处理。这也是进行大多数空间数据查询与分析的基 础，是为以后的数据叠加分析、最短路径与最优路径分析等傲数据准备。s u p e r e u p 中内置了建立实体间的空间拓扑关系的功能，并提供完整的拓扑编辑与处理能 力，方便对地理空间数据进行拓扑错误检查和处理，主要包括： 弧段交叉和自交叉； 去除冗余顶点、薰复线； 去除短悬线和延伸长悬线； 4 2 ，1 拓扑数据处理 由于最短路径是在网络数据集上的应用。网络数据集中的地理对象在空间位 置上的相互关系，包括相邻、包含、相交、部分覆盖和相离五种基本拓扑关系。 上海师范大学硕士学位毕业论文 这些拓扑关系常常涉及到不同类型数据集之间的操作，这里主要处理网络线数据 集内各对象之间的拓扑关系，为以后进行各种各样的查询和分析操作做准备。下 面分别介绍拓扑建立以前拓扑数据处理的各步骤。 ( 1 ) 线对象相交 为了建立拓扑关系，首先要对线对象进行相交计算，并根据交点按顺序把线 对象分解成多个线对象，如图4 1 。一般而言，在二维坐标系统中凡是与其他线有 交点的线对象都需要从交点处打断，实际应用中情况可能有所不同。比如一条铁 路横跨一一条公路，从二维坐标上来看是相交的两个线对象，但是事实上不能在交 点处被分解。这时候需要做一些处理，将两个线对象分别赋予一个可以代表二者 在z 轴方向上相对位置的属性，可以是海拔高度值，也可以是一个代表相对位置 的数值。如果两个线对象的高度属性值不等，则不予计算交点“。 目疑首茸拥艇后 图4 1 线对象相交 ( 2 ) 剔除冗余点和重复线 拓扑关系建立过程中，如果在折线上某点附近存在两个点号不同的节点，且 两个节点之间的距离在一定的范围内，则这两个节点之一就构成为冗余节点。识 别并去掉冗余节点的操作被称为去冗余点“”，如图4 2 。这里的范围即为图4 5 中的f u z z y 容限，它指图层的精度，代表节点之间的最小距离。也就是说，在此 距离之内的两个点可以视为重合。f u z z y 容限一般为图层范围的1 1 0 0 0 0 1 1 0 0 0 0 0 0 之间。为确保地图精度，本系统默认为1 1 0 0 0 0 0 0 ，适于建立拓扑关系。 在建立拓扑结构时，有时会出现线对象的重合，重合的线对象只保留其中一个， 多余的应删除。 1 6 上海师范大学硕士学位毕业论文 8 0 酴冗余节点敖割除冠枭节点君 图4 2 冗余节点处理 ( 3 ) 悬线处理 地图的线对象中，当条线段的端点没有与任何其它线段的端点重合时称该 线段为悬线。按照长度则可以分为：短悬线和长悬线。短悬线指长度小于指定容 限的悬线；在一定容许范围内，短悬线可以被去掉，这种操作被称为去短悬线，如 图4 3 ；长悬线是指长度大于指定容限，且沿悬节点方向延伸指定容限长度后可 与其他线对象相交的悬线。长悬线可以被延长到另一条线上去，即到线的中间或 节点处，这种操作被称为长悬线延伸“。这里容限即为图4 5 中的d a n g l e 容限。 用于指定建立拓扑关系时可以删除的过头线的最大长度。系统默认d a n g l e 容限是 l 1 0 0 0 0 。 图4 3 短悬线处理 由于对电子地图进行了拓扑海量处理，特别是去除冗余节点和悬线的处理。 使得网络数据集中的节点数目比实际的要少，所以所获得的网络数据集是有损的 网络数据集。图4 4 和4 5 分别是拓扑数据处理的设定，为了保证最短路径的精度， 本试验采用了较小的容限设置，f u z z y 容限为1 1 0 0 0 0 0 0 ，d a n 9 1 e 容限是1 1 0 0 0 0 。 1 7 上海师范大学硕士学位毕业论文 4 2 3 地图数据的选择 圈4 4 拓扑数据箍理选项设定 图4 5 拓扑数据处理容限设定 地图拓扑数据的处理在一定程度上，减少了网络数据中的节点和路径的数 最。由于地图具有较大的地区广域性，而用户输入的起点和终点，以及经过的路 径，可能只是在地图的一个很小区域内。如果对整个地图的节点进行搜索，无疑 将增加算法的执行时间。 在汽车导航系统实现的初期阶段，最短路径实现策略采用的存储调用的原 理。即事先将各个路段节点之间的最短路径计算出来并存放在数据库中。当需要 上海师范大学硕士学位毕业论文 应用时，再根据用户输入的起点和终点在数据库中进行搜索。这样，可以在很短 的时间内输出结果，尤其是实施车辆调度时，效果更明显。一些地理信息系统， 例如国内的著名软件吉奥之星g e o s t a r 都是采取这种思想。但采取这种方法随着 网络节点的增加，物理存储空间将成级数的增加。更重要的是，交通道路的通行 率的数据是动态更新的，利用静态数据库查找，与实际情况不相符，缺乏实际意 义。这种方法只能起一点静态的指导意义。所以现在的导航系统几乎都采用动态 的在线算法，并利用多种手段来优化算法，减少响应时间，满足用户的要求。“。 如果在整个地图上动态查找，将含有很多实际不需要的网络的节点，这样算 法的执行的时问就会变得很长。为了提取实际应用的地图网络数据信息，本论文 采用矩形限制区域地图数据选择法。该方法主要是以用户输入的起点和终点为地 图数据选择的参考点，在此基础上，按照一定的规则扩大范围以生成最初的矩形 区域，并在这部分信息中查找最短路径，如果找到则结束，如果找不到最短路径 那么扩大地图网络数据信息，直到找到为止。 露 、 k 卜蟋 霭 蠡 嚣 。 o 赫。囊粤蜜 图4 5 地图矩形区域选择图 图4 6 中，s 点和z 点是起点和终点，系统将以横向长度口和纵向长度b 将分 别向外扩展，并最终在矩形区域中进行搜索。如果不能在该区域内得出一条最短 路径，则将递增地扩增，并在新的区域内进行搜索。其中的a 值常设为两条相邻 垂直大路间的平均距离，b 值设为两条相邻水平大路间的平均距离啪1 。 采用矩形限制区域地图数据选择法可以有效的缩小搜索范围，使得搜索节点 的数目明显的小于总节点数目，提高了搜索的速度。可是采用这种方法，可能使 1 9 卜攀 堍 爨髀 上海师范大学硕士学位毕业论文 系统找到的不是真正的最短路径，是有损的最短路径。 4 3d i j k s t r a 算法 最短路径问题是交通网络分析中的一个重要问题，也是交通地理信息系统中 的一个研究热点。它是资源分配、路线设计及分析等优化阀题的基础。 最短路径问题可分为单源最短路径问题及所有节点间最短路径问题，其中单 源最短路径更具有普遍意义。单源最短路径问题的算法有很多种，从早期的基于 限制条件的深度优先搜索算法、基于有向无环图