GPS车载导航系统路径规划设计

1、编 号：审定成绩：重庆邮电大学自考本科毕业论文专 业：通信工程论文题目：GPS车载导航系统路径规 划设计准考证号：011812303475姓 名：陈欧洛指导教师：贾俊霞工作单位或家庭地址：四川省盐亭县毛公乡铁垭村联系电话庆邮电大学自考毕业设计（论文）重庆邮电大学通信工程（本科）专业毕业设计（论文）任务书学生姓 名陈欧洛准考证号码011812303475专业通信工程指导教师姓名贾俊霞指导教师单位 重庆邮电大学一、设计题目：GPS车载导航系统路径规划设计二、设计（论文）要求：查阅GPS车载导航系统路径规划设计组建及相关资料和操作的方法， 研究了 车载导航系统的路径规划问题

2、。综合考虑并比较了多种最短路径的选择算法 ，并 对其优缺点进行了分析。主要研究要求：车载导航系统的发展历史和国内外研究现状，以及 GPS车载导航系统的组 成、功能、实现过程、路径规划算法以及地理信息系统的功能。并以Mao Info为工具，在路径规划系统中实现了地图的基本操作。三、设计（论文）的主要内容：本文重点研究了车载导航系统的路径规划问题。综合考虑并比较了多种最短路径的选择算法，并对其优缺点进行了分析。四、主要参考资料：1 唐依珠，郑茜颖 GPS车载多媒体导航系统的研究与开发 福州大学计算机 系,2000.12.2 张书毕，刘作才.基于GIS的GPS车辆监控系统设计与实现.测绘通报， 20

3、02-1.3 龚键雅.地理信息系统基础.北京：科学出版社，2001.4 赵伟华，章复嘉，梁红兵.车辆导航系统最优路径规划的研究与实现.杭州电子工业学院学报,2003. 理解SuperMap GIS .北京：北京超图地理信息技术有限公司.2003.2.6 SuperMap Objects入门教程.北京：北京超图地理信息技术有限公司.2003.2.7 毕军，付梦印,周培德.一种适于车辆导航系统的快速路径规划算法.北京理工大学学报，2002.2.8 乐阳，龚健雅.Dijkstra最短路径算法的一种高效率实现.武汉测绘科技大学学报.9 刘玉树，于东凯.指挥辅助决策技术一一动态路径规划.北京理工大学计算

4、机系，2001-1-3.10 修文群，池天河.城市地理信息系统.北京：北京希望电子出版社.11 果仁忠.空间分析.武汉：武汉测绘科技大学出版社,2000.1.12 曹元大，陈军，韩刚.车载导航系统路径规划与数据组织研究.北京理工大学计算机系，2002.指导教师（签名）部门负责人（签名）（校外设计请加盖单位公章） 年 月 日I重庆邮电大学自考毕业设计（论文）重庆邮电大学自考本科毕业设计（论文）开题报告考 号 011812303475姓 名陈欧洛导师单位重庆邮电大学导师姓名贾俊霞填表日期 2014 年2月iii重庆邮电大学自考毕业设计(论文)论文 题目GPS车载导航路径规划设计课 题 调 查 与

5、文 献 阅 读1、选题背景：交通事业的发展与我国社会主义现代化建设有着密不可分的关 系，并且对人们的日常生活有着巨大的影响。车辆作为主要的交通 工具，一方面促进了社会经济的快速发展，另一方面也不断的改善 着人们的生活。然而，近年来大幅增长的机动车辆使交通问题在日 常生活中愈加突出。交通拥堵、交通事故等社会冋题严重影响到交 通正常秩序乃至社会正常秩序。当前的交通问题是从发展中国家到 发达国家都正面临的一个重要的问题。以投入巨大资源修建道路这 种咼成本的方式解决交通拥挤冋题是杯水车薪。资金、环境、历史 原因等因素是改善道路交通成本更加高昂问题也更加复杂。所以， 修建道路这种方式的效果非常有限，无法

6、从根本上解决交通问题。近年来人们已经逐渐认识到单纯靠增加道路基础设施建设不可 能从根本上解决车辆的快速增长与交通设施滞后之间的突出矛盾。 只有在计算机、信息和通讯等高科技手段的辅助下充分利用现有的 道路基础设施，才是最合理最可行的方法。因此，人们从系统角度 提出了智能交通系统(ITS , In tellige nt Tran sport System)的概念，建立现代化的交通系统已然成为国家现代化的重要标志之一。 ITS是一个复杂的巨系统，包含了众多的子系统，其中车载导航系统 是最为重要的子系统之一，具有极大的市场前景和发展潜力。车载 导航系统的研制开发可规划分为相互关联的技术模块，路径规划则

