张 媛，刘 峰
（南京邮电大学 图像处理与图像通信江苏省重点实验室，江苏 南京 210003）
摘 要： 采用改进的层次分析法分析道路状况的多种因素，得出了当道路发生紧急事故时，符合时效性、安全性、经济性的路段权值。然后根据实时交通信息，利用改进的Dijkstra算法，探索了路径权重计算方法，建立了交通网络的运行时间的加权图，验证了本方法在实际交通网络中的应用，证实了方法的有效性和可行性。
关键词：智能交通系统；最优路径；层次分析法；Dijkstra算法
0 引言
随着城镇人口的增长和可用物理空间的日益缺乏，交通管理面临的挑战越来越严峻，继续扩大道路网络来解决日益增长的交通需求已经被视为一个不可持续的方案。本文利用智能交通的动态路径选择思想，为驾驶员提供实时最优路径，避开拥挤路段，或根据驾驶员需求提供最优路径，实现智能且人性化的路径诱导。在实际车辆行驶时，由A地到达B地的最佳路径的标准不只是道路距离、路面质量、交通拥堵、驾驶习惯等因素中的某单一标准，从驾驶员心理角度出发，依据每个人内心的不同的标准，综合考虑多种影响因素以后得出最能够接受的方案，从而获得车辆行驶的最佳选择。
目前，有十多种计算最优路径的方法，其中Dijkstra算法是理论上最完善的方法，已被GIS系统广泛采用。同时它也存在以下缺点：（1）它的计算仅仅基于道路的长度，而不考虑影响道路交通的实际因素，如道路等级、道路上的交通拥堵等其他因素，所以在复杂的交通环境中结果往往并非最优。（2）在有大量节点的交通网络中，拓扑结构中占用大量的存储空间，且遍历算法的搜索效率很低。
本文提出了层次分析法（Analytic Hierarchy Process，AHP）[1]的最优路径选择模型，运用运筹学中的AHP计算路径的权重，然后利用改进的Dijkstra算法获得最佳路径。这种复杂的路径决策算法可应用于复杂路况的选路，尤其适用于应急救援、多目标决策的情况。
1 路段权重的判定
1.1 层次分析法介绍
层次分析法是一种解决复杂、模糊问题的简单决策方法，特别是如本文讨论的“最优路径”等难以进行定量分析的问题。现实情况是不仅道路的长度不同，受到交通状况、路面质量、天气条件等因素的影响，各道路上的车辆行驶时间都会不同。采用层次分析法，所有这些因素都被考虑，通过各自不同的重要性影响路径权重。于是得到了一个更贴近现实的交通网络有向图加权图。
通常，该方法可分为三个步骤：
（1）建立层次结构模型；
（2）构造各层次的判断矩阵；
（3）实施层次排序和一致性检验。
1.2 建立层次分析法模型
本文考虑了现实条件下可能影响驾驶员路径选择的因素，除了一些常见的因素（如路径距离，道路等级，车辆限制，交通流量，气候条件）[2-4]以外，如果车辆前方路段突然发生车祸、坍塌等严重事故，可能造成交通完全瘫痪，严重影响车辆行驶的时间成本，所以获得的实时前方路况需要实时更新。此外在复杂道路情况下，驾驶员对道路的熟悉程度也部分地影响了行驶时间。所以设定集合：S={路径距离/车速，道路等级，交通流量，车辆限制，气候条件，实时路况信息，驾驶熟悉度}。根据层次分析法的思想，将层次结构分为3层（如图1所示），最上层为目标层：路径权重W；中间层是准则层，即集合S中的各项指标；底层是方案层，即计算所得的最优路径。
在使用AHP时，必须注意矩阵的一致性。如果不满足一致性，则结果错误。Jiang Hua[5]提出的AHM方法可以避免检测一致性，从而能确保决策不会出现：a>b，b>c，得出c>a这种情况。
1.3 计算基于实时交通信息的权重值
步骤1：利用层次分析法计算准则层各指标对于目标层的权重w1、w2、w3、w4、w5、w6、w7。
对准则层的各因素按1~9标度思想分别赋值，含义见表1[6]。
准则层的各个准则占最终结果的比重不一定相同，从驾驶员的需求出发，给它们设定不同的比例。由此构造出判断矩阵，如表2所示。
步骤2：计算权重的方法有几何平均法、算术平均法、特征向量法和最小二乘法。本文选用特征向量法，公式为：
AW=λmaxW（1）
λmax为判断矩阵的最大特征值，存在唯一的W的分量为正分量，将求得的W作归一化处理即为特征向量。
步骤3：上述方法计算的判断矩阵通常是不一致的，为了获得它对应于最大特征值的特征向量，被比较因素的权重向量不一致程度应在容许的范围内，以保证其可靠性，所以必须进行一致性检验[7]。
一致性指标：
CI=（λmax-n）/（n-1）（2）
其中，n是A的阶数。RI为平均随机一致性指标，取值参考表3。
对判断矩阵的一致性进行检验：
CR=CI/RI（3）
当CR小于10%时，认为判断矩阵的一致性是令人满意的，否则应当进一步修正判断矩阵。
步骤4：在获得了各因素的权重值以后，计算路段权重，并对路段权重进行等值的无量纲处理[8]。
W=s/v（w2r+w3l+w4f+w5w+w6m+w7c）（4）
其中s是实际路段长度，v是车辆平均行驶速度，s/v则是理想情况下车辆匀速行驶所用的时间；r是道路等级，根据公路的使用任务、功能和流量划分为5个等级（0.2、0.4、0.6、0.8、1.0）；l是交通流量，与设计交通流量作比较，比值由低到高赋以[0，1]区间内的实数；f为车辆限制，表示不同类型车辆的通行是否受限于该路段，受限则f=1，否则f=0；w是天气状况，根据车辆行驶的适宜程度赋以[0，1]区间内的实数；m是实时路况信息，根据车辆获得实时路况的能力赋以[0，1]区间的实数；c是驾驶员对路段的熟悉程度，驾驶员通常主观倾向于自己较熟悉的道路，赋以（0，1）区间的实数，若取值在0附近，则选取的可能性较小。
步骤5：实时更新交通信息。
信息采集系统包括车辆信息采集设备和路边信息采集设备，将采集的信息发送到信息监控中心。为了获取各路径交通信息，更好地实现交通诱导，本文设计了一种基于socket通信[9]的模拟车辆运行状态采集方法，将车辆作为客户机，采集中心作为服务器，采用TCP/IP通信协议。通信流程图如图2。
每一个客户机代表一辆车，客户机程序产生以下信息，向服务器发送，如表4。
服务器接收以上客户机发送的数据，得出某一路段的实时道路信息，若大量车聚集在某一个路段，则可判断该路段的权重增大。结合路边信息采集设备获得的数据和驾驶员自身判断因素，可以得到准则层7个影响判决因素的模拟数值。
2 综合最优路径算法
2.1 Dijkstra算法介绍
Dijkstra[10]算法是图论中求解最短路径的一个著名的算法，用于求图中一个节点到其他各个节点的最短路径。将道路抽象为图论中的边，交叉口抽象为节点。道路相关的参数影响边的权值，权值是广泛的，可以表示速度、天气情况、交通情况、距离等。衡量最短路径的准则是计算出的路径权值W的大小，并且边的权值都是非负数。网络中所有节点初始化为未标记节点，在搜索过程中与最短路径中的节点相连通的节点称为临时标记节点，每次循环都从临时标记节点开始搜索距源点最短的路径长度的节点，将其变为永久标记节点。直到所有节点都成为永久标记节点，算法运行结束。
传统的Dijkstra算法是从起点V到图的剩余顶点的最短路径的长度增加的序列，它用于解决有向加权图的问题[11]。其基本思想是：首先建立一个节点集S，选择贪婪算法不断扩展集合S。假设所有节点的集合是V，S的初始值是源节点，T是存在于V中但不在S中的节点集，T的初始值是除源节点外的所有节点。T中的节点根据路径长度的升序逐个进入S，直到可以从源节点到达的节点全部进入S。然而，把Dijkstra算法应用到基于GIS的应急救援体系，仍存在一定的不足：（1）该算法使用O（N2）的时间找到单源最短路径，使其低效地处理GIS系统中的海量数据[12]。（2）在路径信息不变的情况下，搜索相同一对源点和目的节点时，得到的路线应该是一样的。但此算法每次寻路都要重新计算最短路径，浪费时间。（3）在传统图论网络分析中，每个路径正反向权值是相同的。而实际交通中同一条道路两个方向的路况可能差别非常大，所以在仿真时采用不同的权重因子更加符合现实情况。
2.2 对选路算法的改进
本论文对此提出以下改进：
（1）在GIS应急救援系统中因为交通网络特征的动态变化特性，一般顺序计算产生的最短路径树不能完全满足需要。例如，当汽车到达节点3，发现道路L35交通堵塞非常严重时，必须重新寻路。这时，应重新选择3的邻接结点来计算最短路径树T。从动态变化的特性出发，本文采用了逆向运行的方法，即构建一个逆向的最短路径树[13]，使源节点是终节点，且起始节点设在分支节点。此改进适用于在行车至某一节点遇到前方路段突然发生车祸、坍塌等严重事故，造成交通完全瘫痪的情况。
（2）由于相同始末节点仍然会重新搜索，造成资源浪费，每次使用Dijkstra算法搜索完最优路径后，将所有路段信息和最短路径的信息加入到数据库中。用户需要选择路线时，程序先搜索数据库，将之前保存的路线反馈出来。当城市中道路状况改变时，重新执行Dijkstra算法，更新数据库中之前所有最短路径信息[14]。
（3）在各指标对于目标层的权重系数中，交通流量、实时路况信息受到行驶方向影响较大，所以将这两个因子根据路况灵活选取，其他因子在同一条道路上数值相同。正反两个方向的计算结果可能完全不同。本文将一段路径正反向的某些参数设为不同值，这样更符合实际交通状况。
3 最优路径选择仿真实验
在研究各种路径算法后，本文选择在MATLAB平台上，实现利用AHP计算权重的改进的Dijkstra算法作为最优路径算法。
首先，根据表2的判断矩阵A，计算可得特征向量w和特征值k。经计算最大特征值为：k=7.339 2，对应的归一化特征向量为：
wT={0.4048，0.1184，0.1119，0.1592，0.1257，0.0478，0.0322}
通过MATLAB编程计算得到：
CI=0.056 5
CR=0.041 6
说明此矩阵的一致性可以接受。
然后，结合以下某地区的交通示意图3，譬如节点7到12的距离为15 km；设计平均时速为80 km/h；道路等级为一级，r=0.4；实际交通流量l=0.6；路段对车辆通行无限制，f=0；该时段天气良好，能见度较高，a=0.1；路段可以及时获得前方的路况信息，m=0.2；司机较熟悉此路段，c=0.85。本题s／v以min作为单位。利用公式（4），计算得节点7到12的权值为16.3，其余路径的权值略。
本实验由于节点数量较多，仅测试由节点9到节点12的路径，仿真结果如下：
起始点（9）到终止点（12）的路径为：9→10→6→12
路径权重：44.4
根据实时采集的交通信息，若大量车辆行驶在10→6路段，则该路段极其拥堵，此路段的交通流量l无限接近于1，计算路径权重变为56.5，数值明显增大。
再测试一次选路结果：
起始点（9）到终止点（12）的路径为：9→11→4→7→12
路径权重：45
可以看出，新选择的最优路径权重远小于56.5，本算法是方便可行的，并且同时可以得到任意起点i到终点j的最短路径。
4 结论
对于最优路径算法的研究，本文充分考虑了各因素对行驶速度的影响，将层次分析法引入应急救援系统，分析计算得出了各因子的相对重要度。据此提出了一种基于实时路况的路径权重计算方法，采用基于经典Dijkstra算法进行改进的路径搜索算法，使计算值更符合现实，实现了系统的时效性、安全性、经济性。在本文中，该算法模型在遇到紧急情况时，结合交通实况能做出最佳决策，具有很强的现实意义。
参考文献
[1] Yang Fujin， Tan Wenan， Shen Weiming， et al. A dynamic critical path computation algorithm for enterprise process cooperative scheduling[C]. Computer Supported Cooperative Work in Design （CSCWD）， 2010 14th International Conference on. IEEE， 2010：606-610.
[2] Li Caixia， ANAVATTI S G， RAY T. Analytical hierarchy process using fuzzy inference technique for real-time route guidance system[J]. Intelligent Transportation Systems， IEEE Transactions on， 2014， 15（1）：84-93.
[3] Yang Shu， Li Chunhua. An enhanced routing method with Dijkstra algorithm and AHP analysis in GIS-based emergency plan[C]. Geoinformatics， International Conference on， 2010：1-6.
[4] Qi Guanghui， Huang Ronggang， Zhe Zeng， et al. An AHP based multi-factors weight method for route selection of oil and gas pipelines[J]. Science of Surveying and Mapping， 2013， 38（5）：122-125.
[5] Zhou Binbin， Chen Xuebo. Path selection algorithm based on AHP for small-world with three-weight[C]. Control and Decision Conference， Chinese.IEEE， 2014：3627-3631.
[6] 张慧.基于层次分析法的应急救援最优路径选择分析[J].交通标准化，2014（3）：68-71.
[7] Ma Wenjing， Xu Yingzhuo， Xie Hui.The optimal path algorithm for emergency rescue for drilling accidents[C].Network Infrastructure and Digital Content， 2009.IC-NIDC 2009.IEEE International Conference on. IEEE， 2009：866-870.
[8] 江文奇.无量纲化方法对属性权重影响的敏感性和方案保序性[J].系统工程与电子技术，2012，34（12）：2520-2523.
[9] Song Guoqing. The study and design of network traffic monitoring based on socket[C]. Computational and Information Sciences （ICCIS）， 2012 Fourth International Conference on， 2012：845-848.
[10] YERSHOV D S， LAVALLE S M. Simplicial Dijkstra and A*algorithms： from graphs to continuous spaces[J]. Advanced Robotics， 2012， 26（17）：2065-2085.
[11] Yin Tieyuan， Yang Jianyong. Dynamic application of the path selection in the road[C]. Proceedings of 2010 IEEE International Conference on Software Engineering and Service Sciences， 2010.
[12] 李宽荣，陆通，高勇.一种基于STL的高效最短路径算法[J].科技创新导报，2014（12）：37-37.
[13] 任刚，王炜.转向约束网络中的对偶最短路径树原理及其原型算法[J].交通运输工程学报，2008，8（4）：84-89.
[14] 刘帅修.智能交通中的路径选择及其移动终端信息展示系统[D].南京：南京邮电大学，2012.