[参考]gps车载导航仪的路径规划研究

[参考]gps车载导航仪的路径规划研究 摘要 摘 要 随着私人汽车在中国的普及，车载导航仪成为了日常生活中必不可少的工具。车载导航系统的路径规划的研究无论是从方便驾驶员出行，提高运输效率，优化城市交通，还是在改造与提升交通管理系统上，都对现代的交通道路起着十分重要的影响，因此受到社会和政府部门的关注和大力支持。 本 论文 政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载 介绍了车载导航系统的发展历史和国内外研究现状，以及GPS车载导航系统的组成、功能、实现过程、路径规划算法以及地理信息系统的功能。并以MaoInfo为工具，在路径规划系统中实现了地图的基本操作。本文重点研究了车载导航系统的路径规划问题。综合考虑并比较了多种最短路径的选择算法,并对其优缺点进行了分析。 关键词:GPS GIS 车载导航系统 路径规划 Dijkstra算法 ABSTRACT ABSTRACT With the popularization of private cars in China ，the navigators became the daily life of the necessary tools. The car's navigation system path planning research whether from convenient drivers travel to improve transport efficiency and optimize the urban traffic, or in the reform and improve traffic management system, all the way to modern traffic plays a very important influence, and it is by society and government departments of the attention and support. This paper introduces the development history of the car's navigation system and research status from domestic and abroad.The structure, function and the realization of the whole system are demonstrated in detail in this thesis. The GIS(Geographic Information System) theory is introduced .By using MapInfo software as a supporting platform, basic operation of map are realized. The algorithms of Route Planning are discussed in detail. Think over and compare many shortest path algorithms and present a improved algorithm based on the original Dijkstra algorithm in this thesis. It saves memory space and increases efficiency. Keywords: GPS GIS Vehicle navigation System Route-Planning Dijkstra algorithm i 目录 目 录 第一章 绪论 ................................................. 1 1.1 研究背景与意义 ........................................................................................... 1 1.2 GPS导航系统的发展概况 ............................................................................ 1 1.1.1 GPS导航系统的发展历程 .................................................................... 2 1.1.2 GPS导航技术应用的发展趋势 ............................................................ 2 1.2 研究内容及安排 ........................................................................................... 3 1.2.1 研究的内容 ........................................................................................... 3 1.2.2 本文的安排 ........................................................................................... 4 第二章 GPS车载导航系统的结构与关键技术......................... 5 2.1 车载导航系统的发展 ................................................................................... 5 2.2 车载导航技术的总体结构和关键技术 ....................................................... 5 2.2.1 车载导航系统的总体结构 ................................................................... 6 2.2.2 车载导航系统的关键技术 ................................................................... 6 2.3 车载导航系统结构分析及功能要求 ........................................................... 7 2.4 系统的功能要求 ........................................................................................... 7 第三章 路径规划的分析及设计 ................................... 9 3.1 导航电子地图数据库的设计 ....................................................................... 9 3.1.1 导航电子地图的数据结构与数据模型 ............................................... 9 3.1.2 导航电子地图数据库的设计原则 ..................................................... 10 3.1.3 导航电子地图数据库的结构设计与实现 ..........................................11 3.2 导航电子地图中道路网络的拓扑生成方法 ............................................. 12 3.2.1 导航电子地图中道路网络的模型与储存 ......................................... 12 3.2.2 折线道路网络的拓扑生成法 ............................................................. 14 3.3 路径规划的分析及设计 ............................................................................. 16 ii 目录 3.3.1 路径规划的基础算法..........................................................................16 3.3.2 限制搜索区域的路径规划算法..........................................................20 3.3.3 基于分层道路网络的分层路径规划算法..........................................22 3.3.4 限制搜索区域的分层路径规划算法..................................................23 第四章 路径规划的优缺点分析 ..................................25 4.1 算法的实验结果..........................................................................................25 4.2 算法实验结果的比对及优缺点分析..........................................................26 第五章 结论 ................................................29 5.1 论文小结......................................................................................................29 5.2 路径规划系统的展望..................................................................................29 致 谢 ....................................................31 参考文献 ....................................................33 1 第一章 绪论 第一章 绪论 1.1 研究背景与意义 交通事业的发展与我国社会主义现代化建设有着密不可分的关系，并且对人们的日常生活有着巨大的影响。车辆作为主要的交通工具，一方面促进了社会经济的快速发展，另一方面也不断的改善着人们的生活，提高了人们的生活质量。然而，近年来大幅增长的机动车辆使交通问题在日常生活中愈加突出。交通拥堵、交通事故等社会问题严重影响到交通正常秩序乃至社会正常秩序。当前的交通问题是全世界国家，从发展中国家到发展国家都正面临的一个重要的问题。以投入巨大资源修建道路这种高成本的方式解决交通拥挤问题是杯水车薪。资金、环境、历史原因等因素是改善道路交通成本更加高昂问题也更加复杂。所以，修建道路这种方式的效果非常有限，无法从根本上解决交通问题。 为了缓解交通问题，从上世纪60年代起，发达国家开始着手研究解决交通问题的可行办法。制定交通规划、使用信号灯等措施缓解了交通问题，但不足以高效的解决交通问题，仍无法解决快速增长的车辆需要，必须从系统观点整体上综合考虑解决。 近年来人们已经逐渐认识到单纯靠增加道路基础设施建设不可能从根本上解决车辆的快速增长与交通设施滞后之间的突出矛盾。只有在计算机、信息和通讯等高科技手段的辅助下充分利用现有的道路基础设施，才是最合理最可行的方法。因此，人们从系统角度提出了智能交通系统(ITS,Itelligent Transport System)的概念，建立现代化的交通系统已然成为国家现代化的重要标志之一。 ITS是一个复杂的巨系统，包含了众多的子系统，其中车载导航系统是最为重要的子系统之一，具有极大的市场前景和发展潜力。车载导航系统的研制开发可规划分为相互关联的技术模块，路径规划则是其他功能模块运行的基础，同时包含了车载导航系统中的很多关键技术。本文就是重点研究了车载导航系统的路径规划问题。 1.2 GPS导航系统的发展概况 2 GPS车载导航仪的路径规划研究 1.1.1 GPS导航系统的发展历程 在很早的时候就已经有导航技术的应用。指南针和记里鼓车等古代时期的导航设备被认为是现代磁罗盘和差分里程计的原型，是已知最早的导航工具。 1957年10月世界上第一颗卫星发射成功后，科学家开始进行卫星定位和导航的研究工作。1964年1月世界上第一个卫星导航系统研制成功即“子午卫星系统”，但由于该系统存在较大的缺陷，且不能满足当前实时、动态、精确的定位需要，所以终止了该系统的研究。 20世纪60年代末，美国开始着手研制新的卫星导航系统，以满足陆海空三军和民用部对导航的高要求。1973,1978年，发射了4颗试验卫星，建立了地面跟踪网，研制了地面接收机;1979年,1984年又陆续发射了7颗Block?试验卫星，研制了各种用途的接收机，包括导航型和测地型接收机;1985,1993年发射Block?和Block?A;直到1994年顺利完成了24颗卫星的布设，这就是“导航卫星授时与测距全球定位系统”(Navigation Satellite Timing and Raining/ Global Positioning System,NAVSTAR,GPS),简称全球定位系统(GPS)。 GPS主要由三大部分组成:?空间卫星部分:21颗工作卫星，3颗备用卫星;?地面控制部分:1个主控站，3个注入站，5个监测站;?用户接收机部分:接受GPS卫星发射信号，以获得必要的导航和定位信息，经数据处理，完成导航和定位工作，GPS接收机硬件一般由主机、天线和电源三部分组成。 全球定位系统不仅集成以前所有的单用途卫星系统，并且致力于更广泛的用途。该系统具有比其他导航系统优越的特性:?全能性，能在空中、海洋、陆地等全球范围内进行导航、授时、定位及测速;?全球性，在全球的任何地点都可以进行定位;?全天候，白天黑夜都可以工作。 实践证明，GPS对人类活动影响极大，应用价值很高，该工程从根本上解决了人类在地球上的导航问题和定位问题，可以满足不同用户的要求。 1.1.2 GPS导航技术应用的发展趋势 目前世界上很多国家大力开发GPS的应用，形成了融合许多领域的GPS产业。GPS产业的发展趋势呈现以下三方面特点: ? 随着微电子技术及信号处理技术的进步，新的软硬件开发工具的出现，GPS 3 第一章 绪论 技术水平越来越高。GPS技术从单点定位、相对定位发展到差分定位、广域差分定位，从利用测码伪距定位、载波平滑伪距定位到利用载波相位，从数据后处理到实时在航解算，定位精度越来越高，速度越来越快。并行跟踪窄相关技术及高速DSP的采纳，使得GPS定位实时数据更新率由通常的1s降低至0.1s，而新兴的实时相位差分(RTK)技术可使实时定位达到厘米乃至毫米级精度。虚拟差分站(VRS)技术更是增加了定位数据的完整性和可靠性。 ? GPS技术的应用越来越广泛，与其他领域的融合也越来越密切。地理信息系统(GIS)利用GPS作为采集数据工具，与先进的无线技术结合应用于交通领域，形成新兴的智能交通系统(ITS)，大大提高了效率，并在国民经济建设中发挥了越来越大的作用。经典的惯性导航技术(INS)与GPS结合，形成新型组合导航系统，以最优的价格和性能为陆海空提供导航服务。GPS通信组网技术的发展，使GPS成为未来通信必不可少的组成部分，为广泛流行的位置服务(LBS)提供了极具竞争力的选择 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 。与此同时，GPS与其他导航通信卫星之间的联合也逐步展开，如与前苏联(现由俄罗斯掌管)的GLONASS卫星以及国际海事卫星INMARSAT联合，组成未来的全球导航系统(GNSS)。如此种种，不胜枚举。总之，GPS技术已发展成多领域、多模式、多用途、多机型的高新技术国际性产业，广泛应用于海陆空在途导航、精密定位、精确授时、卫星定规、武器制导、交通控制、灾害监测、大地测量、大气研究等多个领域，正如人们所说，“GPS的应用，禁受人类想象力的约束”。 ? GPS不仅深入跨学科的领域，而且已渗透到人类生活的人文领域。随着GPS应用的不断深入，许多工程实际上已经离不开GPS，GPS政策成为世界各国关注的焦点。GPS平行系统的酝酿及出现，促使美国政府对GPS服务的限制逐步取消。随着美国GPS现代化 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 的实施，GPS国际化的趋势日趋明显。GPS将如现在司空见惯的电视、电信系统一样，成为人们日常生活必不可少的组成部分。 1.2 研究内容及安排 1.2.1 研究的内容 车载导航系统是集成应用了自动车辆定位技术、地理信息系统技术、数据库技术、多媒体技术和现代通信技术等的高科技综合系统;是一个为客户提供定位、 4 GPS车载导航仪的路径规划研究 路径规划、路径引导等多种服务的复杂系统，其中路径规划是帮助司机在行车过程中规划行驶路线的过程，是路径引导、信息服务等模块的基础，因此其被广泛认为是汽车导航系统的基础问题。路径规划的实现主要依靠所选择的路径规划算法，因此路径规划算法的研究成为车载导航系统的重中之重。本文的主要内容就是在研究车载导航系统的同时，重点研究其中的路径规划问题，研究路径规划的算法。 1.2.2 本文的安排 本文共分为五章: 第一章是“绪论”，说明了本文的研究背景及意义，简要介绍了GPS的发展概况和发展趋势，并对论文的研究内容和章节安排做了介绍。 第二章是“GPS车载导航系统的结构与关键技术”，简述了车载导航系统的发展，设计的主要思路，以及GPS车载导航系统的总体结构和关键技术以及系统结构分析和各模块的功能。 第三章是“路径规划的分析及设计”，主要研究了电子地图的数据库生成和道路的生成，以及路径规划的几种算法，并举例设计了几个简单的路径规划。 第四章是“路径规划的优缺点分析”，本章主要说明了上一章介绍的几种路径规划的优缺点。 第五章是“结论”，对本论文的总结及对本研究今后可能的发展和创新的展望。 5 第二章 GPS车载导航系统的结构与关键技术 第二章 GPS车载导航系统的结构与关键技术 2.1 车载导航系统的发展 车载导航系统的研究和发展在人类的文明史上已有相当长的历史，最古老、最简单的导航方法是星历导航，人们通过观察天空上星星的位置变更来确定自己的位置和前进方向。随着科学技术的高速发展，将先进的信息处理技术、数据通信技术、电子控制技术及计算机处理等技术集于一体的智能交通系统的研究是21世纪现代运输管理体系的模式和发展方向。卫星定位技术(GPS)、地理信息系统(GIS)、遥感技术(RS)、数据库技术、计算机网络技术等科技技术的出现，有效地解决了当前城市现代交通管理的诸多问题。 目前，不管是在经济发达的欧洲、美国、日本，还是在经济正在快速发展的中国和其他国家，车辆导航系统都是各国政府的重要建设项目。美国公路局最早于20世纪60年代末期提出了一种电子路径引导系统(ERGS)，这是一种具有无线路径引导功能的导航系统，用于控制和疏导交通，但由于资金问题没有实现。最终终于在80年代中期相继把先进的导航产品投入市场。日本从1971年开始研究综合车辆交通控制系统计划(CACS)，从1973,1978年，日本成功的组织了一个叫做动态路径诱导的实验。从20世纪80年代中期到90中期的10年间，相继完成了路车间通信系统(RACS)、先进的管理交通信息控制系统(AMTICS)、交通信息通信系统(TICS)及智能车辆系统等研究，并推出了各种导航仪器。欧洲也大量的发行了自己的许多导航产品。我国的车载导航系统的发展始于20世纪80年代末期，虽然在自主引导型车载导航系统方面还没有非常成熟，但监管控制型的导航产品已经接近成熟并开始使用。目前已有许多科学研究单位和公司从事这方面的开发应用。 因此，GPS导航系统在交通管理以及运输方面是非常有前景的，并且能够带动与其相关的通信技术、信息技术、控制技术、多媒体技术和计算机应用技术的发展。 2.2 车载导航技术的总体结构和关键技术 6 GPS车载导航仪的路径规划研究 2.2.1 车载导航系统的总体结构 车载导航系统是由GPS终端、车载计算机、导航软件、显示器及GIS软件等组成的(如图2.1)。主要包括:?GPS接收机，它接受卫星定位信号，确定车辆当前所在的经纬度信息。其主要功能是采集实时的位置信息，进行自身的定位，不断的更新当前数据，为交通管理提供最新的数据信息。?计算机，结合编程技术及地图数据，为用户提供了多媒体信息服务。?GIS电子地图，把地理数据以图形的方式显示出来，提供了多种地图服务，为用户提供一个直观清晰的界面。?车载手机、寻呼机，提供与控制中心的通信手段，接受、发送各种数据、命令、请求以及服务信息。 GPS终端 GIS软件 空间数据库 电子 地图车载计算机数据 导航软件 库 DBMS软件 属性数据库 显示器 图2.1 车载导航系统的总体结构 2.2.2 车载导航系统的关键技术 ? 数字地图:也称电子地图，是一个矢量化的地图，即该地图中应该包括地图上的基本对象的属性数据。它是GPS导航系统和GIS的数据基础。典型的数字地图的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 格式有MapInfo的MIF/MID文件，AutoCAD的DXF文件等。 ? 地图匹配:即利用电子地图中高精度的道路位置信息来修正定位系统给出的车辆位置信息，进一步提高车辆定位精度的技术。一个完整的地图匹配过程包括三个主要环节，即误差区域的确定、匹配道路的选择及定位结果的修正。 ? 路径规划:路径规划是车辆导航系统必不可少的核心功能之一，也是实现导航功能的前提条件。车辆导航系统的路径规划是帮助驾驶员在旅行前或旅行中规划行驶路径的过程，它要解决的主要问题是在给定的数字道路地图中寻找从出 7 第二章 GPS车载导航系统的结构与关键技术 发地到目的地的最优路径，为满足实际要求，路径规划应具有快速性和最佳性。 2.3 车载导航系统结构分析及功能要求 车载导航系统共分为6个模块: ? 定位模块:采用全球定位系统(GPS)来实现车辆定位。 ? 数字地图数据库模块:主要负责存储数字地图及信息。它主要包括了支持电子地图显示的地图数据库及用于路径引导的道路特征数据库，是导航和定位的基础。 ? 地图匹配模块:又称地理编码，即通过给定的经纬度坐标确定地图上街道的地址，或者相反的过称。 ? 路径规划模块:帮助司机在车辆运行过程中，根据地图数据库模块所提供的地图，按要求的条件快速生成任意两点之间的最佳驾驶路线。如果有条件利用实时的交通信息，还应对驾驶路线及时调整以适应交通当前的状况。 路径导航模块:指挥司机按着路径规划模块计算出来的路线，并通过定位? 系统引导车辆行驶。路径行驶包括两个任务:一是产生行驶指令，任务是产生一个行驶指令列表使其遵循路径规划跟踪的路线。二是规划跟踪，任务是紧密监视车辆所在的路段位置。这些信息通过人——机接口，并以特殊的指令如视、听提供给司机。 ? 无线通信模块:可进一步改善系统的性能增加系统的功能，通过一个或多个不同的通信设备，车载系统或交通管理系统能够接受实时交通信息或报告，去辅助车辆定位和导航，以促进车载系统或整个公共网络工作的更加安全有效。 2.4 系统的功能要求 车载导航系统的主要功能有: ? 定位功能:利用全球定位系统(GPS)来获取当前的定位信息并与地图进行匹配，从而决定车辆当前的所在然后以图形的方式显示出来。 ? 最优路径搜索功能:根据用户在地图上选取的任意两地，系统将进行实时计算，按照用户的需求规划从出发地到目的地的最佳行驶路径，并以醒目的方式将路径显示在电子地图上。 8 GPS车载导航仪的路径规划研究 ? 地图浏览功能:地图浏览包括缩放、移动等，用户可以在一定的放大级上将地图进行缩小、放大、移动的操作。 ? 信息查询功能:为用户提供所需的目标查询，如服务区、道路、学校、医院、宾馆、餐馆等，用户可以根据自己的需要在电子地图上查询。查询的资料可以通过文字、图形的方式在电子地图上显示其位置。 车载导航系统是利用全球定位系统、地理信息系统、计算机和先进的通信技术等，将实时的重要信息高效的提供给驾驶员，使其能够选择更优的路径驾驶，具有很强的实用价值和非常广阔的前景。其中的路径规划是导航系统的一项关键技术，是导航系统的基础部分。 9 第三章 路径规划的分析及设计 第三章 路径规划的分析及设计 3.1 导航电子地图数据库的设计 3.1.1 导航电子地图的数据结构与数据模型 1.常用导航电子地图数据模型与结构 (1)空间数据结构 空间数据结构包括矢量结构、栅格结构及矢量栅格一体化结构三种。 ?矢量结构 该结构用空间坐标及其关系描述空间对象，单个空间对象是图形数据的基本逻辑单位。其优点是对图形数据表达良好、结构紧凑、冗余度低。缺点是数据结构复杂，对软硬件要求高。根据数据结构中空间对象的组织形式与联系程度又分 NODE结构。 为描述结构、整体多边形结构、对偶独立地图编码结构及ARC- ?栅格结构 该结构用点的像素表示空间对象。其优点是结构简单、显示速度快。缺点是精度较差、网络拓扑建立困难。根据像素的存贮结构及空间单元不同，具体又分为栅格编码结构、嵌套结构、不规则结构等多种形式。 ?矢量栅格一体化结构 该结构综合了两种结构的优点，在许多电子地图中得到了应用。 (2)属性数据的数据模型 目前，属性数据采用的模型有层次模型、网状模型和关系模型。 ?层次模型 该模型的基本结构是树形结构。层次模型数据库系统是数据库领域发展最早的一种，目前已基本不用，但其在数据库发展历史上有着重大的作用和影响，以后的模型均受其影响。 ?网状模型 网状模型明显优于层次模型，数据显示和数据操作方法均呈现高效、成熟的特点，但是，网状模型不足之处在于使用时涉及系统内部因素较多，用户操作使用不方便，数据模式与系统实现也甚不理想。 10 GPS车载导航仪的路径规划研究 ?关系模型 关系模型是完全不同于前两种模型的一种新的模型，前两种模型一般被称为格式化模型，而关系模型一般称为非格式化模型，其基本结构是二维表，简称表(table)。二维表由表框架和元组组成，表框架由n个属性(或称为列)组成，而存放于框架内的每行数据称为元组(或称为行)，因此，一张二维表是由一个n元属性的框架及m个元组组成。关系模型中的操作是建立在二维表上的操作，包括对一张表及多张表间的查询、删除、插入及修改等操作。 2.面向对象的整体数据结构 面向对象的整体数据模型是将面向对象(object oriented)思想和面向对象的分析设计方法应用到空间数据模型的设计中，将各种空间实体抽象为某一类具有公共属性的对象，如点、线、面等对象，每个具体的地理实体是该对象的一个实例，具有自己的属性，各种对象分层管理，实现空间数据与属性数据的统一管理。 面向对象的整体数据模型强调的是整体与面向对象的概念。它不仅将地理世界以实体为单位进行组织，而且将客观世界作为一个整体看待，即每个实体不仅自身具有空间特性和属性特性的联系，更重要的是它与其它实体之间同时还具有逻辑上的语义联系，此外，它也具有时间属性。面向对象的方法为数据模型的建立提供了四种数据抽象技术(分类、概括、联合、聚集)和两种数据抽象工具(继承和传播)，利用这些技术所构造的数据模型要比传统的数据模型丰富的多，更适用于定义复杂的地理实体和对复杂对象的直接操作。因此，面向对象的整体数据模型是一种有效的空间数据模型。 面向对象的方法为描述复杂的空间信息提供了一种直观有效的方法。与传统的导航电子地图数据模型相比，面向对象的数据模型具有的优点是:结构清晰、组织有序，所有空间实体都以对象的形式封装;可以定义和处理复杂的空间实体;易于扩充和二次开发;面向对象的用户界面更便于用户操作和使用。 3.1.2 导航电子地图数据库的设计原则 在智能车辆导航系统中，导航电子地图工作于实时、多任务的环境，图形的显示、刷新、信息查询、拓扑关系等是数据结构设计必须考虑的重要因素。一般设计导航电子地图数据库应遵循以下原则: 11 第三章 路径规划的分析及设计 ?图形结构简单。由于导航电子地图主要包含点、线、面等空间对象，简单的图形结构具有数据量少、刷新快、图形剪裁方便等特点。 ?冗余度小。小的地图数据冗余度将使地图信息查询、路径搜索的速度都得以提高，同时降低数据的储存空间。 ?拓扑关系简单。简单明了的拓扑关系将缩短最优路径规划及地图匹配时间。 ?空间信息查询速度快。好的数据结构将提高空间信息的查询速度。 ?数据接口开放。电子地图中的非空间数据具有良好的数据接口，能够兼容商用的非空间数据库。 3.1.3 导航电子地图数据库的结构设计与实现 导航电子地图数据库是整个系统的基石，系统中几乎所有的模块都直接或间接的与其相关，其结构设计的好坏将直接影响整个系统的最终性能。综合考虑各方面因素，采用三层结构模式，以便充分利用面向对象程序设计方法的特性，使各层之间保持低耦合、高内聚的特点，层与层之间以通过的接口方式保持通讯，其层次结构如图3.1所示。 空间对象 属性数据 接口层 对象访问 索引操作 属性操作 核心层 二进制文件读写模块 读写层 OBJIDXDBF 其他 文件 文件 文件 文件 图 3.1 导航电子地图数据库的层次结构 第一层为接口层，包括空间对象与属性结构。该层为设计的数据库进行二次开发提供了一系列的接口。应用软件设计人员可以调用该结构访问数字地图文件，并对地图对象和属性数据进行操作，例如属性数据的查询等。 12 GPS车载导航仪的路径规划研究 第二层为核心层，是实现整个数据库的关键部分，涉及到得数据结构和算法在这部分实现。 第三层为读写层，完成对二进制文件底层读写操作。系统的其他部分不能对数据库文件直接进行操作。读写层抽象了对文件进行操作的特性，封装了对磁盘链的管理和读写操作等。 图3.2给出了导航电子地图数据库实现流程，整个过程可以分为文件层、用户层和接口层三部分。 人机接口界面 (地图显示、信息查询、路径规划及地图匹配等功) 用户层 属性数据 空间数据 接口层 空间对象/索引对象/属性对象 地图数据库文件读写 导航电子地图数据库文件 (即.OBI、.IDX、.DBF及.TP文件) 文件层 格式转换及拓扑生成 数据格式分析/关键数据解析 外部地图数据源 图 3.2 导航电子地图数据库实现流程 3.2 导航电子地图中道路网络的拓扑生成方法 3.2.1 导航电子地图中道路网络的模型与储存 1.导航电子地图中道路网络的数据模型 道路网络的数据模型，是指导航电子地图道路网络用来组织其数据所采用的模型，它是生成具有拓扑结构道路网络的基础。目前，有关道路网络的数据模型 13 第三章 路径规划的分析及设计 用的较多有基于路段连接和基于Arc-Node(弧-节点法)等若干种。本文采用Arc-Node结构，其主要特点是，容易表达实际路网的拓扑关系，且形式简洁。 Arc-Node模型的基本原理是，将显示中的真实道路用一系列折线段来模拟和近似，即在一定精度的允许范围内，采用以直代曲的思想，用分段连续的小段直线段所组成的折线段来代替和逼近真实的道路曲线，将其中小段的直线段称作Arc，Arc的端点称为Node,这样，整个道路网络将由Arc和Node组成，其形式化定义为 Rw = (N,R) N = {x|x?Ns} R = {NR} NR = {,x,y,|L(x,y)...(x,y?N)} 式中:Rw ——道路网络; Ns ——道路网络的节点集; R——道路网络中任意两节点间拓扑关系的集合; N ,x,y,——节点x和y之间存在的一条弧; L(x,y) ——节点x和y之间的权值，节点和节点之间连接的权值可以用节 点之间的集合长度或者其他费用来表示。 根据实际交通网络的特点，我们作如下分析假设: ?所有的编制都是直线。对于弯曲弧度较大的路段，可以通过在该路段上 插入一系列节点使该路段由一些弧度较小的路段构成，弧度较小的路段可以认 为是一条边。如图3.3，节点1、2之间路段的弧度较大，在路段上加入节点2，把原来的路段分成两个弧度相对较小的路段。 ?边通常是双向可通的，边的权值为正值。 ?网络中有较多的节点和边。 ?和节点相关联的边数为常数，且远小于网络中总的节点数。 14 GPS车载导航仪的路径规划研究 节点3 节点1 节点2 图 3.3 弧度较大的路段处理 2.导航电子地图中道路网络的计算机存储 计算机存储的是矢量化的道路网络，网络的存储结构是影响路径规划算法搜索速度和事件复杂度的一个重要因素。一个简单直观的存储方法是对道路网络图中的每一个节点进行编号，采用邻接表的链式存储结构。在邻接表中，对图的每个节点建立一个单链表，每个单链表都由表节点和表头节点构成。第i个单链表的w个表节点分别对应着和图中第i个节点相关联的w条边。链表的表头节点以顺序结构形式存储，以便随机访问图中任一节点的单链表。因此，采用邻接表的链式存储结构，很容易找到和图中任一节点相关联的边。单链表的表头节点和表节点的结构如图3.4所示，图中，Name:节点编号;Position:节点位置坐标;First:指向链表中的第一个表节点;Next:指向链表中的下一个表节点;Weight:边的权值。 表头节点 表节点 Name Position First Name Position Weight Next 图 3.4 链表结构 3.2.2 折线道路网络的拓扑生成法 1.折线道路网络的组成特点 折线道路网络组成的最大特点是，每一条道路都是由带有宽度值的折线段(简称道路中心线)表示。有时，为了数据获取方便，也可能以近似的道路中心线来表示。各种来源提供的实际数据使得折线道路网络中可能存在以下情况: ?线段间的虚交特性，即两条实际相交的路段，在给定的道路网络数据中却 15 第三章 路径规划的分析及设计 不存在与交点对应的节点。如图3.5(a)所示，路段AB与路段CD实际应相交于节点O，而节点O并未出现在路段AB与路段CD的给定数据中。 ?线段间的虚段特性，即两条实际相交的路段，因其中一条路段偏短导致没能相交。如图3.5(b)所示，路段AB与路段CD实际应相交于节点B，而节点B并未出现在路段CD的给定数据中，将节点B称为虚断点。 ?线段间的过交特性，即两条相交的路段，因其中一条路段偏长而导致过短的毛刺路段出现。如图3.5(c)所示，路段AB与路段CD相交于节点O，过短路段BO应该不存在，然而，节点B却出现在路段AB给定数据中，将节点B称为过交点。 ?节点的冗余特性，一种情况是，实际应该是同一节点的点却存在多个相邻的节点。如图3.5(d)所示，节点A、B、C、D实际表示的地图中的同一点，换言之，此时应该只用一个节点来表示地图中的该点，然而，给定的道路网络数据中却存在节点A、B、C、D;另一种情况是，本来可以由两个节点表示的路段，给定 e)所示，路段AB只需节点A和B的道路网络数据中却存在其他节点，如图3.5( 便能在精度允许范围内准确表示，而实际数据中却包括节点C和D。 B D D C C D A B B O A O C A (a)线段间的虚交特性 (c)线段间的过交特性 (b)线段间的虚断特 (c)线段间的过交特性 性 D D C B C A A B (d)表示同一点的多个节点 (e)可以压缩掉的中间节点 图 3.5 实际数据中折线道路网络的情况 2.折线道路网络拓扑生成算法原理 算法的原理可以简单的描述为:依据折线道路网络的组成特点及Arc-Node数据模型，由给定的折线道路网络数据生成表示其拓扑结构的Arc-Node数据结构。具体生成过称分为两步: 第一步是完善给定的折线道路网络数据，即对前面介绍的道路网络的几种特 16 GPS车载导航仪的路径规划研究 性进行相应的处理。具体的处理方法是:虚交时，将实际应该有的交点分别插入两条路段中，从而两条路段分裂成四条路段，如图3.5(a)中，应将节点O分别插入路段AB和路段CD中，从而使路段AB与路段CD分裂成路段AO、OB、CO和OD;虚断时，应以偏短路段延长线与另一路段的交点代替偏短路段中靠近该交点节点，如图3.4(b)中，应将路段AB的节点B用路段AB的延长线与路段CD之交点来代替;过交时，应该删除过短路段，如图3.5(c)中，应将路段OB删除，即将节点B从路段AB中删除;节点冗余时，如果是第一种情况，应以冗余节点的中心点代替这些冗余点;如果是第二种情况，则应将所有的冗余节点删除，如图3.5(d)中，应将A、B、C、D用它们的中心点来代替，该中心点的纵横坐标分别为这些冗余节点纵横坐标的均值，如图3.5(e)中，应将路段AB中的节点C和D删除而只保留节点A和B。 第二步是在第一步的基础上，由完善以后的折线道路网络数据生成表示其拓扑结构的Arc-Node数据结构，Arc-Node数据结构采用邻接表结构。 3.3 路径规划的分析及设计 路径规划是现代智能车辆导航的一项关键技术，是基于具有拓扑结构的道路网络，在车辆行驶前或行驶过程中寻找出发点到目标点最优行车路线的过称。本节充分挖掘实际道路网络具有的各种特性，分别利用道路网络空间分布特性和道路等级特性，设计了两种针对道路网络的启发式搜索策略，即方向搜索策略和分层搜索策略;利用所构造的搜索策略设计了三种不同的启发式搜索策略。 3.3.1 路径规划的基础算法 Dijkstra算法是设计各种路径规划的基础。本节简要的介绍Dijkstra算法的原理及特点，并给出它的两种具体实现方法，即邻接矩阵法和邻接节点法，作为后续几个路径规划算法的基础算法。 1.算法原理 给定带权有向图G=(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)表示为: 17 第三章 路径规划的分析及设计 TC(Pab)=?c(vi,vi+1) (i=1,2,„,n-1) (3-1) 所谓最短路径问题是指，在带权的有向图中寻找从指定起点到终点的一条权值总和最小路径。如果把权值看成弧的长度(即距离)，则目标路径就是起点到终点的距离最短的路径。 为说明求解给定两点间最短路径的算法，我们先来讨论单源点的路径问题，即给定带权的有向图G=(V,E)和原点v，求从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的路径。这可用反证法来证明:假设此路径上有一个节点不在S中，则说明存在一条终点不在S而长度比路径更短的路径。事实上这是不可能的。因为我们是按路径长度递增的次序来产生各条最短路径的，故长度比此路径短的所有路径均已产生，它们的终点必定是在S中，即假设不成立。因此，在一般情况下，下一条长度次短的最短路径的长度必须是 D(j)=Min{ D(i)|vi?V-S} (3-2) 其中，D(i)或者是弧〈v,vi〉上的权值，或者是D(k)(vk?S)和弧〈vk,vi〉上的权值之和。 从以上对Dijkstra算法原理分析可以看出，其最大特点是在最短路径的求解过程中搜索算法具有很大的盲目性，随时准备向其四面八方展开，最终的搜索区域基本上是以起始点为原点，以起始点与目标点的连线长度为半径的一个圆。 2.算法实现 (1)邻接矩阵法 根据上面对算法原理的分析，可以得到如下描述的单源点最短路径算法: 步骤一，假设用带权的邻接矩阵cost来表示带权有向图，cost(i,j)表示弧〈vi,vj〉上的权值，其中，1?i?n,1?j?n。若〈vi,vj〉不存在，则置cost(i,j)为?。S的初状态为空集。从v出发到图上其余各节点(终点)vi可能达到的最短 18 GPS车载导航仪的路径规划研究 路径长度D(i)的初始值为 D(i)=cost(v,vi) vi?V (3-3) 步骤二，选择vj，使得 D(j)=Min{ D(i)|vi?V-S} (3-4) vj就是当前求得的从v出发的最短路径的终点，令 S=S?{vj} (3-5) 步骤三，修改从v出发到集合V-S上任一节点vk可达的最短路径长度，如果 D(j)+cost(j,k),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的最短路径。 由于采用邻接矩阵法在解算最短路径时，搜索算法假设道路网络中的任意一个节点都和其他所有节点相邻接，因此导致其时间复杂度为O(n?),其中n为道路网络的节点总数。 (2)邻接节点法 邻接矩阵法的不足是邻接矩阵cost中存在大量的无效的0元素和?元素，这不仅占用大量的存储空间，而且也使得基于矩阵运算的Dijkstra算法效率大为降低。为了弥补邻接矩阵法的这种不足，下面给出Dijkstra算法的另一种实现算法——邻接节点法。 邻接节点法的基本思想是:先求出道路网络中各节点直接相邻节点的最大个数(简称为最大邻接点数，用变量MaxNum表示)，然后以MaxNum作为矩阵的列数，以道路网络中的节点总数n作为矩阵的行数，构造邻接节点矩阵J来描述道路网 19 第三章 路径规划的分析及设计 络中节点间的邻接关系。J的行按节点号从小到大顺序排列，与节点i邻接的节点号卸载矩阵的第i行，如果节点i的邻接节点个数小于MaxNum，则以0填充第i行直到填满。构造与J结构相同的初始判断矩阵DJ，同时将J中个元素邻接关系对应的边的权值填在同一位置上(?对应0元素)。即J(i,j)表示第j个与节点i邻接的节点编号，相应的，DJ(i,j)表示节点i与其邻接节点J(i,j)连线的权值，其中，1?i?n,1?j?MaxNum。这样，邻接节点法便用维数相对较低的矩阵J和DJ取代了邻接矩阵法中维数较高的矩阵cost，从而有效地改善了算法的存储效率和运算效率。 为了能够应用邻接节点法解算任意指定两点间的最短路径，程序首先需要完成以下3项预处理工作，以便得到初始化矩阵J和DJ: ?装载道路网络数据，获得道路网络中的节点和边的内部序号。需要说明的是，道路网络节点和边的内部序号与实际编号可以不相同。为了增加算法的灵活性，算法使用内部编号参数运算(这里假设内部序号和实际编号相同)。 ?计算道路网络的最大邻接节点数MaxNum。 ?构造邻接节点矩阵J，各行中的节点序号可以前后随意放置。对应邻接节点矩阵J的各元素，构造初始判断矩阵DJ。 有了邻接节点矩阵J和初始判断矩阵DJ以后，就可以对网络中任意给定两点进行最短路径规划。下面给出邻接节点法的具体实现步骤: 输入:道路网络的邻接节点矩阵J和初始判断矩阵DJ，以及路径规划的起点S和终点D。 输出:起点S到终点D的一条最短路径MinWay及相应的最短距离MinDist。 步骤一，初始化标记向量Mark，Mark(i)=—1，其中，i=1,2，„，MaxNum。 步骤二，根据起始点S，标记初始判断矩阵DJ的第s行，Mark(s)=0，记最短距离 MinDist=0。 步骤三，根据终点D，判断DJ的第d行是否已经标记，是则转步骤五;否则继续。 步骤四，在DJ已标记的行中，求所有元素的最小值dmin，若dmin=?，说明不存在最短路径，程序退出;否则MinDist=dmin，记录最小值元素所在的行di、列dj。然后再J中取(di,dj)元素，记为w，若第w行尚未标记，则将DJ的第w行标记，Mark(w)=di;并在J的第w行寻找值为di的元素，记录该元素的行ri、列 20 GPS车载导航仪的路径规划研究 rj。将DJ刚获得标记的行中各元素值均加上MinDist，并使DJ的(di,dj)和(ri,rj)元素为?。然后转步骤三。 步骤五，从终点D开始，由标记向量Mark的分量寻前点，知道起始点S，查得最短路径MinWay，MinDist即为相应的最短路径距离。 与邻接矩阵法相比，邻接节点法不仅将道路网络的存储空间降低到原来的MaxNum/n，而且也将搜索算法的时间复杂度降低到O(MaxNum?n)，由于MaxNum,,n，因此采用邻接节点法时算法的时间复杂度实质上是O(n)。 为方便起见，我们将不加任何启发式搜索策略的经典Dijkstra算法简称为算法RP0。 3.3.2 限制搜索区域的路径规划算法 针对Dijkstra算法搜索过程中无方向性的缺点，本节利用道路网络特有的空间分布特性够早了一种方向搜索策略，并给出利用该搜索策略合理限制算法搜索区域的具体方法，从而降低了算法搜索空间，提高了算法搜索效率。 1.算法原理 )道路网络特有的空间分布特性 (1 与普通的平面网络图相比，描述实际城市道路网络的拓扑图通常具有以下特点: ?多为大规模的稀疏网络，点多边少(网络的节点通常成千上万，甚至更多，而每个节点相连的路段一般不超过5，多为2、3或4)。 ?网络结构相对比较规则，即网中的节点分布比较均与(特别是经过规划的现代大都市)。 ?网络通常是(或近似是)完全连通图，即网络中的任意两点都可以相互到达。 ?网络中有表示供智能车辆掉头的换向节点，而且一般距当前路口500m左右。 (2)方向搜索策略的构造与应用 受几何学中“两点之间直线距离最短”的启发，在对实际城市道路网络中的给定两点进行最短路径规划时，起点到终点的连线方向基本上代表了最短路径的大致走向。在进行最短路径搜索时，我们可以利用该启发式信息来构造方向启发式搜索方法，合理缩小算法的空间，提高算法的搜索效率。 21 第三章 路径规划的分析及设计 2.限制搜索区域的确定方法 利用方向搜索策略合理限制算法的搜索区域是设计本算法的关键。 我们将此算法简称3-1算法，如图3.6所示在给定相同的路径规划起始点S和目标点D时，为搜索到从S到D的最短路径，算法RP0所需的搜索区域理论上是一个以S为圆心，以D为半径的圆;而算法3-1所需搜索区域则是如下一个区域:先以S和D的连线为对角线形成一个矩形R1(当S与D的连线水平或垂直时，R1退化为一条线段)，然后将R1的各边想外扩展一个阈值T2，形成一个更大的矩形R2，最后通过R2被与线段SD平行、距SD距离为阈值T1的左右(或上下)两条直线L1和L2切割形成搜索区域。 图3.6 限制搜索区域的确定方法 3.算法实现 算法3-1的实现步骤如下: 输入:采用邻接节点数据结构存储的矢量化城市道路网络，路径规划的起点S， ，阈值T终点D1和T2。 输出:节点S和节点D之间的一条距离最短路径。 步骤一，初始化，完成道路网络数据加载及程序运行环境设置等。 步骤二，根据阈值T1和T2构造限制搜索区域。 步骤三，在限制搜索区域内，根据给定的起点S和目标点D，调用算法RP0的实现程序进行最短路径计算。 步骤四，输出S和D之间的一条距离最短路径。 以上四步的关键是合理设定阈值T1和T2，构造合适的限制搜索区域。设计中 22 GPS车载导航仪的路径规划研究 主要依据是前面提到的换向距离500m和矢量化道路网络中边的平均长度，本算法中阈值T1和T2分别设为500m和1500m。 3.3.3 基于分层道路网络的分层路径规划算法 前面介绍的限制搜索区域的最短路径规划算法，有效地降低了算法的搜索空间，提高了算法的搜索效率。然而，桐多数路径规划算法一样，限制搜索区域的路径规划算法所解算出的最短路径，仍然只是数学意义上的最短路径，而非意义上的最优路径。所谓行车意义上的最优路径是指多数驾驶员所期望的行车路径。 事实上，最短路径无论距离最短还是时间最短，都不一定是行车意义上的最短路径。因为除了形式距离或形式时间外，最优路径的选择还需要考虑很多无法预期或定量化的因素。本节利用实际城市道路网络中路段的不同等级特性，构造了不同于方向搜索策略的另一种启发式搜索策略，即分层搜索策略，给出了利用该搜索策略设计分层道路网络和基于分层道路网络设计分层路径规划算法的具体方法。 1.算法原理 分层路径规划算法(简称算法3-2)的基本思想是:根据道路网络中路段的不同等级特性，将整个道路网络分为不同的层次，每一层包含道路网络不同级别的细节。高层道路网络是其相邻低层道路网络的抽象和浓缩，低层则是其相邻高层道路网络的具体扩展。换言之，任一高层道路网络内的路段和节点都包含于其相邻的低层道路网络内，而任意一个低层道路网络除了包含其相邻高层道路网络内的路段和节点外，还包含更多的其他路段和节点。这样，在进行路径规划是，我们便可以先在高层空间进行搜索，然后在搜索高层空间获得的结果基础上再添上低层空间的细节，得到问题的最终解。 2.分层道路网络设计 (1)城市道路网络中路段的分等级特性 多数城市道路网络存在的一个事实是其中的路段具有不同等级特性。这些不同的道路等级一般又都对应着不同的行车环境，如道路的行车时速限制、道路上红绿灯的设置间距、道路的宽度及路面质量等多种与行车密切相关的因素。 (2)道路网络的分层方法 将分层思想引入到道路网络的设计中，即根据道路网路中路段的不同等级特 23 第三章 路径规划的分析及设计 性，将整个道路网络RN分为不同的层。 (3)分层道路网络的表示 分层道路网络的表示是指分层道路网络如何在计算机中表示和存储，它是算法3-2的基础。设计中，首先采用Arc-Node模型将整个道路网络表示为:G=(N,A,B)，这里N={N1，N2，„,Nn}是道路网络中节点的集合，A={aij|1?i?n,1?j?MaxNum，其中MaxNum是RN的最大邻接节点数}是RN中各节点间邻接关系的集合，aij表示第j个与节点i邻接的节点，而且认为两节点间的边是双向的，B={bij|1?i?n,1?j?MaxNum ，其中MaxNum 是RN的最大邻接节点数}是RN中各邻接节点间连接边的权值合集，bij表示节点i与节点aij之间的边的权值，而且认为两节点间的边是双向的，另外，每条路段都有一个非负的权值和它关联，每条道路则是由一系列首尾相连的路段构成，它的权值是组成它的所有路段的权值之和。然后，为了将RN分为HRN和LRN，定义一个标记数组Mark1来标记RN中的节点属于哪些HRN，若Mark1(i)=1，则表示节点i不仅属于LRN，而且同时属于HRN，这样便将RN从逻辑上分成了高低两层。 3.算法实现 输入:具有拓扑结构矢量化道路网络RN及其对应分层道路网络HRN和LRN，起点S、终点D为道路网络中任意指定的两个节点。 输出:节点S和节点D之间的一条最优路径。 步骤一，初始化，完成路网数据加载及程序运行环境设置。 步骤二，判断节点S和D所在的路网层次，若节点S和D都已经在HRN中，则算法3-2直接转入步骤三;否则，若节点S不在HRN中，则算法必须先在S附近的小区域内调用算法RP0的实现程序进行结算，由它进入高层路网的最短路径L1及相应的位于高层路网上的节点S′，对节点D作类似的处理，求出相应的最短路径L2及相应的位于高层路网上的节点D′。 步骤三，在HRN中对节点S(或对应节点S′)和D(或对应节点D′)调用算法RP0的实现程序解算其最短路径L0。 步骤四，综合L0、L1及L2为L，将L作为节点S和D之间的一条最优路径输出。 3.3.4 限制搜索区域的分层路径规划算法 24 GPS车载导航仪的路径规划研究 由于方向搜索策略和分层搜索策略是从两个不同的角度降低算法搜索空间的，因此可以考虑将二者有机结合，以便同时从不同角度缩小算法的搜索空间，设计更为合理的路径规划算法。本节从这一设计思路出发，将前面的算法3-1和算法3-2进行有机结合，利用方向和分层搜索相结合策略，提出了新的算法3-3. 1.算法原理 算法3-3的基本思想是:先进行分层路径规划，然后再对高层网络中的两个相应节点进行路径规划时，采用限制搜索区域的路径规划算法。与算法3-2不同的是，算法3-3在HRN中搜索时，只对落入限制区域范围内的HRN进行搜索，而不是在整个HRN中进行搜索，因此它只保证搜索结果与算法3-2相同的同时，搜索效率却比算法3-1和算法3-2都高。 2.算法实现 输入:具有拓扑结构的矢量化道路网络RN，RN对应的分层道路网络HRN和LRN，路径规划的起点S和终点D，阈值T1和T2。 输出:节点S和节点D之间的一条行车最优路径。 步骤一，初始化，完成路网数据加载及程序运行环境设置。 步骤二，判断节点S和D所在的路网层次，若节点S和D都已在HRN中，则算法直接转入步骤三;否则，若节点S不在HRN中，则算法现在S附近小区域内调用算法RP0子程序搜索由它进入HRN的最短路径L1及相应的位于HRN上的节点S′，然后，对节点D作同样的处理，求得相应的最短路径L2及相应的位于HRN上的节点D′。 步骤三，根据阈值T1和T2，在HRN中对节点S(或对应的节点S′)和D(或对应的节点D′)构造限制搜索区域，然后调用算法RP0的子程序解算最优路径L0。 步骤四，综合L0、L1及L2为L，将L作为节点S和D之间的最优路径输出。 25 第四章 路径规划的优缺点分析 第四章 路径规划的优缺点分析 4.1 算法的实验结果 将算法RP0、算法3-1、算法3-2及算法3-3四种算法同时应用于西安市二环内道路网络中，在给定起始节点1979和1264时，图4.1,图4.4分别是算法RP0、算法3-1、算法3-2和算法3-3的搜索结果显示。图中，粗线为搜索出的最短路径。 图 4.1算法RP0 图 4.2 算法3-1 26 GPS车载导航仪的路径规划研究 图 4.3 算法3-2 图 4.4 算法3-3 4.2 算法实验结果的比对及优缺点分析 表4-1列出了四种算法搜索结果的部分性能对比。在表4-1中，N1表示起点，N2表示终点;T1表示算法RP0所用的搜索时间，T2表示算法3-2所用的搜索时间，T3表示算法3-1所用的搜索时间，，T4表示算法3-3所用的搜索时间;D1表示算法RP0规划出的最优路径长度，D2表示算法3-2规划出的最优路径长度，D3表示算法3-1规划出的最优路径长度，D4表示算法3-3规划出的最优路径长度。 从表4-1可以看出，算法3-3较算法3-1和算法3-2的搜索效率高，体现在 27 第四章 路径规划的优缺点分析 相同输入是T4比T1的十分之一还小，比T2的三分之一还小。从D1、D2、D3和D4四列可以看出，算法3-3和算法3-2规划出的最优路径相同，且其长度比算法RP0和算法3-1规划出的最短路径长度稍长，这样的规划结果更符合实际系统要求，因为多数驾驶员都希望行车过程中能尽量走这种路径。 表 4-1 算法RP0、3-1、3-2与3-3搜索结果性能对比 N1 N2 T1/s T2/s T3/s T4/s D1/m D2/m D3/m D4/m 1979 1264 3.999 0.734 1.313 0.334 27215 28514 27215 28514 1170 955 3.609 0.671 0.702 0.203 20747 21055 20747 28514 2350 3730 1.797 0.344 0.25 0.109 7662 8374 7662 8374 2853 3275 3.28 0.734 0.344 0.17 17306 17395 17306 17395 1979 5498 3.344 0.702 1.249 0.296 25763 27902 25763 27902 6421 5691 2.797 0.515 0.39 0.155 15567 16031 15567 16031 3736 1264 3.051 0.547 0.312 0.141 15853 17100 15853 17100 3736 3730 1.359 0.234 0.141 0.079 9094 1012 9094 1012 28 GPS车载导航仪的路径规划研究 第五章 结论 29 第五章 结论 2.1 论文小结 在进行本论文的研究过称中，本人得出以下结论:路径规划是车载导航系统中的基础，是系统设计中的核心内容。本文对GPS车载导航系统的总体结构进行了简单的研究，并介绍了本文内所涉及的相关知识，如GPS、GIS、电子地图数据库、拓扑网络等，重点对路径规划的算法进行了详细研究，综合考虑了多种最短路径选择算法。本设计以MapInfo地理信息系统软件为工具，实现了Dijkstra算法,并作了一定的改进，并在数字地图上显示了要求的最短路径的结果，设计基本达到预期目标。 2.2 路径规划系统的展望 鉴于个人的能力有限，本论文所进行的路径规划研究并不能完全解决车载导航系统的需求，因此还存在以下问题有待进一步研究和改进的地方: (1)显示地图上任意两点间的最短距离:本文中是将用户任意选择的点与其最近的节点相匹配，求出的是匹配后两点之间的最短距离，这样显示的时候不能以用户所选的点为起始点和终止点，甚至在有些情况下会出现错误。如何使用户选择的任意点匹配到道路地图上，还需要进一步的研究。 (2)最佳路径分析:最佳路径分析要比最短路径分析复杂的多。在实际应用中，要考虑到实际路况信息，例如道路堵塞等。本文规划出的仅仅是最短路径，没有联系实际的路况。 (3)同路况监测系统的集成:在交通网络中，车辆的运行过程是一个动态变化的过程，交通网络中的所有节点和路段的某些属性并不是一成不变的，而是是随着时间不断变化的，并且极可能影响到路径规划的准确性，导致提供不正确的规划结果。因此仅使用静态网络中的静态信息来进行路径规划，结果可能不能满足用户实际的需要。在实际行驶时,需要知道当前各路段交通的状况，以便给用户提供真正的“最佳路径”。 (4)基础道路数据的更新:在城市在不断地发展变化中城市路网也在变化， 30 GPS车载导航仪的路径规划研究 因此系统所用的数字地图也需要实时更新，所以实时更新GIS也需要进一步讨论。 (5)道路网数据模型的改进:本文中并没有考虑到城市交通设施中实际存在的立交桥及单向车道等特殊道路，需要在交通道路方面进一步改进数据模型，完整地表达各个道路的拓扑关系。 (6)复杂地形上的路径规划:要进行路径规划的区域也许是一个复杂的地理区域，包括河流、丘陵、建筑物等。如果要使路径规划系统适应这些复杂地形上的路径规划，就需要有能够适应三维图形上的路径规划算法加以辅助。 31 致谢 致 谢 在本论文即将完成之际，我要感谢我的导师王文朋老师。在完成论文的过程中王老师给了我许多建议及指导，王老师的谆谆教诲、严格要求以及他那极具启发性的指导和严谨求实的治学态度使我受益非浅，无论在理论上还是实践上他都给了我莫大的帮助，使我自身得到了不少提高。在此，我要对王老师表示最崇高的敬意和最衷心的感谢。另外我还要感谢我的同学们，他们也给了我许多有益的建议。 最后再次衷心的感谢所有支持和帮助我的老师和同学们。 32 33 致谢 参考文献 [1] 黄丁发，张献州，熊永良，李春华，周乐韬，罗德安，GPS卫星导航定位技术与方法，科学出版社，2009年 [2] 常青，杨东凯，寇艳红，张其善，车辆导航定位方法及应用，机械工业出版社，2005年5月 [3] 付梦印，邓志红，刘彤，智能车辆导航技术，科学出版社，2009年 [4] 杨柳，车载导航系统中路径规划算法的研究及实现，北京交通大学硕士研究生学位论文，2008年6月 [5] 屈展，车载导航系统中路径规划问题的研究，兰州理工大学硕士研究生学位论文，2009年9月 [6] 王亚文，智能交通系统中路径规划算法研究与系统设计，陕西师范大学硕士研究生学位论文，2007年5月 [7] 付梦印，李杰，邓志红，限制搜索区域的距离最短路径规划算法，北京理工大学学报，2004年 [8] 付梦印，李杰，邓志红，基于分层道路网络的新型路径规划算法，北京理工大学学报，2005年 [9] 付梦印，李杰，邓志红，限制搜索区域的分层路径规划算法，北京理工大学学报，2005年 [10] 吴秀琳，刘永革，王利军，MapInfo 9.5中文标准版教程，清华大学出版社，2009年 参考: 毕业论文(设计)工作记录及成绩评定册 题 目: 33 34 学生姓名: 学 号: 专 业: 班 级: 指 导 教 师: 职称: 助理指导教师: 职称: 年 月 日 实验中心制 使 用 说 明 一、此册中各项内容为对学生毕业论文(设计)的工作和成绩评定记录，请各环节记录人用黑色或蓝色钢笔(签字笔)认真填写(建议填写前先写出相应草稿～以避免填错)，并妥善保存。 二、此册于学院组织对各专业题目审查完成后，各教研室汇编选题指南，经学生自由选题后，由实验中心组织发给学生。 三、学生如实填好本册封面上的各项内容和选题审批表的相应内容，经指导教师和学院领导小组批准后，交指导教师;指导老师填好《毕业论文(设计)任务书》的各项内容，经教研室审核后交学生签名确认其毕业论文(设计)工作任 34 35 致谢 务。 四、学生在指导老师的指导下填好《毕业论文(设计)开题报告》各项内容，由指导教师和教研室审核通过后，确定其开题，并将此册交指导老师保存。 五、指导老师原则上每周至少保证一次对学生的指导，如实按时填好《毕业论文(设计)指导教师工作记录》，并请学生签字确认。 六、中期检查时，指导老师将此册交学生填写前期工作小结，指导教师对其任务完成情况进行评价，学院中期检查领导小组对师生中期工作进行核查，并对未完成者提出整改意见，后将此册交指导老师保存。 七、毕业论文(设计)定稿后，根据学院工作安排，学生把论文(打印件)交指导老师评阅。指导老师应认真按《毕业论文(设计)指导教师成绩评审表》对学生的论文进行评审并写出评语，然后把论文和此册一同交教研室。 八、教研室将学生的论文和此册分别交两位评阅人评阅后交回教研室保存。 九、学院答辩委员会审核学生答辩资格，确定答辩学生名单，把具有答辩资格学生的论文连同此册交各答辩小组。 十、学生答辩后由答辩小组记录人填好《毕业论文(设计)答辩记录表》中各项内容，然后把学生的论文和此册一同交所在答辩小组，答辩小组对其答辩进行评审并填写评语后交教研室。 十一、学院答辩委员会进行成绩总评定，填好《毕业论文(设计)成绩评定表》中各项内容，然后把论文(印刷版和电子版(另传))和此册等资料装入专用档案袋中，教教研室后由实验中心统一保存。 目 录 1(毕业论文(设计)选题审批表 2. 毕业论文(设计)任务书 3(毕业论文(设计)开题报告 4. 学生毕业论文(设计)题目更改 申请表 食品经营许可证新办申请表下载调动申请表下载出差申请表下载就业申请表下载数据下载申请表 35 36 5(毕业论文(设计)指导老师工作记录 6(毕业论文(设计)中期检查记录 7(毕业论文(设计)指导教师成绩评审表 8(毕业论文(设计)评阅人成绩评审表 9. 毕业论文(设计)答辩申请表 10(毕业论文(设计)答辩记录表 11(毕业论文(设计)答辩成绩评审表 12(毕业论文(设计)成绩评定表 36 37 致谢 毕业设计(论文)选题审批表 题目名称 基于单片机的超声波测距 ?科研题目 ?生产?工程设计 ?理论研究 现场 题目性质 ?实验研究 ?计算机软件 题目来源 ?教学 ?其它 ?综合论文 ?其它 ?自拟题目 选题理由:由于超声波指向性强，能量消耗缓慢，在介质中传播的距离较远，因而超声波 经常用于距离的测量。利用超声波检测距离，设计比较方便，计算处理也较简单，精度也能达到使用要求，超声波测距应用于各种工业领域，如工业自动控制，建筑工程测量和机器人视觉识别等方面。超声波作为一种检测技术，采用的是非接触式测量，由于它具有不受外界因素影响，对环境有一定的适应能力，且操作简单、测量精度高等优点而被广泛应用。这些特点可使测量仪器不受被测介质的影响，大大解决了传统测量仪器存在的问题，比如，在粉尘多情况下对人引起的身体接触伤害，腐蚀性质的被测物对测量仪器腐蚀，触电接触不良造成的误测等。此外该技术对被测元件无磨损，使测量仪器牢固耐用，使用寿命加长，而且还降低了能量耗损，节省人力和劳动的强度。因此，利用超声波检测既迅速、方便、计算简单，又易于实时控制，在测量精度方面能达到工业实用的要求。 37 38 指导教师意见: 签名: 年 月 日 院(系)领导小组意见: 签名: 年 月 日 注:此表由学生填写 38 39 致谢 毕业论文(设计)任务书 1、毕业论文(设计)应达到的目的: (1)能对学生在学期间所学知识的检验与总结，培养和提高学生独立分析问题和解决问题的能力，使学生受到科学研究、工程设计和撰写技术报告等方面的基本训练。 (2)提高学生对工作认真负责、一丝不苟，对事物能潜心观察、用于开拓、用于实践的基本素质; (3)培养学生综合运用所学知识，结合实际独立完成课题的工作能力。 (4)对学生的知识面、掌握知识的深度、运用理论结合实际去处理问题的能力、实践能力、计算机运用水平、书面及口头表达能力进行考核。 2、毕业论文(设计)的内容和要求(包括原始数据、技术要求、工作要求等): 以单片机为核心设计了基于激光测距的防撞预警系统，采用TDC-GP2芯片作为激光飞行计时单元,给出激光发射及回波接收放大电路，基于模块化思想设计、完成系统软件设计流程;最后通过实验测试，系统要能很好测出前方车辆距离及运行状态，并能及时发出报警，利用Matlab对其测试结果进行验证，修正。 3、对毕业论文(设计)成果的要求〔包括图表、实物等硬件要求〕: 设计完成后，要提供电路图，实验电路版，控制原始程序，实验要保存大量的原始数据。完成设计论文。 39 40 4、毕业论文(设计)工作进度计划: 日期(起止周序号 论文(设计)工作进度 数) 根据所出题目，结合自身所学知识，选择合适课题，确定毕业设计13-14-1 1 论文题目。 第16周止 根据所定题目，全面搜集素材，列出各种设计方案，并一一比较，13-14-1 2 选择出最好的设计方案。 第18周止 联系指导老师，将自己的设计方案与老师沟通、交流，得到指导老13-14-1 3 师的认同与指点，开始设计。 第19周止 根据方案，确定所要用的器材。设计总体框架结构，分出各大的模13-14-2 4 块，并将其展开，以得到比较细的设计模式。 第1周止 根据所列框图，结合自己所学知识，开始各分支电路模块的设计。 13-14-2 5 第2周止 完成初稿，将所做的模块给指导老师查阅，看是否有不当之处，再13-14-2 6 进行改进。并将大电路的设计方案告之老师，得到老师更好的建议。 第3周止 大胆进行设计，将每一个小的电路，大的模块，都精心设计好，完13-14-2 7 第6周止 成整个硬件和软件部分的设计过程。 将所有设计整理结合，形成设计论文，交与指导老师检查，并经老13-14-2 8 师指点，做进一步的改进工作。 第7周止 13-14-2 改进毕业设计论文，得到自己及老师认为满意的论文。 9 第10周止 指导教师 日期 年 月 日 教研室审查意见: 签字: 年 月 日 学院负责人意见: 签字: 年 月 日 学生签字: 接受任务时间: 年 月 日 注:任务书由指导教师填写。 40 41 致谢 毕业论文(设计)开题报告 题 目 基于单片机的超声波测距 1、本课题的研究意义，国内外研究现状、水平和发展趋势 近年来，随着电子测量技术的发展，运用超声波作出精确测量已成可能。随着经济发展，电子测量技术应用越来越广泛，而超声波测量精确高，成本低，性能稳定则备受青睐。超声波是指频率在20kHz以上的声波，它属于机械波的范畴。超声波也遵循一般机械波在弹性介质中的传播规律，如在介质的分界面处发生反射和折射现象，在进入介质后被介质吸收而发生衰减等。正是因为具有这些性质，使得超声波可以用于距离的测量中。随着科技水平的不断提高，超声波测距技术被广泛应用于人们日常工作和生活之中。一般的超声波测距仪可用于固定物位或液位的测量，适用于建筑物内部、液位高度的测量等。 随着科学技术的快速发展，超声波将在测距仪中的应用越来越广。但就目 前技术水平来说，人们可以具体利用的测距技术还十分有限，因此，这是一个正在 蓬勃发展而又有无限前景的技术及产业领域。展望未来，超声波测距仪作为一种新 型的非常重要有用的工具在各方面都将有很大的发展空间，它将朝着更加高定位高 精度的方向发展，以满足日益发展的社会需求，如声纳的发展趋势基本为:研制具 有更高定位精度的被动测距声纳，以满足水中武器实施全隐蔽攻击的需要;继续发 展采用低频线谱检测的潜艇拖曳线列阵声纳，实现超远程的被动探测和识别;研制 更适合于浅海工作的潜艇声纳，特别是解决浅海水中目标识别问题;大力降低潜艇 自噪声，改善潜艇声纳的工作环境。无庸置疑，未来的超声波测距仪将与自动化智 能化接轨，与其他的测距仪集成和融合，形成多测距仪。随着测距仪的技术进步， 测距仪将从具有单纯判断功能发展到具有学习功能，最终发展到具有创造力。在新 的世纪里，面貌一新的测距仪将发挥更大的作用。 41 42 2、本课题的基本内容，预计可能遇到的困难，提出解决问题的方法和措施 利用单片机控制超声波测距，发射器发出的超声波以速度υ在空气中传播，在到达被测 s,vt/2物体时被反射返回，由接收器接收，其往返时间为t,由即可算出被测物体的距离。 预计可能遇到的问题是受温度的影响，测量精度不高，则应通过温度补偿的方法加以校正。 报告人签名: 2015年 3 月 20 日 3、本课题拟采用的研究手段(途径)和可行性分析 由于超声波指向性强，能量消耗缓慢，在介质中传播的距离较远，因而超声波 经常用于距离的测量。利用超声波检测距离，设计比较方便，计算处理也较简单， 并且在测量精度方面也能达到农业生产等自动化的使用要求。 超声波发生器可以分为两大类:一类是用电气方式产生超声波，一类是用机械方 式产生超声波。电气方式包括压电型、电动型等;机械方式有加尔统笛、液哨和气 流旋笛等。它们所产生的超声波的频率、功率、和声波特性各不相同，因而用途也 各不相同。目前在近距离测量方面常用的是压电式超声波换能器。根据设计要求并 综合各方面因素，本文采用AT89C51 单片机作为控制器，用动态扫描法实现LED 数 字显示，超声波驱动信号用单片机的定时器。 42 43 致谢 4、进度计划 序号 日期 进度安排 根据所出题目，结合自身所学知识，选择合适课题，确定13-14-1 1 毕业设计论文题目。 第16周止 联系指导老师，将自己的设计方案与老师沟通、交流，得13-14-1 2 到指导老师的认同与指点，开始设计。 第18周止 联系指导老师，将自己的设计方案与老师沟通、交流，得13-14-1 3 到指导老师的认同与指点，开始设计。 第19周止 根据方案，确定所要用的器材。设计总体框架结构，分出13-14-2 4 各模块，并将其展开，以得到比较细的设计模式。 第1周止 根据所列框图，结合自己所学知识，开始各分支电路模块13-14-2 5 的设计。 第2周止 完成初稿，将所做的模块给指导老师查阅，看是否有不当13-14-2 6 之处，再进行改进。并将大电路的设计方案告之老师，得第3周止 到老师更好的建议。 大胆进行设计，将每一个小的电路，大的模块，都精心设13-14-2 7 计好，完成整个硬件和软件部分的设计过程。 第6周止 将所有设计整理结合，形成设计论文，交与指导老师检查，13-14-2 8 并经老师指点，做进一步的改进工作。 第7周止 13-14-2 9 改进毕业设计论文，得到自己及老师认为满意的论文。 第10周止 10 11 43 44 5、指导教师意见(对本课题的深度、广度及工作量的意见和对设计结果的预测) 指导教师(签字): 年 月 日 6、教研室意见 教研室主任(签字): 年 月 日 说明:开题报告应根据教师下发的毕业设计(论文)任务书，在教师的指导下由学生 独立撰写，在毕业设计开始后两周内完成。 44 45 致谢 学生毕业论文(设计)题目更改申请表 原毕业论文(设计)题目 基于单片机的激光测距 现毕业论文(设计)题目 基于单片机的超声波测距 首先激光测距仪成本较高，且制作的难度大，测量距离较短，需要注意人体 安全，光学系统需要保持干净，否则影响测量精度。而且单片机与激光测距仪 的连接很复杂，我主要是利用单片机控制测距仪器，目的是对单片机的知识进 行巩固和进一步学习，从而完成毕业设计。 更 改 原 因 理 由 学生签名: 日期:2015.3.2 指 导 教 师 指导教师签名: 意 见 日期: 教 研 室 教研室主任签名: 意 见 日期: 45 46 院 系 论文负责人签名: 意 见 日期: 46 47 参考文献 毕业论文(设计)指导教师工作记录 (由指导老师填写与学生见面、电话、网上指导的主要内容，原则上一周填写一次。) 指导记录: 到中国知网和西南财经大学图书馆查阅资料，学习关于超声波的知识，弄清楚超声波测距的原理，然后搞懂各个模块的电路。 教师签学生签 填写时间:2015 年 2 月28 日 名 名 指导记录: 大概弄懂各个模块的电路图及工作原理， 选出一个最好的方案进行设计，有问题赶快问，不能等，在毕业设计中学到知识。 教师签学生签 填写时间: 2015 年3 月 8 日 名 名 指导记录: 根据自己设计的方案，完成毕业论文的初稿。 教师签学生签 填写时间: 2015 年 3月 18 日 名 名 指导记录: 填写时间: 年 月 日 教师签学生签 47 48 参考文献 名 名 毕业论文(设计)指导教师工作记录 (由指导老师填写与学生见面、电话、网上指导的主要内容，原则上一周填写一次。) 指导记录: 教师签学生签 填写时间: 年 月 日 名 名 指导记录: 教师签学生签 填写时间: 年 月 日 名 名 指导记录: 教师签学生签填写时间: 年 月 日 名 名 指导记录: 教师签学生签 填写时间: 年 月 日 名 名 48 49 参考文献 毕业论文(设计)指导教师工作记录 (由指导老师填写与学生见面、电话、网上指导的主要内容，原则上一周填写一次。) 指导记录: 教师签学生签 填写时间: 年 月 日 名 名 指导记录: 教师签学生签 填写时间: 年 月 日 名 名 指导记录: 教师签学生签填写时间: 年 月 日 名 名 指导记录: 教师签学生签 填写时间: 年 月 日 名 名 毕业论文(设计)指导教师工作记录 49 50 参考文献 (由指导老师填写与学生见面、电话、网上指导的主要内容，原则上一周填写一次。)指导记录: 教师签学生签 填写时间: 年 月 日 名 名 指导记录: 教师签学生签 填写时间: 年 月 日 名 名 指导记录: 教师签学生签填写时间: 年 月 日 名 名 指导记录: 教师签学生签 填写时间: 年 月 日 名 名 毕业论文(设计)中期检查记录 50 51 参考文献 完成的主要工作及质量，存在的问题和拟解决的方法: 前期 工作 学 小结 生 填 写 ?指导教师坚持每周指导，认真负责，要求严格 指导情况 ?指导教师指导不够，要求欠严格 学生签名 年 月 日 ?按计划完成预定的工作内容 完成质量:?好 ?一般 ?差 ?未按计划完成预定的工作内容，主要原因: 对学生完指 成任务情导 况的评价 教 师 填 写 ?坚持每周指导，学生积极寻求和接受指导 指导情况 ?学生寻求和接受指导主动性不够 教师签名 年 月 日 ?按计划完成预定的工作内容 对学生学完成质量:?好 ?一般 ?差 习的评价 ?未按计划完成预定的工作内容 对指导教?坚持每周指导，认真负责，要求严格，指导记录填写详实、规范 院(系)师工作的?坚持每周指导，认真负责，指导记录填写不详实、欠规范 评价 ?未坚持每周指导 中期检 查领导 小组填 写 整改意见 检查小组负责人(签字) 年 月 日 毕业设计(论文)指导教师成绩评审表 分得评分项目 评价内涵 值 分 51 52 参考文献 遵守各项纪律，工作刻苦努力，具有良好的科学工作态度。 01 学习态度 6 工作 通过实验、试验、查阅文献、深入生产实践等渠道获取与表现 02 7 科学实践、调研 毕业设计有关的材料。 20% 按期圆满完成规定的任务，工作量饱满。 03 课题工作量 7 能运用所学知识和技能去发现与解决实际问题，能正确处04 15 综合运用知识的能力 理实验数据，能对课题进行理论分析，得出有价值的结论。 能独立查阅相关文献和从事其他调研;能提出并较好地论 述课题的实施方案;有收集、加工各种信息及获取新知识05 5 应用文献的能力 的能力。 能力 能正确设计实验方案，独立进行装置安装、调试、操作等06 15 实验(设计)能力 水平 实验工作，数据正确、可靠。 45% 能运用计算机进行资料搜集、加工、处理和辅助设计等。 07 5 计算机应用能力 对实验结果的分析能力 具有较强的数据收集、分析、处理、综合的能力。 08 (或综合分析能力、技5 术经济分析能力) 插图(或图纸)质量、符合本专业规定要求。 9 5 篇幅 论文(或设计说明书)综述简练完整，有见解;立论正确，论述充分，结论严谨10 10 合理;实验正确，分析处理科学。 撰写水平 成果 论文(或设计)的实用质量 具有科学性，有一定的实用价值。 11 5 性与科学性 35% 文字通顺，技术用语准确，符号统一，编号齐全，图表完论文(或设计)规范化备、整洁、正确;用语格式、图表、数据、各种资料的运12 5 程度 用及引用都要规范化。 对前人工作有改进或突破，或有独特见解。 13 10 创新 是否达到答成 辩要求 绩 评阅人评语 评阅人(签名): 年 月 日 毕业论文(设计)评阅人成绩评审表 52 53 参考文献 分得评分项目 评价内涵 值 分 遵守各项纪律，工作刻苦努力，具有良好的科学工作态度。 01 6 学习态度 工作 通过实验、试验、查阅文献、深入生产实践等渠道获取与表现 02 7 科学实践、调研 毕业设计有关的材料。 20% 按期圆满完成规定的任务，工作量饱满。 03 7 课题工作量 能运用所学知识和技能去发现与解决实际问题，能正确处04 15 综合运用知识的能力 理实验数据，能对课题进行理论分析，得出有价值的结论。 能独立查阅相关文献和从事其他调研;能提出并较好地论 述课题的实施方案;有收集、加工各种信息及获取新知识05 5 应用文献的能力 的能力。 能力 能正确设计实验方案，独立进行装置安装、调试、操作等06 15 实验(设计)能力 水平 实验工作，数据正确、可靠。 45% 能运用计算机进行资料搜集、加工、处理和辅助设计等。 07 计算机应用能力 5 对实验结果的分析能力 具有较强的数据收集、分析、处理、综合的能力。 08 (或综合分析能力、技5 术经济分析能力) 插图(或图纸)质量、符合本专业规定要求。 9 5 篇幅 论文(或设计说明书)综述简练完整，有见解;立论正确，论述充分，结论严谨10 10 合理;实验正确，分析处理科学。 撰写水平 成果 论文(或设计)的实用质量 具有科学性，有一定的实用价值。 11 5 性与科学性 35% 文字通顺，技术用语准确，符号统一，编号齐全，图表完论文(或设计)规范化备、整洁、正确;用语格式、图表、数据、各种资料的运12 5 程度 用及引用都要规范化。 对前人工作有改进或突破，或有独特见解。 13 10 创新 是否达到答成 辩要求 绩 评阅人评语 评阅人(签名): 年 月 日 53 54 参考文献 毕业论文(设计)评阅人成绩评审表 分得评分项目 评价内涵 值 分 遵守各项纪律，工作刻苦努力，具有良好的科学工作态度。 01 6 学习态度 工作 通过实验、试验、查阅文献、深入生产实践等渠道获取与表现 02 科学实践、调研 7 毕业设计有关的材料。 20% 按期圆满完成规定的任务，工作量饱满。 03 7 课题工作量 能运用所学知识和技能去发现与解决实际问题，能正确处04 15 综合运用知识的能力 理实验数据，能对课题进行理论分析，得出有价值的结论。 能独立查阅相关文献和从事其他调研;能提出并较好地论 述课题的实施方案;有收集、加工各种信息及获取新知识05 5 应用文献的能力 的能力。 能力 能正确设计实验方案，独立进行装置安装、调试、操作等06 15 实验(设计)能力 水平 实验工作，数据正确、可靠。 45% 能运用计算机进行资料搜集、加工、处理和辅助设计等。 07 5 计算机应用能力 对实验结果的分析能力 具有较强的数据收集、分析、处理、综合的能力。 08 (或综合分析能力、技5 术经济分析能力) 插图(或图纸)质量、符合本专业规定要求。 9 5 篇幅 论文(或设计说明书)综述简练完整，有见解;立论正确，论述充分，结论严谨10 10 合理;实验正确，分析处理科学。 撰写水平 成果 论文(或设计)的实用质量 具有科学性，有一定的实用价值。 11 5 性与科学性 35% 文字通顺，技术用语准确，符号统一，编号齐全，图表完论文(或设计)规范化备、整洁、正确;用语格式、图表、数据、各种资料的运12 5 程度 用及引用都要规范化。 对前人工作有改进或突破，或有独特见解。 13 10 创新 是否达到答成 辩要求 绩 评阅人评语 54 55 参考文献 评阅人(签名): 年 月 日 毕业论文(设计)答辩申请表 学生姓名 学号 专业 论文(设 ? 设计 ? 论文 计)题目 申 请 理 由 申请人(签名): 年 月 日 指 导 教 师 意 见 指导教师(签名): 年 月 日 55 56 参考文献 教 研 室 意 见 负责人(签名): 年 月 日 说明:此表打印后用黑色或蓝色钢笔(或签字笔)手工填写。 专科毕业设计(论文)答辩记录表 (由记录人使用) 姓名 性别 职称 职务 其他 答辩小组名单 56 57 参考文献 答辩记录: 记录人(签字): 年 月 日 专科毕业设计(论文)答辩成绩评审表 (答辩小组用) 评分项目 分值 得分 评价内涵 准备充分 01 答辩准备 5 思路清晰;语言表达准确，概念清楚，论点正02 10 陈述表达 确; 符合本学科的发展和培养目标，体现学科、专 业特点和教学计划中对能力知识结构的基本要03 5 选题 求，达到毕业设计(论文)综合训练的目的。 分析归纳合理，方案论证充分，实验方法科学。 04 10 设计(论文)思路 圆满完成规定任务，工作量饱满，难度较大， 具备综合运用所学知识和技能，有分析、解决05 30 主要完成情况 实际问题的能力，论文(设计)有应用价值。 回答问题有理论根据，基本概念清楚，主要问06 20 回答专家提问 题回答准确、深入，有逻辑性。 条理清楚，文理通顺，用语符合技术规范;图07 5 论文书写质量 表完备、整洁、正确，书写格式规范 57 58 参考文献 合理使用各种检索工具，能独立检索文献资料。 08 文献查阅 5 对前人工作有改进或突破，或有独特见解，有09 创新 10 一定的应用价值。 成 绩 答辩 小组 评语 组长(签字): 年 月 日 专科毕业设计(论文)成绩评定表 ,答辩委员会用, 题目名称 姓名 学号 专业 各项成绩 评分项目 评定成绩 实际得分 所占比例 指导教师评分 30% 评阅人1 评阅人评分 30% 评阅人2 58 59 参考文献 答辩小组评分 40% 成绩等级结论 是否同意毕业设计(论文)通 ?同意 ?不同意(?重新修改?重新答辩) 过 院(系)答辩委员会主任签字: 年 月 日 院(系)公章: 说明:1. 毕业设计(论文)的成绩应由指导教师、评阅人、答辩小组三部分的评分组成。 2.成绩折算标准:优?>=90分、良?>=80分、中?>=70分、及格?>=60分、不及 格?<60分。 59