7、 是其他功能模块运行的基础，同时包含了车载导航系统中的很多关 键技术。本文就是重点研究了车载导航系统的路径规划问题。2、技术现状：1.导航，即电子地图功能三维导航是GPS的首要功能，飞机、船舶、地面车辆以及步行 都可以利用导航接受器导航。(1)车辆导航：有专门提供GPS定位服务的公司，通过通信或图#重庆邮电大学自考毕业设计（论文）示为装有GPS接收终端的车辆进行导航服务。车载导航器可以收集 到各种路况信息，从而可以避免堵车，选择最佳路线快速行驶。（2）车船的管理、跟踪和调度：通过地面计算机终端，实时显示 出车船的实际位臵。监控中心的智能化调度管理软件可以根据工作 需要和车船的当前位臵来分配任务

8、调度管理，实现工作派遣和车辆 调度最佳化。2. 语言数字通信语言和数字通信合二为一，使用车载 GPS对讲设备的语言功能 与司机进行通话或使用本系统安装在移动设备的汉字液晶显示器进 行汉字消息收发对话。3. 反劫防盗报警可以对移动车辆进行全方位、不间断、高精度、实时动态监控， 利用无线通信设备将目标的位臵和其他信息传至主控中心，并在电 子地图上显示车辆的当前位臵和运行轨迹，从而随时掌握车辆的行 踪，为管理提供决策支持。在遇到抢劫、被盗等紧急情况时，可以 向主控中心发送报警信息，及时得到附近安全部门的支持。系统还 可以与公安110、急救120网络连接。不仅集成以前所有的单用途卫星系统，并且致力于更

9、广泛的用 途。该系统具有比其他导航系统优越的特性：（1）全能性，能在空 中、海洋、陆地等全球范围内进行导航、授时、定位及测速；（2）全球性，在全球的任何地点都可以进行定位；（3）全天候，白天黑 夜都可以工作。实践证明，GPS对人类活动影响极大，应用价值很高，该工程从根本 上解决了人类在地球上的导航问题和定位问题，可以满足不同用户 的要求。GPS技术作为一种新兴的导航技术，它具有以往的任何导航 技术所没有的巨大的优越性，无论是定位精度、服务提供实时性、 时间的精确性、全天候不间断性等等特点，都是任何别的导航技术 所不能比拟的。它刚一出现和投入使用，就极大的改变了人类的工 作和生活。随着全球定位系

10、统的不断改进，硬、软件的不断完善，V重庆邮电大学自考毕业设计（论文）应用领域正在不断地开拓，目前已遍及国民经济各种部门，并开始 逐步深入人们的日常生活。3、未来发展目前世界上很多国家大力开发 GPS的应用，形成了融合许多领 域的GPS产业。GPS产业的发展趋势呈现以下三方面特点：1. 随着微电子技术及信号处理技术的进步， 新的软硬件开发工具的出现，GPS技术水平越来越高。GPS技术从单点定位、相对定位 发展到差分定位、广域差分定位，从利用测码伪距定位、载波平滑 伪距定位到利用载波相位，从数据后处理到实时在航解算，定位精 度越来越高，速度越来越快。并行跟踪窄相关技术及高速DSP的采纳，使得GPS

11、定位实时数据更新率由通常的1s降低至0.1s，而新兴 的实时相位差分（RTK技术可使实时定位达到厘米乃至毫米级精度。 虚拟差分站（VRS技术更是增加了定位数据的完整性和可靠性。2. GPS技术的应用越来越广泛，与其他领域的融合也越来越密切。地理信息系统（GIS）利用GPS作为采集数据工具，与先进的无 线技术结合应用于交通领域，形成新兴的智能交通系统（ITS），大 大提高了效率，并在国民经济建设中发挥了越来越大的作用。经典 的惯性导航技术（INS）与GPS结合，形成新型组合导航系统，以最 优的价格和性能为陆海空提供导航服务。GPSS信组网技术的发展，使GPS成为未来通信必不可少的组成部分，为广泛

12、流行的位臵服务（LBS提供了极具竞争力的选择方案。与此同时，GPS与其他导航通信卫星之间的联合也逐步展开，如与前苏联（现由俄罗斯掌管） 的GLONASS星以及国际海事卫星INMARSATS合，组成未来的全球 导航系统（GNSS。如此种种，不胜枚举。总之，GPS技术已发展成 多领域、多模式、多用途、多机型的高新技术国际性产业，广泛应 用于海陆空在途导航、精密定位、精确授时、卫星定规、武器制导、 交通控制、灾害监测、大地测量、大气研究等多个领域，正如人们 所说，“ GPS的应用，禁受人类想象力的约束”。3. GPS不仅深入跨学科的领域，而且已渗透到人类生活的人文领域。随着GPS用的不断深入，许多工

13、程实际上已经离不开 GPSGPS 政策成为世界各国关注的焦点。GPS平行系统的酝酿及出现，促使美 国政府对GP&艮务的限制逐步取消。随着美国 GPS现代化计划的实 施，GPS国际化的趋势日趋明显。GPS各如现在司空见惯的电视、电 信系统一样，成为人们日常生活必不可少的组成部分。4、选题研究的方法文献研究法：查阅相关专业书籍，搜集相关文献，同时进行网络检索。在此 基础上整理、分析完成整个GPS车载导航系统路径规划的设计。 实践研究法：在查阅相关书籍和文献的基础上，通过对实物GPS车载导航系统 的认识和了解，更加深刻地理解该设计的方案和实施办法。、 、 、 、 、 、 12 3 12 3 理论分析

