基本信息
- 项目名称：
- 基于GPS的最佳动态路径分析与仿真研究
- 来源：
- 第十二届“挑战杯”省赛作品
- 小类：
- 机械与控制
- 大类：
- 自然科学类学术论文
- 简介：
- 利用车辆导航技术的反馈信息，通过A*算法对静态路网的最优路径做出动态选择。现今流行的Dijkstra算法、A*算法等，都是基于完全静态、确定的信息数据库下，求解得出的最短路径。本文通过A*算法充分利用静态路网信息，借助车辆导航系统加以动态路网中的适应条件，以及实时更新的交通数据，得出计算结果精确，时间复杂度较低，且符合实际情况的最佳路径。
- 详细介绍：
- 目前，随着社会经济的发展、城市化进程的加快和机动车保有量的快速增长，尤其私家小汽车的快速发展，城市交通越发拥挤。 由于土地资源不足，建造各种公路等物理设施的能力是有限的, 所以单纯地依靠修建更多的道路、扩大路网规模等这样的措施仅仅能解一时之需, 并不能从根本上解决日益增长的交通需求。基于这种需要，提出了以车载GPS（Global Positioning System）为核心的路径分析系统。该技术是以GPS技术为核心, 综合利用广播技术、光电传感器、计算机网络、自动控制和人工智能等技术的一种新型车辆导航技术[1]。 现阶段，车载GPS进入规模化发展阶段。“车载GPS 最佳路径分析” 在车辆导航系统及城市应急系统中有着广泛的应用前景。针对城市道路网的特点，对基于城市道路网的最佳路径分析的关键技术进行了研究和验证。提出了一种实用、高效的最佳路径分析解决方案，并在此基础上实现了一个最佳路径分析法的高效实现算法。 一条路径的确定取决于许多因素，如距离、行程时间、路网弯数、路况复杂度、转向灯个数、交通信号灯的数目和动态交通信息等。选择最短路径、最佳路径、最低耗费等问题，都离不开最短路径搜索并以其作为选择依据。路径选择标准可由程序设计决定或通过用户界面修改[2]。 最短路径问题的解决方法很多，包括启发式搜索A*算法、动态规划方法、神经网络、Dijkstra 算法等，其中以迪杰斯特拉(Dijkstra)算法在实际应用中较为广泛。 由于Dijkstra算法的搜索过程属于遍历计算，所以出现大量的搜索节点。其中，Dijkstra算法与A*算法搜索范围特点如下图1所示。由于所引入的动态算法，是要求处理大量的静态数据的同时，还需要实时监测接受的动态数据，并计算当前对于最佳路径的影响的一些数据[3]。因此，处理量就变得相当大，一般来说，硬件不能支持。 A*算法是比较流行的启发式搜索算法之一，被广泛应用于路径的最优解。A*算法对比其他算法，不同之处在于A*算法引入了启发式函数。启发式估价函数估价每一生成节点以确定此节点的优劣性。通过这种方式，启发式函数决定在诸多路径中首先遍历那条路径以便搜索过程更为有效，因为算法首先搜索最优希望的节点[4]。 A*算法的算法步骤： 1)创建开放列表OPENLIST，初始化列表，使其只包含起始点； 2)创建关闭列表CLOSEDLIST，初始化清空列表； 3)从OPENLIST中选择f′(n)值最小的一个节点n； 4)如果n是目标节点，停止搜索，转到步骤（7）； 5)对于n的相邻节点中的一个节点m； （1）如果m在CLOSEDLIST中并且g（m）更小，更新节点m的g值，将其父节点指向n。 （2）如果m在OPENLIST中且目前的g（m）更小，更新节点m的g值，将其父节点指向n。 （3）如果m不在OPENLIST和CLOSEDLIST中，将m加入OPENLIST中，计算其g值，将其父指针指向n。 6)返回执行步骤（3），继续搜索； 7)从目标节点向上回溯到原节点，记录经过的节点。遍历一系列后向指针后，得到最佳路径； 现实生活当中，交通信息属于动态信息，即每一段路都有其自己的属性。如果单纯地从距离和时间出发，所得出的最短路径与实际驾驶者所希望的并不能完全符合。譬如，得出的最短路径上，有其中路段属于交通拥堵严重的，即其路段的效率就相对低下。相对驾驶者来说，意味着比其他路径所使用的路径花费更多时间。又或者即使路径上没有交通意外，堵塞等情况，但是路径上出现较多的收费设置，同样对于驾驶者来说是不利的[5]。因为这意味着花费更多的费用。 因此，必须从动态路网中分析主要影响车辆行驶最佳路径的因素。根据路径选择的限制要求，得出以下几点： 1）道路系数 道路的级别对于车辆通过性有重要意义，高速公路的效率肯定要比城市里面的支路的效率高。同样级别的道路，双车道和四车道同样拥有不同的通过效率[6]。根据我国现行的《公路工程技术标准》（JTJ001-1997），公路按使用任务、功能和适应的交通量分为高速公路、一级公路、二级公路、三级公路、四级公路五个等级： （1）、高速公路为专供汽车分向分车道行驶并应全部控制出入的多车道公路。 四车道高速公路能适应将各种汽车折合成小客车的年平均日交通量25000～55000辆。 六车道高速公路能适应将各种汽车折合成小客车的年平均日交通量45000～80000辆。 八车道高速公路能适应将各种汽车折合成小客车的年平均日交通量60000～100000辆。 （2）、一级公路为供汽车分向分车道行驶并可根据需要控制出入的多车道公路。 四车道一级公路能适应将各种汽车折合成小客车的年平均日交通量15000～30000辆。 六车道一级公路能适应将各种汽车折合成小客车的年平均日交通量25000～55000辆。 （3）、二级公路为供汽车行驶的双车道公路。 一般能适应每昼夜3000～7500辆中型载重汽车交通量。 （4）、三级公路为主要供汽车行驶的双车道公路。 一般能适应每昼夜1000～4000辆中型载重汽车交通量。 （5）、四级公路为主要供汽车行驶的双车道或单车道公路。 双车道四级公路能适应每昼夜中型载重汽车交通量1500辆以下。 单车道四级公路能适应每昼夜中型载重汽车交通量200辆以下。 2）GPS/DR（航位推算,Dead-Reckoning)组合定位的反馈信息 DR的基本原理是利用方向传感器和速度传感器来推算车辆的瞬时位置，可以实现连续自主式定位。但由于其推算过程是一个累加过程，方向传感器的误差随时间的延长而积累，另外，推算只能确定相对位置和航向。因此，将航位推算与GPS 组合起来，两者取长补短，可以弥补各自的缺点, 确保系统能在任何时候都能为运动车辆提供较为准确的导航信息。一方面可以利用GPS精确的定位结果辅助DR 的初始化并且可以定期地用它对DR 的定位误差进行在线校正。另一方面，在GPS无法定位时系统又可以自动地切换到DR 导航方式，直至GPS 恢复正常接收后, 系统再回到GPS 与DR 的组合导航方式[7]。从而，即使在GPS失效、单独使用DR推算定位时也能长时间保持较高的定位精度。 通过GPS反馈的定位信号进行运动车辆的检测和分割，预测其在相关路径的运动轨迹，从而根据交通流量综合其他情况进行调度，可以把发生冲突的交通流从时间和空间上进行分离，稳定平衡交通流的密度。 3）广播和交通部门信息的双向调控 在通信网络的支持下，参考广播电台的实时路面路况信息，即时接受交通部门发布的突发事故，并通过GSM通信网与移动中的车辆进行通话、短信息传输和数据传输，完成车辆定位、调度、监控、报警等功能，且在电子地图上显示车辆的位置，做出应急路径选择，间接地约束最优动态路径，避免大面积的交通瘫痪，保证动态路网运动车辆行驶路径的准确性[8]。 其中，接受短信息可用GSM用户终端（如车载台、手机）或用可接收短信息功能的固定用户设备，也可用ISDN方式直接连接到移动通信局的短消息服务中心，并联通车辆导航管理系统，这样接收短信息更迅捷，容量更大[9]。 4）可自动更新的数据库管理系统 车辆定位导航系统由自导航系统，管理系统，组合系统三部分组成。同时，系统应配置有图形结构简单、冗余度小、拓扑关系简单、空间信息查询与分析速度快、拥有开放数据接口的电子地图数据库。 出发地和目的地之间的最佳线路需要参照最新的时间、距离、收费等标准，并且所要求的数据存储冗余小，空间数据处理与分析操作时间短。因此，要求电子地图的数据库能够智能通过GRPS联网更新，进行电子地图数据的自适应，并要求装载硬盘的剩余空间足够大而拥有不断下载更新包的能力。 由上述约束条件，得到基于A*算法的最佳路径的算法流程图。 欧氏距离在路网中的代码如下： function distance=euclideandis(x，y)％x and y：two vectors to be tested． if(max(size(x))-----max(size(y)))％label lerror(’Array sizes do not match．’)； end if((rain(size(x))--=1)l(min(size(y))-一-1)) error(’Both x and Y are vectors’)； end％label2 distance=sqrt(sum((x•y)．^2))／max(size(x))； GPS \DR快速定位功能弥补了遥感不足，GPS 能将遥感获取数据实时快速进入地理信息系统，并保证遥感数据与地面同步监测数据获取动态配准，动态进入GIS（地理信息系统，Geographic Information System）、RS (遥感，Remote Sensing) 数据库。同时，利用遥感数据可实现GPS 定位遥感信息查询。GIS系统，GPS 定位信息电子地图上将以实时反映和漫游查询。将GPS 和电子图相配合，可组成各种电子导航和监控系统。并且，GPS\DR 可为GIS 及时采集，更新和修正数据，输入电子图或数据库后，可对原有专题图进行修正，核实或形成新专题图件，从而得到动态实时的显示车辆的运行状况，车辆所处的位置，周围道路两侧的空间信息等[10]。 通过最小距离点连点的方法获取原始路径，再由行车电脑内置的大容量导航电子地图处理相关位置信息，同时，对比优化电子地图的数据库进行自适应管理，添补更多的路面信息，包括路途上的交通信息，入限速标志、交叉路口转弯限制、信号灯等。 根据当前位置和将要到达的目标位置(工作时输入)，导航系统自动，实时地计算和显示最短路径或最佳路径，引导驾驶员最快地到达目的地。最短路径或最佳路径的分析计算量比较大，因此采用上述的算法，减少系统的搜索时间和运算速度至关重要。最佳路径的选择不仅要考虑，距离最短，而且也要考虑时间最省，道路状况，交通管制等因素[11]。根据用户的要求，系统建立空间索引，通过查询和分析数据库的历史数据和道路空间数据的信息，选择满足用户要求的一条路线。 本文讨论分析了基于车辆监控导航系统的A*算法最佳路径,并通过相关的约束条件进行优化。针对城乡路网的特点，对最短路径分析的各项关键技术进行了研究，编写了相关路径选择程序进行了模拟，提出了一种实用的最佳路径分析解决方案，在此基础上实施了最佳路径分析方法及技术；城市交通设施和规则日益复杂，需要进一步改进数据模型，较完整地表达和建立了路网的拓扑关系。本文的算法能较准确、快速地检测和提取出运动目标,为交通调度提供了保障,有一定的实用价值。
作品图片
作品专业信息
撰写目的和基本思路
- 撰写的目的：为缓解城市交通拥挤，改善交通状况，保障公共安全，提高汽车出行效率，通过以GPS为核心的动态路径分析，配合交通部门调度，使得交通网络运行畅通。 撰写的基本思路： 以基于静态路网的A*算法为核心，通过对原算法添加道路权值的约束（约束包括：道路等级系数、道路堵塞系数、道路通过系数等），判断路径的动态情况，并作出车辆与路网的实时匹配，从而获得对交通行驶最有利的高效路径。
科学性、先进性及独特之处
- 引入了启发式函数，估价每一生成节点以确定此节点的优劣性。因为算法首先搜索最有希望的节点，启发式函数决定在诸多路径中首先遍历那条路径以便搜索过程更有效。通过添加道路权值改进A*算法，更精确地寻找出适合交通行驶的动态路径。算法通过添加约束条件的推荐系数，结合实时交通情况对车辆进行有效地调度，提高道路的利用效率。GPS/DR相关模块的引入，减少系统的搜索时间和运算速度，便于最佳路径的快速获得。
应用价值和现实意义
- 针对城市路网的特点，对最短路径分析的关键技术进行了优化，提出实用的最佳路径分析解决方案，在此基础上实施了最佳路径分析方法及技术。随着城市交通设施和规则日益复杂，需要电子地图数据库能够完整地建立和表达路网的拓扑关系。本文的算法能准确、快速地检测和提取出运动目标并有很强的实践性,仿真程序能够按照算法约束条件的动态反馈信息对突发事件作出及时的处理，从而为城乡交通路网提供有效的、智能化的调度。
学术论文摘要
- 利用车辆导航技术的反馈信息，通过A*算法对静态路网的最优路径做出动态选择。基于静态路网信息的最优路径求解是现时车辆GPS导航领域所面临的关键问题。现今流行的Dijkstra算法、A*算法等，都是基于完全静态、确定的信息数据库下，求解得出的最短路径。本文通过A*算法充分利用静态路网信息，借助车辆导航系统加以动态路网中的适应条件，以及实时更新的交通数据，得出计算结果精确，时间复杂度较低，且符合实际情况的最佳路径。
获奖情况
- 无
鉴定结果
- 本自然论文是由曾志雄等同学在老师的指导下通过一系列的理论分析和讨论研究独立编撰完成的，情况属实。并且，论文符合挑战杯课外学术科技作品竞赛的要求。
参考文献
- [1]杨利强,张宁,陶志祥. 3G移动通信技术在城市交通信息系统中的应用研究[J]. 公路交通科技, 2007,(12) [2]杨兆升. 关于智能运输系统的关键理论——综合路段行程时间预测的研究[J]. 交通运输工程学报, 2001,(01) [3]于德新，杨兆升，高鹏. 动态限制搜索区域的带约束K则最优路径算法[J]. 吉林大学学报（工学版），2009（39）2:172-176 [4]Van der Auweraer H,Mas P,Dom S,et al. Transfer analysis in the critical path of vehicle refinement:the role of fast,hybrid and operational path analysis .SAE Paper 2007 -01-2352 [5]杨瑞臣,周永付,云庆夏. 寻找车辆最优路径的混合算法[J]. 交通运输工程学报, 2005,(01) [6]张兰,雷秀娟. 几种改进PSO算法在带时间窗车辆路径问题中的比较与分析[J]. 计算机工程与科学, 2008,(12) [7]Juha Plunt. Finding and fixing vehicle nvh problems transfer path analysis[J] .Sound and Vibration, 2005, 39 (11) :12-16 [8]Hendricx William,De Vis Dirk. An overview of the European research project DIANA .SAE Paper 971897 [9]贺竹磬,孙林岩. 动态交通下车辆路径选择模型及算法[J]. 交通运输工程学报, 2007,(01) [10]李瑞敏,陆化普. 基于WebGIS的智能交通管理指挥调度系统[J]. 计算机工程, 2007,(21)
同类课题研究水平概述
- 1、美国、西欧和日本等发达国家为了解决共同所面临的交通问题，竞相投入大量资金和人力，开始大规模地进行道路交通运输智能化的研究试验。 2、在美国，智能交通应用发展较快的几个方面分别是，车辆安全系统（占 51%），电子收费（占37%），公路及车辆管理系统（占28%），实时自动定位系统（占20%），商业车辆管理系统（占14%）。因为美国交通路网的前期规划十分合理，因此其关注的重点是安全。 3、北美、欧洲和日本的很多城市现在都在开始使用“自适应面控系统”，即面控的信号灯系统模式，而我国还主要停留在点控的信号灯系统模式上，可见差距巨大。国外一些城市现在已经尝试对每辆车安装GPS，以此确定每辆车的位置，最终通过物流网技术来调节交通拥堵。而国内还在对智能交通系统的基础——中国国情下的“车流量”如何计算投入研究，规划实现一条线上四五个路口之间信号灯配合的线控系统模式。 4、国外的研究表明，智能交通系统可极大地提高公路的通行能力和服务水平，使每条车道每小时的车流量增加2至3倍，缩短行车时间35％ ～50％。此外，智能交通系统还可以大大提高公路交通的安全性，降低并排除人为错误、驾驶员心理对交通安全的消极影响，使预防和避免交通事故成为可能。从理论上讲，智能交通系统可以减少事故31％ ～85％。 5、利用地理信息系统（GIS），GPS，专用短程通信技术（DSRC）开发ATIS，ETC，CVO的车辆安全系统作为智能交通的主要应用在全球范围内已呈一种趋势。 6、智能交通的前景是美好的，但也是交通运输领域中技术难度最高的系统，其中，基于磁性标记诱导的车辆车道自动保持技术是当今世界车辆工程及自动控制领域的研究前沿，无论在理论上，还是在工程实践上都是对各国科研攻关实力和水平的考验。
