智能交通最短路径Dijkstra模糊动态方法分析

周 佳，沈 岩，夏 宇，韩大明

（东北林业大学 交通学院，黑龙江 哈尔滨150040）

伴随着城市化的发展，最短路径选择问题已经成为解决交通问题的关键。与此同时，许多解决这一问题的方法也应运而生，如零空间LDA法、PCA结合LPP法等。但这些方法普遍受算法求取离散值分类的影响，速度较慢，而本文提出了一种基于模糊的Dijkstra最短路径的动态算法，能很好地解决这一问题。

目前，Dijkstra算法是公认的处理最短路径的较好方法，由于它只处理数字，许多语言变量的数量优化方法不能直接应用于模糊数，因此，Dijkstra算法在使用前需要进行修改。许多典型的做法是通过去除模糊化的方法把模糊数转化为确定数。在应用模糊算法时，需要解决三个关键问题:量化的语言变成模糊数，采用梯级平均综合表示方法使两个数相加的和可用一个确定数来表示，从而在Dijkstra算法中被轻易实现。

该算法的复杂性为O（｜E｜＋｜V｜log｜V｜，其中｜V｜为顶点的数目，｜E｜为边数），该算法不适于在模糊环境下应用，因此，本文应采用模糊集理论修改该算法。首先，利用模糊数代表用户的参数，然后用模糊数的模糊算法来找到最短路径，得到模糊的Dijkstra算法（FDA），因此，FDA处理模糊最短路径问题更具灵活性和有效性。此外，FDA的特点之一就是模糊数间不具有秩序关系。

1 数学模型

1.1 Dijkstra算法概述

Dijkstra算法是由荷兰计算机科学家Dijkstra在1956提出的，是典型的最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层扩展，直至扩展到终点为止。最终Dijkstra算法通过层层迭代能得出最短路径的最优解。本文算法是在Dijkstra算法的基础上结合模糊理论求最优解算法。

1.2 Dijkstra算法流程

如图1所示，设A为源点，求A到其他各顶点（B，C，D，E，F，G，H，I，J，K，L）的最短路径。线上所标注为相邻线段之间的距离，即权值。求各点最短路径的流程，如图1所示。

图1 加权连通

2 模糊Dijkstra算法流程

模糊逻辑处理不确定性的影响因素较多，如语言的模糊性和人类介入等因素。还有一些情况也会影响到驾驶员对路径的选择，如旅行时间、旅行距离、交通信号数、娱乐路线、路径驾驶困难等因素。旅行时间、旅行距离等因素也可被用于寻找最短路径，因此，当同时考虑到交通信号数、娱乐路线、路径困难等多种因素的路线才是最佳路线，所以，可以通过模糊理论得到将多种情况综合考虑后的最佳路线。

2.1 模糊Dijkstra算法具体步骤

模糊Dijkstra算法流程如图2所示，具体运算可以分为5个步骤，如下所示。

步骤1:构建一个网络G＝（V，E），V为顶点集，E为边的集合；

步骤2:获得交通信号的三角模糊数（见图3）或梯形模糊数（见图4），每边的边权值根据具体的道路情况，如娱乐路段、繁忙路段、驾驶难度等因素进行设置；

图2 Dijkstra算法流程

图3 三角模糊数

图4 梯形模糊数

步骤3:使用模糊数运算来添加收费关卡质量路段的模糊参数；

步骤4:使用模糊化方法计算每个边缘的危险因素；

步骤5:计算所有可能路径中的PI，使用Dijkstra最短路径算法计算出从源顶点s到所有其他顶点的最短路径值。

运用模糊Dijikstra最短路径算法找到每个顶点的最短路径，并结合给定源点模糊值进行运算。首先，找到最短路径从源点到一个拥有和它最近模糊值的顶点；然后找到第二近的顶点，依此类推；直至找到所有顶点最短路径。

2.2 算法的实现伪码

2.3 两种算法计算过程

图5所示为一个简单的交通网络，共拥有5个节点和6条路线。从节点a到d有两条路线:一条为a→b→c→d；另一条为a→b→d。用更加确切的模糊数在最短路径问题中的方式表达其路线为a→b→c→d，通常可以用两种算法进行计算。

2.3.1 dijkstra算法计算过程

2.3.2 模糊dijkstra算法计算过程

图5 一个简单的交通网络

结果表明74／6好于153／6。这里的动态路径采用基于Dijikstras算法与模糊参数相结合的算法，通过利用典型的加法运算，其结果为一个清晰的没有模糊数的排序过程。

在图6中以城市a作为源节点，城市a将移动到其它3个城市，计算从源节点到其它3个顶点的距离:在它们中，最短的距离是a或者b到3个顶点的路线，权值为6.66；下一个最短路径为b或者d到其它点的路径，路线权值为14.76；接着，城市c从b中被选择出来的权值为16.99；最后，城市e从b中被选择出来的权值为18.82；剩下的城市成为一个空集，这个搜索得以完成。其计算机仿真结果（见图7）显示了模糊算法的高效性，其交通网络路线的梯形模糊数隶属函数如表1所示。

图6 Dijkstra模糊算法举例应用

图7 模糊Dijkstra算法在简单交通网络中的仿真结果

表1 隶属函数参数计算表

3 结 语

通过对Dijkstra算法进行分析，求解具有模糊参数的最短路径。解决了三个关键性问题:一是如何添加模糊参数；二是如何通过模糊化确定路径权值，并用其模糊数表示，使用简单的网络问题例子说明了模糊Dijkstra算法的高效性；三是通过本算法可以比较并确定两个不同路径间的最短模糊化距离。该方法大大优化了交通系统，可以应用于许多方面，例如火警、救护车的救援路线选择、市民出行时的道路提醒等，能有效地解决城市道路拥堵、道路禁行等实际问题，对促进社会和谐具有一定积极作用。

［1］王林，石剑锋.智能交通系统中几种最短路径算法分析［J］.2009，54（4）:1008－5696.

［2］王树西.改进的Dijkstra最短路径算法及其应用研究［J］.计算机科学，2012（5）:223－228.

［3］陈亮，何为，韩力群.城市交通最优路径算法［J］.智能系统学报，2012，7（2）:1673－4785.

［4］谢海涛，宋奇文.基于交通仿真的区域交通协同优化控制系统［J］.交通科技与经济，2014，16（3）:4－7.

［5］邹涛，陈峰，张凯.智能交通系统中综合地图匹配算法［J］.交通科技与经济，2014，16（2）:48－51.

［6］M.xu，Y.Liu，Q.Huang，Y.Zhang，G.Luan；An improved Dijkstra shortest path algorithm for sparse network，Applied Mathematics and Computation 2007，185:247－254.

［7］X.Lu，M.Camitz；Finding the shortest paths by node combination，Applied Mathematics and Computation 2011，217:6401－6408 .

［8］S.T.Liu，C.Kao；Network flow problems with fuzzy arc lengths，IEEE Transaction on Systems，Man，and Cybernetics，Part B:Cybernetics 2004，34:765－769.

［9］R.E.Belman and L.A.Zadeh；，Decision making in a fuzzy environment，Management science，1970，17，B141－B164.

［10］C.C.Chou.；The canonical representation of multiplication operation on triangular fuzzy numbers，Computers and Mathematics with Applications 2003，45:1601－1610.