14、与实验方法理论分析：1、GPS导航系统的认识和理解。2、GPS系统结构的整体把握。3、路径规划的分析。实验方法：1、对GPS导航系统构建。2、路径的规划设计。3、运行测试与分析。注：此页不够可增加工 作 进 度 计 划7佥 h?0 写W阅 耨 撰 占W处 日3,晋 占。 准 整 対 导 稿， 月隹心并対 伽 诩 收* 提 文 辩 年行 并 论 昔 进R, 成 好 料 弋 稿 完 做 ： 资 Q 初 见， 字 关 近 的 意。文 签 相 文 改稿论 生 对 界 论 修宀归印 学 , 斗 写 的 ，打 求 的 撰 给式并 奕 巧 纲 师格丈 书 大 老及论 务If据 导容悉 任 根 指内熟 根 H

15、 七 根论二 周 哥 、 周 正 十 二Hr六 九修、 一、 一一、一 応 人 W - 第保第 第 第第第 1报 2仏3ao456 题 讨 修指导教师意见日月年 宀 签部门意见日月年 宀 签 人 责 负说明：1.开题报告工作是毕业设计的重要环节，务必高度重视。2.开题报告在毕业设计的第三周内完成，并由导师和导师所在部门负责 人签字。重庆邮电大学通信工程（本科）专业毕业设计（论文）指导教师意见指导教师评语：建议成绩（分数）指导教师（签名）年 月日重庆邮电大学通信工程（本科）专业毕业设计（论文）评阅教师意见评阅教师评语：建议成绩（分数）评阅教师（签名）年 月 日重庆邮电大学通信工程（本科）专业毕业

16、设计（论文）答辩记录-、学生介绍设计（论文）情况：二、提问及答辩情况:提问一: 答辩:提问二:答辩:13重庆邮电大学自考毕业设计（论文）15重庆邮电大学自考毕业设计（论文）提问三:答辩:提问四:答辩:提问五:答辩:录（签名）年 月 日#重庆邮电大学自考毕业设计（论文）重庆邮电大学通信工程（本科）专业毕业设计（论文）答辩小组意见答辩小组评语：答辩成绩（分数）（校外加盖单位公章）毕业设计总评成绩:指导教师给定 建议成绩（1）评阅教师给定 建议成绩（2）答辩小组给定 答辩成绩（3）毕业设计总评成绩(1)X 0.3 +( 2 )X 0.3 +( 3 )X 0.4答辩小组结论性意见:答辩小组负责人（签名

17、）院答辩委员会负责人（签名）（校外设计请加盖单位公章）年 月 日17重庆邮电大学自考毕业设计（论文）摘要随着私人汽车在中国的普及，车载导航仪成为了日常生活中必不可少的工 具。车载导航系统的路径规划的研究无论是从方便驾驶员出行，提高运输效率， 优化城市交通，还是在改造与提升交通管理系统上， 都对现代的交通道路起着十 分重要的影响，因此受到社会和政府部门的关注和大力支持。本论文介绍了车载导航系统的发展历史和国内外研究现状，以及GPS车载导航系统的组成、功能、实现过程、路径规划算法以及地理信息系统的功能。并以 Mao Info为工具，在路径规划系统中实现了地图的基本操作。本文重点研究了 车载导航系统

18、的路径规划问题。综合考虑并比较了多种最短路径的选择算法，并对其优缺点进行了分析。【关键词】：GPS GIS车载导航系统路径规划 Dijkstra算法-1 -重庆邮电大学自考毕业设计（论文）ABSTRACTWith the popularization of private cars in China , the navigators became the daily life of the necessary tools. The cars navigation system path planning research whether from convenient drivers trav

19、el to improve tran sport efficie ncy and optimize the urban traffic, or in the reform and improve traffic management system, all the way to moder n traffic plays a very importa nt in flue nee, and it is by society and gover nment departme nts of the atte nti on and support.This paper in troduces the

20、 developme nt history of the cars n avigati on system and research status from domestic and abroad. The structure, function and the realization of the whole system are dem on strated i n detail in this thesis. The GIS(Geographic Information System) theory is introduced .By using MapInfo software as

21、a supporting platform, basic operati on of map are realized. The algorithms of Route Pla nning are discussed in detail. Think over and compare many shortest path algorithms and prese nt a improved algorithm based on the orig inal Dijkstra algorithm in this thesis. It saves memory space and in crease

