·114-
基于地理位置的最知
短路径导航算法赵银银
（北华大学工程训练中心，吉林吉林132021）
科技论坛
摘要：智能交通系统(ITS)在交通领城的应用使人们能够避开节省时间、安全出行，是解决措车问题的利器。本文根据道路交通网的关键词：交通乎航；路网模型；路径规划
1概述
智能交通系统是将信息、通讯、电子传感、电子控制以及计算机处理技术等有效地集成运用于整个交通运输管理体系.提高了通系统的可靠性、安全性、经济性及运行效率-。导航系统是智能交通系统中重要的组成部分。常用的导航算法复杂度较高，因而实时性较差，为提高实时性通常需要辆性算法的精度。本文考虑了道路导航在地理位置上的特点，设计出了一套更加简化、实时性更高的路径规划方法
2路网模型
本文设计的路网模型如图1所示，它最突出的优点是增减节点对整个网络的影响不大，这样的路网模型可以表示为：
G =(R,)
R=fr..... =n,n.)
(1)
当前节点为D4，当查找到D4的可达结点后，D5成为当前结点；当 D5查找到可达结点后，E1成为可达结点，如此向下，每条线路每次只向下搜索一步，各条线路并行向下搜索，直到搜索到目的地节点，此时一条线路规划完成.修改当前节点，继续查找其它线路。
c2 ca
e
图2路径规划算法运行示意
o
offie(OD) DG
图3路段的编移量计算
若O为当前结点，E为目的地结点.A、B、C、D为当前结点的可达结点。以0为原点，东西方向为X轴，南北方向为Y轴，将图划分
f:f(r)
为四个象限。OA与OE在同一象限，则其偏移量为零；OC与OE象
其中：G为路网模型，R为道路的集合，r;表示某一段道路，n；
限相对，则其偏移量为路段OC的长度；OB、OD的偏移量如图3所
表示某一结点，表示某条道路的权值。在这样的路网模型中，路网的拓扑关系表现为节点从属于路段，路段的终点作为其可达路段的起点。
mr 书点(n
图1路网模型
3路径规划
3.1基于地理位置的最短路径算法
人们选择的起点与终点之间的道路通常具有很强的方向性，即在起点到终点连线的方向上，也是在小范围内进行。但是由于拥堵等原因，“绕路"花费的时间反而会更少，因此在选择同向路段时需要保留一定的余量，允许选择的路段方向与终点方向有一定的偏移
量。
基本思想如下：a.确定路径规划的起点所在的路段，将该路段设
为当前路段，该路段的终点设为当前结点0；确定终点所在的路段，将该路段的起点设为目的地结点END。h.由当前结点搜寻其可达结点并判断当前路径是否已包含此结点，若未包含则计算二者的偏移量，以及到此处为止的总偏移量，若总偏移量超过一定数值，则舍弃这条路径。e.修改当前结点为还未作过当前结点的前一步搜寻到的可达结点。重复b，直到目的地结点成为可达结点，此时规划出一条路线，再继续搜寻其他路线。当我们将所有可行的路径选择出来以后，利用基于卡尔曼滤波算法的行程时间预测模型的结果分别计算各路径花费的时间，然后选择花费时间最小的路线作为最佳路线。
其体举例如图2所示，A为起始结点，B1、B2为A的可达结点， C1、C2为B1的可达结点,C3为B2的可达结点，路线(A,B1,C1,D1) 由于总偏移量过大而被舍弃。由于D2、D3已查找到可达结点，因此
示。此外，设置一个总偏移量，用它记录规划到当前结点时，各个路段偏移量的和。当每次选择下一结点时，计算它的偏移量，并加入总偏移量。若总偏移量超过一定数值，则舍弃当前的路径。
3.2算法的复杂度
常用的路由算法中，Dijkstra算法的时间复杂度为O(V*V+E),其中V为节点总数.E为路段股的总数。Floyd-Warshall算法的时间复杂度为0(V~3),容间复杂度为0(V~2)。本文提出的算法的时间复杂度为0(V).空间复杂度为0(V"2)。本算法的复杂度低，因而执行速度更快，也更适合动态交通环境下的车辆导航
4结论
本文根据道路导航的地理位置特点，在新设计的路网模型上，提出了一种执行速度更快、执行效率更高的、更适合于道路交通导航的基于地理位置的最短路径算法。我们利用北京市东城区道路网和历史交通流数据进行了测试，结果表明基于地理位置的最短路径算法的精度较好，且实时性却远远好于其他算法。
参考文献
[1鲍晓东.智能交通系统的现状及发展[北京：北京工业职业技术学院学报,2012
[2]Gonzalez H, Han J, Li X. Adaptive fastest path computation on road network: A traffic mining approach. Proceedings of the 33rd international conference on Very large data bases (VLDB), Vienna, Austria, 2007. 794805
[3]韩息民,知经纬度计算两点精确距离[J]科技传播.2011,6(3):32-39[4JLI Mingming,LU Hongqian,YIN Hang.Novel algorithm
for
geomagnetic navigation [J]. Jourmal of Central South University of
Technology ,2011,10(3):3259. 2012,3(7):2135