基于洪泛查询的最短路径算法在智能交通系统中的应用
2015-07-21赖培辉曾党泉
赖培辉+曾党泉
摘 要：针对智能交通系统中道路畅通情况时刻变化的最短路径求解问题，提出了一种基于洪泛查询的最短路径算法。该算法采用洪泛思想，位于路网上的某一节点收到来自另一直连节点的路径信息后，向除该节点之外的所有直连节点发送该路径信息。当一个节点收到多条来自同一源和去往同一目的的路径信息时，对多条路径信息的权值进行比较，只转发权值最小的路径信息，即最短路径信息。同时，该算法还能获得多条次优的最短路径，以作为备用路径，当在最短路径的某一段道路上发现了拥堵情况时，可以快速切换到另外一条次优的最短路径，且具有良好的健壮性和高效性。
关键词：洪泛；最短路径；智能交通系统；权值
中图分类号：TP301 文献标识码：A 文章编号：2095-1302（2015）07-00-03
0 引 言
交通系统在城市的发展中具有举足轻重的作用。随着我国城市化进程的加快和居民生活水平的提高，城市人口数量迅速增长，机动车数量越来越多，因此交通阻塞、交通事故问题日趋恶化，交通阻塞造成的经济损失巨大，仅依靠修建道路、扩大道路网络规模等传统方法来缓解日益增长的交通需求，已很难适应我国社会经济快速发展的需求，最好的解决方法是建立城市的智能交通系统[1]。
在智能交通系统中，计算车辆到目的地的最短路径是系统的基本功能。随着交通实时信息采集手段的增多，使得智能交通系统完全可以根据实际的情况，进行由当前点到目标点的最短路径计算，以缩短车辆在途时间，提高道路的通行能力。由于实时交通状况在不断变化，时间最短路径是动态的，在实际应用中，就有必要不断进行相关的计算，以确定当前的时间最短路径[2]。
智能交通系统中最短路径的查询，主要是点到点之间的最短路径，在城市交通中具有很高的实时性，要求对大量的查询给予快速答复。有关最短路径的算法， 经典的有Dijkstra[3]和Floyd[4]算法， 但由于空间的限制， 现在基于实时系统计算的最短路径往往使用Dijkstra 算法或基于其上的一些变形算法，文献[5]列出并比较了一些常用的实现方法。本文针对智能交通系统中实时变化的道路信息，提出基于洪泛查询的最短路径算法来求解智能交通系统中动态变化的道路信息的最短路径，该算法还同时兼顾多条次优路径来作为备用路径，一旦最优路径上某个部分发生拥塞情况就可以快速切换到备用路径。
1 算法设计
1.1 问题描述
本文针对的是城市交通路网中最短路径求解的问题，在进行问题描述时，将交通路网映射为一个带权有向图模型，路网的交叉点为图的节点，路径为图的边，边为带权的有向图，表示是双向通行道路还是单行道。因此，该路网可描述为：带权有向图G=（V，E，w） ，其中，V 是包含N个节点的节点集，E是包含m条边的边集，
从源点S到终点D的路径可能有多条，其中的Wmin为最短路径。如何找出其中的最短路径呢？本文设计了一种基于洪泛查询的最短路径搜索算法。
1.2 算法描述
基于洪泛查询的最短路径搜索算法采用了洪泛的思想，从源点S出发，向所有与之直接相连的节点发送数据，中间节点收到数据之后，向除收到数据之外的所有节点转发数据（S，Vm，P（s，m），W（s，m）），其中S为源点，Vm为当前节点，P（s，m）为从源点到当前节点的路径，W（s，m）为从源点到当前节点的权值的总和。最先到达的终点的那条路径为最短路径。该算法的可以适应时刻变化的城市路网交通，特别是在实时性非常强的智能交通中，城市中各条道路由于交通事故，施工等各种原因通畅和拥塞程度随时发生变化，该算法只要有任何一条能到达终点的路径都可以被搜索到，健壮性非常好。
图1所示是一个交通路线示意图。从源点S到目的地D，中间有若干个节点，节点之间边表示路径，路径上的权值表示经过该路径所需的时间，权值越大，所需时间越长。要找出源点S到目的D的最短路径也就是找出权值之和最小的路径，根据本文的算法，最短路径的求解过程为：
图1 交通路线示意图
从源点S出发，与S直连的节点有三个：V1，V2，V3，根据洪泛的思想，S会向所有与之相连的节点发送信息，于是，三个节点V1、V2和V3都会收到来自源点S的信息，于是这三个节点都会记录来自S的信息：
S->V1（S， V1， （S， V1）， 10）；
S->V2（S， V2， （S， V2）， 5）；
S->V3（S， V3， （S， V3）， 8）
同时，在洪泛的方式下，V1会把来自S的信息发送给V2，V2会把来自S的信息发送给V1和V3，V3会把来自S的信息发送给V2，于是V1、V2、V3又会记录以下信息：
S->V1（S， V1， （S， V2，V1）， 7）；
S->V1（S， V1， （S， V3， V2， V1）， 15）；
S->V2（S， V2， （S， V1， V2）， 12）；
S->V2（S， V2， （S， V3， V2）， 12）；
S->V3（S， V3， （S， V2， V3）， 9）；
S->V3（S， V3， （S， V1， V2， V3）， 16）
根据权值比较，选择最短的路径即权值最小的路径为：
S->V1（S， V1， （S， V2， V1）， 7）；
S->V2（S， V2， （S， V2）， 5）；
S->V3（S， V3， （S， V3）， 8）
同理，与V1直连的有V4，与V2直连的有V5，与V3直连的有V6，所以V4会收到来自V1的信息，V5会收到来自V2的信息，V6会收到来自V3的信息，于是从源点S出发到V4、V5、V6的路径信息为：
S->V4（S， V4， （S， V2， V1， V4）， 13）
S->V5（S， V5， （S， V2， V5）， 14）
S->V6（S， V6， （S， V3， V6）， 16）
在它们各自收到信息之后，由于洪泛的原理也会转发给其它相邻的节点，于是V4、V5、V6的其它路径信息为：
S->V4（S， V4， （S， V2， V5， V4）， 16）；
S->V4（S， V4， （S， V3， V6， V5， V4）， 23）；
S->V5（S， V5， （S， V2， V1， V4，V5）， 15）；
S->V5（S， V5， （S， V3， V6， V5）， 21）；
S->V6（S， V6， （S， V2， V1， V4， V5， V6）， 20）；
S->V6（S， V6， （S， V2， V5， V6）， 19）
根据权值比较，选择最短的路径即权值最小的路径为：
S -> V4 （S， V4， （S， V2， V1， V4）， 13）；
S -> V5 （S， V5， （S， V2， V5）， 14）；
S-> V6（S， V6， （S， V3， V6， 16）
最后，V4、V5、V6都直连到目的地D，所以到D的路径分别为：
S ->D （S， D， （S， V2， V1， V4， D）， 19）；
S-> D （S， D， （S， V2， V5， D）， 20）；
S -> D（S， D， （S， V3， V6， D）， 20）
根据权值比较，选择最短的路径即权值最小的路径为：
S -> D （ S， D， （S， V2， V1， V4， D）， 19）
这条路径即为从源到目的最短路径，其实在计算的时候有三条可达路径，其中一条为最短路径，其余两条可以作为备用路径，一旦其中一条路径出现问题时，可以快速切换到另外一条备用路径。例如当到达V2点时，发现V1到V4的路径发现了拥塞，那么此时可以立即切换到另外一条路径：S -> D （S， D， （S， V2， V5， D）， 20）。
1.3 时间复杂度分析
在该算法中，每个节点会收到来自所有入度的数据，并根据权值的大小进行比较，选择权值最小的那条路径信息向所有的出度进行转发，所以该算法处理的时间复杂度只跟边的数量有关，所以时间复杂度为O（n），n为边的数量。
2 实例分析
现以前面算法描述中的图1为例来分析该算法的工作过程和特点。
首先起点S向直接的节点V1、V2、V3发送洪泛信息，具体如图2所示。
图2 从源点S洪泛到直连节点
V1、V2、V3收到S的信息之后，也都会向与之直连的节点洪泛，如图3所示，节点V1向所有直连的除收到信息之外的节点（即除源节点S之外）洪泛信息。
其它的节点V2、V3做同样的操作。最后从源S到目的地D的最短路径如图4所示。
图3 节点V1向其它节点洪泛信息
图4 S到D的最短路径
该算法在计算时，可以获得三条可达路径，其中一条为最短路径，其余两条为次优路径，可作为备用路径，一旦其中一条路径出现问题时，可以快速切换到另外一条备用路径。例如当到达V2节点时，发现V1到V4的路径发生了拥塞，那么，此时可以立即切换到另外一条路径，如图5所示。
图5 切换到备用路径
3 结 语
本文提出了一种基于洪泛思想的最短路径算法， 利用洪泛的特点，在整个路网中搜索到达目的地的最短路径，在搜索最短路径的同时，还可以搜索到若干条次优路径，在最优路径出现问题时可以快速切换到次优路径，以适应智能交通系统中时刻变化的道路通畅情况。该算法的时间复杂度为O（n），跟经典的Dijkstra和Floyd算法比较，大大降低了搜索范围、提高了计算效率， 而且在保证最短路径求解的同时，还能求出备用路径， 非常适用于动态变化的智能交通系统的最短路径的求解问题。
参考文献
[1]丁革媛，李振江，郑宏云. 智慧城市的应用体系架构研究[J].微型机与应用，2013，22（24）：1-3.
[2] 王元彪.智能交通系统中 Dijkstra 算法的高效实现[J].计算机工程，2007，33（ 6）：256-261.
[3] Dijkstra E W. A note on two problems in connection with graphs[J].Numerische Mathematik， 1959（1）： 269- 271.
[4] Floyd R N. Algorithm 97 shortest path [J]. Comm ACM， 1962， 5 （6）：345.
[5] Zhan F B. Three fastest shortest path algorithms on real road networks： data structures and procedures [J].JGIDA， 1998， 1（1）： 69-82.