22、s efficie ncy.【Key words 】：GPS GIS Vehicle navigation System Route-Planning Dijkstra algorithm-# -重庆邮电大学自考毕业设计（论文）目录刖言1.第一章GPS车载导航系统结构与关键技术 2第一节车载导航系统的发展2第二节车载导航技术的总体结构和关键技术 3一、车载导航系统的总体结构3二、车载导航系统的关键技术3第三节车载导航系统结构分析及功能要求 4第四节系统的功能要求4.第二章 路径规划的分析及设计 .6.第一节导航电子地图数据库的设计6一、导航电子地图的数据结构与数据模型 6二、导航电子地图数据库

23、的设计原则 8三、导航电子地图数据库的结构设计与实现 8第二节 导航电子地图中道路网络的拓扑生成方法 10一、导航电子地图中道路网络的模型与储存 1 0二、折线道路网络的拓扑生成法 1.2第三节路径规划的分析及设计14一、路径规划的基础算法 14二、限制搜索区域的路径规划算法17三、基于分层道路网络的分层路径规划算法 1 9四、限制搜索区域的分层路径规划算法 21第三章 路径规划的优缺点 23第一节 算法的实验结果 23第二节算法实验结果的比对及优缺点分析 25结论27致谢29参考文献30-3 -重庆邮电大学自考毕业设计（论文）自20世纪后期以来，随着全球经济的深入发展，世界各国城市（尤其是大

24、城市）的人口和车辆持续增长，由于交通拥挤而造成的损失随之逐年增加。因而各国竞相投资修建交通设施，试图解决这一问题。但是车辆的增长速度远远高于 道路和其他交通设施的增长速度，由此带来的有目共睹的事实是道路交通系统的 复杂性和拥挤度的与日俱增。近年来人们已经逐渐认识到单纯依靠增加道路基础 设施建设不可能从根本上解决车辆的快速增长与交通设施滞后之间的突出矛盾。 只有在计算机、信息和通讯等高科技手段的辅助下充分利用现有的道路基础设 施，才是合理可行的方法。由此出现了建设智能交通系统（In tellige ntTransportation System, ITS的热潮。事实上，建立现代化的交通系统，已经

25、成为 国家现代化的重要标志之一。与此相关的一系列方法与技术也成为当今计算机科 学、地理信息科学等相关学科中的研究重点和热点。ITS是一个复杂的巨系统，包含了众多的子系统，其中车载导航系统是最为重要的子系统之一，具有极大的 市场前景和发展潜力。车载导航系统的研制开发可以划分为相互关联的技术模 块，其中的路径规划是其他功能模块运行的基础，包含了车载导航系统中的很多关键技术。由于车载导航系统对道路网络建模、实时路径计算等方面有着特别的 要求，在学术、技术上还存在着许多没有完全解决的问题。本文就是重点研究了车载导航系统的路径规划问题。1重庆邮电大学自考毕业设计（论文）第一章GPS车载导航系统结构与关键

26、技术第一节车载导航系统的发展车载导航系统的研究和发展在人类的文明史上已有相当长的历史，最古老、 最简单的导航方法是星历导航，人们通过观察天空上星星的位置变更来确定自己 的位置和前进方向。随着科学技术的高速发展，将先进的信息处理技术、数据通信技术、电子控制技术及计算机处理等技术集于一体的智能交通系统的研究是 21世纪现代运输管理体系的模式和发展方向。卫星定位技术（GPS）、地理信息系统（GIS）、遥感技术（RS）、数据库技术、计算机网络技术等科技技术的出现， 有效地解决了当前城市现代交通管理的诸多问题。目前，不管是在经济发达的欧洲、美国、日本，还是在经济正在快速发展的 中国和其他国家，车辆导航系

27、统都是各国政府的重要建设项目。美国公路局最早于20世纪60年代末期提出了一种电子路径引导系统 （ERGS）,这是一种具有无 线路径引导功能的导航系统，用于控制和疏导交通，但由于资金问题没有实现。 最终终于在80年代中期相继把先进的导航产品投入市场。日本从1971年开始研 究综合车辆交通控制系统计划（CACS），从19731978年，日本成功的组织了 一个叫做动态路径诱导的实验。 从20世纪80年代中期到90中期的10年间，相 继完成了路车间通信系统（RACS）、先进的管理交通信息控制系统（AMTICS ）、 交通信息通信系统（TICS）及智能车辆系统等研究，并推出了各种导航仪器。 欧洲也大量的

28、发行了自己的许多导航产品。我国的车载导航系统的发展始于20世纪80年代末期，虽然在自主引导型车载导航系统方面还没有非常成熟，但监 管控制型的导航产品已经接近成熟并开始使用。目前已有许多科学研究单位和公司从事这方面的开发应用。因此，GPS导航系统在交通管理以及运输方面是非常有前景的，并且能够带 动与其相关的通信技术、信息技术、 控制技术、多媒体技术和计算机应用技术的发展第二节 车载导航技术的总体结构和关键技术、车载导航系统的总体结构车载导航系统是由GPS终端、车载计算机、导航软件、显示器及 GIS软件 等组成的（如图1.1）。主要包括：GPS接收机，它接受卫星定位信号，确定车 辆当前所在的经纬度

