基于GPS的最佳动态路径分析与仿真研究

张云飞 杨亚茹 郑虎龙 段传绪 王廉拓

摘要：利用车辆导航技术的反馈信息，通过A*算法对静态路网的最优路径做出动态选择。基于静态路网信息的最优路径求解是现时车辆GPS导航领域所面临的关键问题。现今流行的Dijkstra算法、A*算法等，都是基于完全静态、确定的信息数据库下，求解得出的最短路径。本文通过A*算法充分利用静态路网信息，借助车辆导航系统加以动态路网中的适应条件，以及实时更新的交通数据，得出计算结果精确，时间复杂度较低，且符合实际情况的最佳路径。

关键词：交通调度  动态路网  最佳路径  A*算法  GPS

引言：

目前，随着社会经济的发展、城市化进程的加快和机动车保有量的快速增长，尤其私家小汽车的快速发展，城市交通越发拥挤。由于土地资源不足，建造各种公路等物理设施的能力是有限的， 所以单纯地依靠修建更多的道路、扩大路网规模等这样的措施仅仅能解一时之需， 并不能从根本上解决日益增长的交通需求。基于这种需要，提出了以车载GPS（Global Positioning System）为核心的路径分析系统。该技术是以GPS技术为核心， 综合利用广播技术、光电传感器、计算机网络、自动控制和人工智能等技术的一种新型车辆导航技术。

现阶段，车载GPS进入规模化发展阶段。

1基于静态路网的A*算法原理

一条路径的确定取决于许多因素，如距离、行程时间、路网弯数、路况复杂度、转向灯个数、交通信号灯的数目和动态交通信息等。选择最短路径、最佳路径、最低耗费等问题，都离不开最短路径搜索并以其作为选择依据。路径选择标准可由程序设计决定或通过用户界面修改。最短路径问题的解决方法很多，包括启发式搜索A*算法、动态规划方法、神经网络、Dijkstra 算法等，其中以迪杰斯特拉（Dijkstra）算法在实际应用中较为广泛。由于Dijkstra算法的搜索过程属于遍历计算，所以出现大量的搜索节点。其中，由于所引入的动态算法，是要求处理大量的静态数据的同时，还需要实时监测接受的动态数据，并计算当前对于最佳路径的影响的一些数据。因此，处理量就变得相当大，一般来说，硬件不能支持。A*算法是比较流行的启发式搜索算法之一，被广泛应用于路径的最优解。A*算法对比其他算法，不同之处在于A*算法引入了启发式函数。启发式估价函数估價每一生成节点以确定此节点的优劣性。通过这种方式，启发式函数决定在诸多路径中首先遍历那条路径以便搜索过程更为有效，因为算法首先搜索最优希望的节点。

2基于A*算法的最佳路径求解

现实生活当中，交通信息属于动态信息，即每一段路都有其自己的属性。如果单纯地从距离和时间出发，所得出的最短路径与实际驾驶者所希望的并不能完全符合。譬如，得出的最短路径上，有其中路段属于交通拥堵严重的，及其路段的效率就相对低下。相对驾驶者来说，意味着比其他路径所使用的路径花费更多时间。又或者即使路径上没有交通意外，堵塞等情况，但是路径上出现较多的收费设置，同样对于驾驶者来说是不利的。因为这意味着花费更多的费用。

2.1GPS/DR（航位推算，Dead-Reckoning）组合定位的反馈信息

DR的基本原理是利用方向传感器和速度传感器来推算车辆的瞬时位置，可以实现连续自主式定位。但由于其推算过程是一个累加过程，方向传感器的误差随时间的延长而积累，另外，推算只能确定相对位置和航向。因此，将航位推算与GPS 组合起来，两者取长补短，可以弥补各自的缺点， 确保系统能在任何时候都能为运动车辆提供较为准确的导航信息。一方面可以利用GPS精确的定位结果辅助DR 的初始化并且可以定期地用它对DR 的定位误差进行在线校正。另一方面，在GPS无法定位时系统又可以自动地切换到DR 导航方式，直至GPS 恢复正常接收后， 系统再回到GPS 与DR 的组合导航方式。从而，即使在GPS失效、单独使用DR推算定位时也能长时间保持较高的定位精度。

通过GPS反馈的定位信号进行运动车辆的检测和分割，预测其在相关路径的运动轨迹，从而根据交通流量综合其他情况进行调度，可以把发生冲突的交通流从时间和空间上进行分离，稳定平衡交通流的密度。

2.2广播和交通部门信息的双向调控

在通信网络的支持下，参考广播电台的实时路面路况信息，即时接受交通部门发布的突发事故，并通过GSM通信网与移动中的车辆进行通话、短信息传输和数据传输，完成车辆定位、调度、监控、报警等功能，且在电子地图上显示车辆的位置，做出应急路径选择，间接地约束最优动态路径，避免大面积的交通瘫痪，保证动态路网运动车辆行驶路径的准确性。

其中，接受短信息可用GSM用户终端（如车载台、手机）或用可接收短信息功能的固定用户设备，也可用ISDN方式直接连接到移动通信局的短消息服务中心，并联通车辆导航管理系统，这样接收短信息更迅捷，容量更大。

结论

本文讨论分析了基于车辆监控导航系统的A*算法最佳路径，并通过相关的约束条件进行优化。针对城乡路网的特点，对最短路径分析的各项关键技术进行了研究，编写了相关路径选择程序进行了模拟，提出了一种实用的最佳路径分析解决方案，在此基础上实施了最佳路径分析方法及技术;城市交通设施和规则日益复杂，需要进一步改进数据模型，较完整地表达和建立了路网的拓扑关系。本文的算法能较准确、快速地检测和提取出运动目标，为交通调度提供了保障，有一定的实用价值。

参考文献

[1] 杨利强，张宁，陶志祥. 3G移动通信技术在城市交通信息系统中的应用研究[J]. 公路交通科技， 2007，（12）

[2] 杨兆升. 关于智能运输系统的关键理论——综合路段行程时间预测的研究[J]. 交通运输工程学报， 2001，（01）