29、信息。其主要功能是采集实时的位置信息，进行自身的定位， 不断的更新当前数据，为交通管理提供最新的数据信息。计算机，结合编程技术及地图数据，为用户提供了多媒体信息服务。 GIS电子地图，把地理数据以 图形的方式显示出来，提供了多种地图服务，为用户提供一个直观清晰的界面。 车载手机、寻呼机，提供与控制中心的通信手段，接受、发送各种数据、命令、 请求以及服务信息。图1.1车载导航系统的总体结构、车载导航系统的关键技术1. 数字地图：也称电子地图，是一个矢量化的地图，即该地图中应该包括地图上的基本对象的属性数据。它是 GPS导航系统和GIS的数据基础。典型的 数字地图的标准格式有 Mapinfo的MI

30、F/MID 文件，AutoCAD的DXF文件等。2. 地图匹配：即利用电子地图中高精度的道路位置信息来修正定位系统给 出的车辆位置信息，进一步提高车辆定位精度的技术。 一个完整的地图匹配过程 包括三个主要环节，即误差区域的确定、匹配道路的选择及定位结果的修正。3. 路径规划：路径规划是车辆导航系统必不可少的核心功能之一，也是实 现导航功能的前提条件。车辆导航系统的路径规划是帮助驾驶员在旅行前或旅行 中规划行驶路径的过程，它要解决的主要问题是在给定的数字道路地图中寻找从 出发地到目的地的最优路径，为满足实际要求，路径规划应具有快速性和最佳性。第三节车载导航系统结构分析及功能要求车载导航系统共分为

31、6个模块：1. 定位模块：采用全球定位系统（GPS）来实现车辆定位。2. 数字地图数据库模块：主要负责存储数字地图及信息。它主要包括了支持电子地图显示的地图数据库及用于路径引导的道路特征数据库，是导航和定位的基础。3地图匹配模块：又称地理编码，即通过给定的经纬度坐标确定地图上街 道的地址，或者相反的过称。4. 路径规划模块：帮助司机在车辆运行过程中，根据地图数据库模块所提 供的地图，按要求的条件快速生成任意两点之间的最佳驾驶路线。如果有条件利 用实时的交通信息，还应对驾驶路线及时调整以适应交通当前的状况。5路径导航模块：指挥司机按着路径规划模块计算出来的路线，并通过定 位系统引导车辆行驶。路径

32、行驶包括两个任务：一是产生行驶指令，任务是产生一个行驶指令列表使其遵循路径规划跟踪的路线。二是规划跟踪，任务是紧密监 视车辆所在的路段位置。这些信息通过人一一机接口，并以特殊的指令如视、听提供给司机。6.无线通信模块：可进一步改善系统的性能增加系统的功能，通过一个或 多个不同的通信设备，车载系统或交通管理系统能够接受实时交通信息或报告， 去辅助车辆定位和导航，以促进车载系统或整个公共网络工作的更加安全有效。第四节系统的功能要求车载导航系统的主要功能有：1. 定位功能：利用全球定位系统（GPS）来获取当前的定位信息并与地图进行匹配，从而决定车辆当前的所在然后以图形的方式显示出来。2. 最优路径搜

33、索功能：根据用户在地图上选取的任意两地，系统将进行实时计算，按照用户的需求规划从出发地到目的地的最佳行驶路径，并以醒目的方式将路径显示在电子地图上。3. 地图浏览功能：地图浏览包括缩放、移动等，用户可以在一定的放大级 上将地图进行缩小、放大、移动的操作。4信息查询功能：为用户提供所需的目标查询，如服务区、道路、学校、 医院、宾馆、餐馆等，用户可以根据自己的需要在电子地图上查询。查询的资料 可以通过文字、图形的方式在电子地图上显示其位置。车载导航系统是利用全球定位系统、地理信息系统、计算机和先进的通信技 术等，将实时的重要信息高效的提供给驾驶员，使其能够选择更优的路径驾驶， 具有很强的实用价值和

34、非常广阔的前景。 其中的路径规划是导航系统的一项关键 技术，是导航系统的基础部分。5重庆邮电大学自考毕业设计（论文）第二章路径规划的分析及设计第一节 导航电子地图数据库的设计、导航电子地图的数据结构与数据模型1常用导航电子地图数据模型与结构（1）空间数据结构空间数据结构包括矢量结构、栅格结构及矢量栅格一体化结构三种。 矢量结构该结构用空间坐标及其关系描述空间对象， 单个空间对象是图形数据的基本 逻辑单位。其优点是对图形数据表达良好、结构紧凑、冗余度低。缺点是数据结 构复杂，对软硬件要求高。根据数据结构中空间对象的组织形式与联系程度又分 为描述结构、整体多边形结构、对偶独立地图编码结构及ARC-

35、NODE结构。 栅格结构该结构用点的像素表示空间对象。 其优点是结构简单、显示速度快。缺点是 精度较差、网络拓扑建立困难。根据像素的存贮结构及空间单元不同， 具体又分 为栅格编码结构、嵌套结构、不规则结构等多种形式。 矢量栅格一体化结构该结构综合了两种结构的优点，在许多电子地图中得到了应用。（2）属性数据的数据模型目前，属性数据采用的模型有层次模型、网状模型和关系模型。 层次模型该模型的基本结构是树形结构。层次模型数据库系统是数据库领域发展最早 的一种，目前已基本不用，但其在数据库发展历史上有着重大的作用和影响，以后的模型均受其影响。 网状模型网状模型明显优于层次模型，数据显示和数据操作方法均

36、呈现高效、 成熟的 特点，但是，网状模型不足之处在于使用时涉及系统内部因素较多， 用户操作使 用不方便，数据模式与系统实现也甚不理想。 关系模型关系模型是完全不同于前两种模型的一种新的模型，前两种模型一般被称为 格式化模型，而关系模型一般称为非格式化模型，其基本结构是二维表，简称表（table）。二维表由表框架和元组组成，表框架由 n个属性（或称为列）组成， 而存放于框架内的每行数据称为元组（或称为行），因此，一张二维表是由一个 n元属性的框架及m个元组组成。关系模型中的操作是建立在二维表上的操作， 包括对一张表及多张表间的查询、删除、插入及修改等操作。2面向对象的整体数据结构面向对象的整体数

37、据模型是将面向对象 （object oriented）思想和面向对象的 分析设计方法应用到空间数据模型的设计中，将各种空间实体抽象为某一类具有公共属性的对象，如点、线、面等对象，每个具体的地理实体是该对象的一个实 例，具有自己的属性，各种对象分层管理，实现空间数据与属性数据的统一管理。面向对象的整体数据模型强调的是整体与面向对象的概念。它不仅将地理世界以实体为单位进行组织，而且将客观世界作为一个整体看待， 即每个实体不仅 自身具有空间特性和属性特性的联系，更重要的是它与其它实体之间同时还具有 逻辑上的语义联系，此外，它也具有时间属性。面向对象的方法为数据模型的建 立提供了四种数据抽象技术（分类

38、、概括、联合、聚集）和两种数据抽象工具（继 承和传播），利用这些技术所构造的数据模型要比传统的数据模型丰富的多，更 适用于定义复杂的地理实体和对复杂对象的直接操作。因此，面向对象的整体数据模型是一种有效的空间数据模型。面向对象的方法为描述复杂的空间信息提供了一种直观有效的方法。与传统的导航电子地图数据模型相比，面向对象的数据模型具有的优点是：结构清晰、 组织有序，所有空间实体都以对象的形式封装；可以定义和处理复杂的空间实体； 易于扩充和二次开发；面向对象的用户界面更便于用户操作和使用。二、导航电子地图数据库的设计原则在智能车辆导航系统中，导航电子地图工作于实时、多任务的环境，图形的 显示、刷新

39、、信息查询、拓扑关系等是数据结构设计必须考虑的重要因素。一般 设计导航电子地图数据库应遵循以下原则：图形结构简单：由于导航电子地图主要包含点、线、面等空间对象，简单的 图形结构具有数据量少、刷新快、图形剪裁方便等特点。冗余度小：小的地图数据冗余度将使地图信息查询、 路径搜索的速度都得以 提高，同时降低数据的储存空间。拓扑关系简单：简单明了的拓扑关系将缩短最优路径规划及地图匹配时间。空间信息查询速度快：好的数据结构将提高空间信息的查询速度。数据接口开放：电子地图中的非空间数据具有良好的数据接口，能够兼容商用的非空间数据库。三、导航电子地图数据库的结构设计与实现导航电子地图数据库是整个系统的基石，

40、系统中几乎所有的模块都直接或间 接的与其相关，其结构设计的好坏将直接影响整个系统的最终性能。综合考虑各 方面因素，采用三层结构模式，以便充分利用面向对象程序设计方法的特性， 使 各层之间保持低耦合、高内聚的特点，层与层之间以通过的接口方式保持通讯， 其层次结构如图2.1所示。7重庆邮电大学自考毕业设计（论文）接口层0 卩空间对象介属性数据核心层1f对象访问索引操作操作属性读写层1iF1OBJIDXDBF其他文件文件文件文件二进制文件读写模块导航电子地图数据库的层次结构图2.1第一层为接口层，包括空间对象与属性结构。该层为设计的数据库进行二次 开发提供了一系列的接口。应用软件设计人员可以调用该结

41、构访问数字地图文 件，并对地图对象和属性数据进行操作，例如属性数据的查询等。第二层为核心层，是实现整个数据库的关键部分，涉及到得数据结构和算法 在这部分实现。第三层为读写层，完成对二进制文件底层读写操作。系统的其他部分不能对 数据库文件直接进行操作。读写层抽象了对文件进行操作的特性，圭寸装了对磁盘 链的管理和读写操作等。图2.2给出了导航电子地图数据库实现流程，整个过程可以分为文件层、用户 层和接口层三部分。9重庆邮电大学自考毕业设计(论文)#重庆邮电大学自考毕业设计(论文)人机接口界面（地團显示、信息查询、路径规划及地囲匹配等功）用户层TP- rJrSaK|L(x, y).(x, y N)式

42、中：R w道路网络；Ns 道路网络的节点集；NR 道路网络中任意两节点间拓扑关系的集合；vx, y 节点x和y之间存在的一条弧；L(x, y)节点x和y之间的权值，节点和节点之间连接的权值可以用节点之间的集合长度或者其他费用来表示。根据实际交通网络的特点，我们作如下分析假设： 所有的编制都是直线。对于弯曲弧度较大的路段，可以通过在该路段上 插入一系列节点使该路段由一些弧度较小的路段构成，弧度较小的路段可以认为是一条边。如图2.3,节点1、2之间路段的弧度较大，在路段上加入节点 2,把 原来的路段分成两个弧度相对较小的路段。 边通常是双向可通的，边的权值为正值。 网络中有较多的节点和边。 和节点

43、相关联的边数为常数，且远小于网络中总的节点数。节点3图2.3 弧度较大的路段处理2.导航电子地图中道路网络的计算机存储计算机存储的是矢量化的道路网络，网络的存储结构是影响路径规划算法搜 索速度和事件复杂度的一个重要因素。一个简单直观的存储方法是对道路网络图 中的每一个节点进行编号，采用邻接表的链式存储结构。在邻接表中，对图的每个节点建立一个单链表，每个单链表都由表节点和表头节点构成。第i个单链表的w个表节点分别对应着和图中第i个节点相关联的w条边。链表的表头节点 以顺序结构形式存储，以便随机访问图中任一节点的单链表。因此，采用邻接表的链式存储结构，很容易找到和图中任一节点相关联的边。单链表的表

44、头节点和表节点的结构如图2.4所示，图中，Name：节点编号；Position：节点位置坐标； First:指向链表中的第一个表节点；Next:指向链表中的下一个表节点； Weight： 边的权值。NamePositionWeightNextNamePositionFirst表P点表头节点图2.4链表结构、折线道路网络的拓扑生成法1. 折线道路网络的组成特点折线道路网络组成的最大特点是，每一条道路都是由带有宽度值的折线段 （简称道路中心线）表示。有时，为了数据获取方便，也可能以近似的道路中心 线来表示。各种来源提供的实际数据使得折线道路网络中可能存在以下情况： 线段间的虚交特性，即两条实际相交

45、的路段，在给定的道路网络数据中却 不存在与交点对应的节点。如图 2.5（a）所示，路段AB与路段CD实际应相交 于节点0,而节点0并未出现在路段AB与路段CD的给定数据中。 线段间的虚段特性，即两条实际相交的路段，因其中一条路段偏短导致没 能相交。如图2.5 （b）所示，路段AB与路段CD实际应相交于节点B,而节点 B并未出现在路段CD的给定数据中，将节点B称为虚断点。 线段间的过交特性，即两条相交的路段，因其中一条路段偏长而导致过短 的毛刺路段出现。如图2.5（c）所示，路段AB与路段CD相交于节点O,过短 路段BO应该不存在，然而，节点B却出现在路段AB给定数据中，将节点B 称为过交点。

46、节点的冗余特性，一种情况是，实际应该是同一节点的点却存在多个相邻 的节点。如图2.5（d）所示，节点A、B、C、D实际表示的地图中的同一点，13重庆邮电大学自考毕业设计(论文)换言之，此时应该只用一个节点来表示地图中的该点，然而，给定的道路网络数据中却存在节点A、B、C、D ；另一种情况是，本来可以由两个节点表示的路段， 给定的道路网络数据中却存在其他节点，如图 2.5（e）所示，路段AB只需节点A和B便能在精度允许范围内准确表示，而实际数据中却包括节点C和D段间的虛交特性（b）线段间的虛断特 性（d瘁示同一点的多个节点可以压缩掉的中间节点图2.5 实际数据中折线道路网络的情况2折线道路网络拓

47、扑生成算法原理算法的原理可以简单的描述为：依据折线道路网络的组成特点及 Arc-Node 数据模型，由给定的折线道路网络数据生成表示其拓扑结构的 Arc-Node数据结 构。具体生成过称分为两步：第一步是完善给定的折线道路网络数据，即对前面介绍的道路网络的几种特 性进行相应的处理。具体的处理方法是：虚交时，将实际应该有的交点分别插入两条路段中，从而两条路段分裂成四条路段，如图2.5（ a）中，应将节点0分别插入路段AB和路段CD中，从而使路段AB与路段CD分裂成路段AO、0B、 CO和0D;虚断时，应以偏短路段延长线与另一路段的交点代替偏短路段中靠 近该交点节点，如图2.4 （b）中，应将路段

48、AB的节点B用路段AB的延长线与 路段CD之交点来代替；过交时，应该删除过短路段，如图 2.5（c）中，应将路 段0B删除，即将节点B从路段AB中删除；节点冗余时，如果是第一种情况， 应以冗余节点的中心点代替这些冗余点；如果是第二种情况，则应将所有的冗余节点删除，如图2.5（ d）中，应将A、B、C、D用它们的中心点来代替，该中 心点的纵横坐标分别为这些冗余节点纵横坐标的均值，如图2.5（ e）中，应将路段AB中的节点C和D删除而只保留节点A和B。第二步是在第一步的基础上，由完善以后的折线道路网络数据生成表示其拓 扑结构的Arc-Node数据结构，Arc-Node数据结构采用邻接表结构。第三节

49、路径规划的分析及设计路径规划是现代智能车辆导航的一项关键技术，是基于具有拓扑结构的道路 网络，在车辆行驶前或行驶过程中寻找出发点到目标点最优行车路线的过称。本节充分挖掘实际道路网络具有的各种特性，分别利用道路网络空间分布特性和道 路等级特性，设计了两种针对道路网络的启发式搜索策略，即方向搜索策略和分层搜索策略；利用所构造的搜索策略设计了三种不同的启发式搜索策略。一、路径规划的基础算法Dijkstra算法是设计各种路径规划的基础。本节简要的介绍Dijkstra算法的原理及特点，并给出它的两种具体实现方法，即邻接矩阵法和邻接节点法，作为后续几个路径规划算法的基础算法。1算法原理给定带权有向图G=(

50、V,E),其中V是包含n个节点的节点集，E是包含m条 弧的弧集，v,w是E中从v至w的弧，c v,w是弧v,w的非负权值，设 a,b是V中的节点，Pab=v0=a,v1, ,vn=b是V中由a到b的一条路径，则路径 Pab的权值总和TC(Pab)表示为：TC(Pab)=Ec(vi,vi+1) (i=1,2,，小-1)(2-1)所谓最短路径问题是指，在带权的有向图中寻找从指定起点到终点的一条权 值总和最小路径。如果把权值看成弧的长度(即距离)，则目标路径就是起点到 终点的距离最短的路径。为说明求解给定两点间最短路径的算法，我们先来讨论单源点的路径问题， 即给定带权的有向图(V,E)和原点v,求从

51、v到G中其余各节点的最短路径。为了 求解这一问题，Dijkstra提出了一种按路径长度递增次序来产生最短路径的 Dijkstra算法，其原理如下：首先，引进一个辅助向量D，它的每个分量D(i)表示当前所找到的从起始点v到每个重点Vi的最短路径的长度。D的初始状态为：若从v到Vi有弧，则D(i) 为弧上的权值；否则令 D(i)为。显然，长度为D(i)=Min D(i)|vi V的路径就 是从v出发的长度最短的一条路径，记为(v , vi)。假设S为已求得最短路径终点 的集合，则下一条最短路径(设其终点为x)或者是弧v , x,或者是中间只经过S中的节点而最后到达节点x的路径。这可用反证法来证明：

52、假设此路径上有 一个节点不在S中，则说明存在一条终点不在S而长度比路径更短的路径。事实 上这是不可能的。因为我们是按路径长度递增的次序来产生各条最短路的，故长度比此路径短的所有路径均已产生，它们的终点必定是在S中，即假设不成立。因此，在一般情况下，下一条长度次短的最短路径的长度必须是D(j)=Min D(i)|vi V-S(2-2)其中，D(i)或者是弧v, vi上的权值，或者是D(k)(v k S)和弧v k ,v I 上的权值之和。从以上对Dijkstra算法原理分析可以看出，其最大特点是在最短路径的求解 过程中搜索算法具有很大的盲目性，随时准备向其四面八方展开，最终的搜索区域基本上是以起

53、始点为原点，以起始点与目标点的连线长度为半径的一个圆。2. 算法实现(1) 邻接矩阵法t(j,k) v D(k)(3-6)则修改D(k)为D(k)= D(j)+cost(j,k)(3-7)步骤四，重复操作步骤二、步骤三共 n-1次，由此求得按路径长度递增次序 排列的从v出发到图上其余各节点的最短路径。以上算法求解的是从源点出发到其余各节点的最短路径。但是车辆导航系统 的路径规划只需要求解出从源点到指定终点的一条最短路径，并且要记下并在地图上显示该路径，因此要对以上算法做适当的修改。设指定终点为t,在步骤二中，如果发现vj=t，则算法终止，D(t)的值就是从源点v到终点t的最短路径 的距离。为了能记下路径，设置一个路径向量P,其中P(i)表示从源点到达i节点的最短路径上该点的前趋节点。算法结束前，可根据P找到从源点到终点t的最短路径上每个节点的前趋节点，从而得到从源点到终点t的最短路径。由于采用邻接矩阵法在解算最短路径时， 搜索算法假设道路网络中的任意一 个节点都和其他所有节点相邻接，因此导致其时间复杂度为0(n2),其中n为道路 网络的节点总数。(2) 邻接节点法