基于改进PageRank算法的路网重要交叉口筛选方法

（1.浙江工业大学信息工程学院，浙江杭州310023；2.杭州通悟科技有限公司，浙江杭州310000）

（1.浙江工业大学信息工程学院，浙江杭州310023；2.杭州通悟科技有限公司，浙江杭州310000）

为便于对饱和交通状况下的城市道路交叉口进行分级管理，需解决城市道路交叉口的重要性排序问题，综合考虑全路网中各交叉口之间的静态结构连接关系和动态流量影响，在改进PageRank算法的基础上，提出了能够反应全路网动态变化的交叉口繁忙程度指标，并将该指标用于路网重要交叉口排序筛选来分析交叉口的状态.研究结果表明：排序越靠前的交叉口越繁忙也越重要，交叉口繁忙程度指标综合考虑了全路网交叉口状况，弥补了以饱和度为评价指标只能片面衡量单个孤立交叉口状态的不足，更准确地反映了饱和交通状况下交叉口之间的相互影响；本文方法排序结果与饱和度评价指标排序结果相比，40%交叉口的排序升降幅度在3位以内，30%交叉口的排序平均下降了7位，其余30%交叉口的排序平均上升了8位.该研究结果为饱和交通状况下交叉口的合理分级提供了量化手段，有助于及时发现急需管控的交叉口.

交叉口；连接关系；PageRank；排序

路网中的交叉口具有两种属性.一种属性是其构成路网物理结构的静态拓扑特性；另一种属性是其输送交通流能力的动态时变特性.拓扑特性取决于路网设计阶段，属于先天特性.时变特性则既与拓扑特性有关，更受路网交通运行状态的影响，所以该特性已成为交通管控中的重要因素.

当路网交通流量较低、各相邻交叉口之间的相互影响较弱时，通常采用交叉口饱和度或通行能力等单一指标评价各交叉口的当前状态［1-3］，据此筛选出需要重点管控的关键交叉口.对交叉口排序的主要依据是饱和度量化指标，仅孤立地观察各个饱和度较高的交叉口.然而，当路网交通运行处于饱和状态时，各交叉口的动态特性受到与其具有连通关系的其他交叉口交通流变化的影响，仅孤立地观察饱和度高的交叉口难以发现问题所在.因此，在饱和状态下，从路网角度出发，充分考虑交叉口之间的相互影响关系，筛选出对路网运行效率有重要影响的关键交叉口，并对这些关键交叉口统一采取管控措施具有重要意义.

文献［4］提供了一些指标对路网中的交叉口进行量化排序，比如交叉口饱和度、通行能力、平均延误时间等.但这些评价指标只能孤立地反映交叉口本身的动态特性，难以体现出每个交叉口在静态路网中固有的结构特性，更不能体现出路网资源紧张情况下各交叉口之间较强的关联和相互影响特性.而这些因素才是揭示和衡量交叉口在路网中重要性的关键依据.

为了能够合理地对路网中的交叉口进行重要性分析，筛选出关键交叉口，为制定交通管控措施提供科学依据，本文借鉴PageRank网页排序算法，在综合考虑交叉口之间的静态连接关系和动态流量影响关系基础上，提出一种路网重要交叉口筛选方法，并通过实例对提出的方法进行分析验证.

1 PageRank算法

PageRank算法是Google的两位创始人Sergey Brin和Larry Page建立的一种搜索引擎算法，该算法将网页排序与网页的一些相关因素相联系［5］. PageRank算法的主要思想是，首先，如果一个网页被很多其他网页所链接，说明它受到普遍的承认和信赖，那么它的排序就高；其次，它借鉴了传统引文分析思想，当网页A有一个链接指向网页B，就认为B获得了A对它贡献的分值，该值取决于A本身的重要程度，即网页A的重要性越大，网页B获得的贡献值就越高［6-7］，计算方法见式（1），

式中：DPR（P）为网页的PageRank值；

d为阻尼因子，取值范围为0＜d＜1，存在阻尼因子是因为并不是所有用户都会顺着网页的超链接浏览，一般取d=0.85；

T1，T2，…，Tn为指向网页P的网页；

DPR（Ti）为指向网页P的网页Ti具有的PageRank值；

NTi为网页Ti具有的导出链接数.

2 路网重要交叉口筛选方法

2.1 改进PageRank算法的交叉口筛选方法分析

根据PageRank算法，在对路网交叉口进行分析时，本文将交叉口各进口道流量作为研究参量，考虑交叉口之间的相互连接及影响关系，主要指各交叉口各进口道的交通流量转向比.

以图1描述的路网为例，分析路网重要交叉口筛选方法的实现过程.图1共包含4个交叉口，交叉口之间存在连通关系，其相互影响主要通过各出入口的流量反映.以交叉口1为例，出口1是交叉口1的出口，同时又是交叉口2的入口.出口1的流量与该交叉口其他方向的入口1、2、3的流量密切相关（在此暂不考虑掉头方向）.

图1 路网示意图Fig.1 Simplified road network

由图1中各入口的转向关系，出口1的流量为

式中：Fent1、Fent2、Fent3分别为入口1、2、3的流量；

RL、RS、RR分别为对应入口的左转流量比、直行流量比、右转流量比.

用式（2）计算出每个交叉口的出口流量.根据交叉口之间的连接及影响关系，各出口流量对其他交叉口入口流量有所贡献.可以按照PageRank算法的计算过程，考虑交叉口之间的相互连接以及影响关系，以流量作为参数计算各交叉口的I值.

式中：I（Yj）为交叉口Y第j入口道的排名值；

k（Zi）为交叉口Z第i入口道对应的转向比；

I（Zi）为交叉口Z第i入口道对应的排名值；

n为与相邻交叉口Y第j入口道流量相关联的入口道数目；

CZi为各个入口道Zi的通行能力；

f为流量修正因子，因为驶出上一个交叉口的车辆未必全部驶入下一个交叉口.

考虑交叉口有多个入口道，且各入口道受通行能力的限制，不能直接地将排名值Ii作为筛选依据，本文将该指标修改为

式中：I（Z）为将交叉口Z各个进口道的Ii最大值作为交叉口繁忙程度的排名值.

繁忙程度类似网页中的PageRank值，某交叉口的繁忙程度是根据与其关联的其他交叉口繁忙程度综合计算而获得的.与传统的仅针对单个交叉口进行分析的饱和度或服务水平的计算方式不同，本文是在综合分析整个路网后计算每个交叉口的繁忙程度.

2.2 路网中重要交叉口筛选方法

本文参考PageRank算法，同时考虑流量分配和转向问题，获得交叉口的指标数据后，依据交叉口繁忙程度对交叉口的重要性进行排名分析，进而筛选出重要的交叉口.该方法步骤如下：

（1）获得交叉口各入口道流量及转向比

通过检测器获得交叉口各入口道的交通流量，用统计方法获得各入口方向的转向比.通过在交叉口出入口道安置交通检测器，根据在一段时间内检测器获得的数据统计入口及出口的流量，便可获知各方向的转向比.

（2）计算相邻交叉口各入口道的Ii值

在获得交叉口各入口道流量及转向比后，可根据路网中交叉口的相互连接关系，计算每个相邻交叉口各入口道的Ii值.

（3）更新各交叉口各入口道的Ii值

在获得各交叉口入口道的Ii值后，按照路网中交叉口出口道与入口道的关系，更新入口道Ii值信息.

（4）迭代计算交叉口各入口道Ii值

在计算交叉口入口道Ii值时，需要进行迭代运算，达到一定的次数时，Ii值基本维持不变.

（5）获取各入口道Ii（Zi）值

将交叉口各入口道繁忙程度最大值作为交叉口繁忙程度值，从大到小对路网中各交叉口进行排序，排名越靠前，其重要程度越高.

交叉口繁忙程度越高，证明该交叉口拥堵对路网交通运行效率的影响越大.

3 路网的存储

由上述分析可知，在对路网交叉口进行筛选时需要获取交叉口之间的连接关系以及各个交叉口的属性（交叉口的通行能力、流量、转向比等）.因此，需要设计路网的存储结构来保存路网的连接关系以及各交叉口的属性.

在图论中，图的存储方式有邻接图、邻接表和前向关联边3种基本结构.由于道路网络属于大型稀疏网络，并且具有节点权重等属性，本文选择前向关联边结构存储路网及节点权重［8］.

前向关联边结构最重要的思想是，将同一个节点发出的所有弧放在同一个数组中，并用长度为n（n为节点个数）的指针数组Pointer表示，数组中每个指针对应一个节点，指针指向该节点所发出的第1条弧；用长度为m（m为弧的条数）的数组PointNode存储指针数组中指针所指向的节点；用长度为n的数组Nature存放节点对应的饱和度和通行能力［9］.图2和图3为前向关联结构.

图2 路网关联关系示意图Fig.2 Correlations of intersections

在进行路网存储时，首先应标明每个交叉口的序号，另外还要从序号小的交叉口开始标明每个交叉口的前向边序号（图2）.将交叉口按序号从小到大存储到Node数组；Nature存储相应的交叉口属性.以图1中交叉口1为例说明路网存储的用法.交叉口1与交叉口2、3、4相连，所以PointNode数组包括交叉口2、3、4，PointNode最先出现的是交叉口2，交叉口1、2之间的前向边序号为1，所以Pointer数组中数为1.其余交叉口以此类推，可得到如图3所示的前向关联边结构.

图3 前向关联边结构Fig.3 Forward star structure

图3中用长度为6的数组Pointer存储与节点相关的数据；另外用一个长度为15的数组PointNode存储与弧相关的数据；长度为6的Nature数组存储节点的属性.这样仅用了2n+m的存储量便可存储了整个路网以及各节点的属性，大大节省了存储空间.

4 实验分析

4.1 实验方案设计

为了对改进PageRank算法的路网交叉口筛选方法进行测试，本文设计的实验方案主要体现多交叉口连接关系对交叉口重要性程度的影响.设计方案考虑如下因素：首先，对多交叉口进行重要性排序，然后考虑各交叉口之间的相互连接及影响关系，我国城市道路按照功能分为快速路、主干路、次干路及支路［10］，根据道路类别的不同，各级道路之间的连接关系也不尽相同.因此，设计实验路网（如图4所示）包含20个交叉口.

图4中交叉口各进口（东、西、南、北）的交通流量、各进口各车道（左转、直行及右转）的转向比见表1和表2.

4.2 实验数据分析

为分析本文提出方法的合理性，分别采用传统的计算交叉口饱和度值的方法与本文基于改进PageRank算法计算交叉口繁忙程度的方法，对路网中的交叉口进行排序筛选，排序结果及其对比见表3、表4和图5.

由表3、表4和图5可以看出，两种筛选方法的排序结果差别明显.按照饱和度值进行排序，突出了各交叉口所辖范围的饱和程度，其意义是能够指导管控决策，逐个针对点（交叉口）进行处理和改善，但难以从全路网角度做出系统化的决策.因为，某个点（交叉口）饱和度高可能是由于与其关联的其他点（交叉口）饱和度低引起的，但用现有方法难以发现这种隐藏的原因.比如交叉口A、B相连，前者饱和度为0.6，后者饱和度为0.5，交叉口A车流量流向B，因而交叉口A的饱和度会影响交叉口B，所以最终判定交叉口A、B哪个更重要将比较困难.

图4 实验路网Fig.4 Experimental road network

表1 交叉口各进口交通流量Tab.1 Traffic volumes of intersection inlets pcu/h

以交叉口1为例，其饱和度为0.36，在饱和度排序方法中排序为20.然而，因其与交叉口2、5相连，而这两个交叉口饱和度较高，因此车流量势必会影响交叉口1，造成交叉口1车流量增加.按照本文的方法，计算出其繁忙程度为0.69，排名为第11.

表2 交叉口各进口车道转向比Tab.2 Turning rates of intersection inlets

表3 饱和度排序结果Tab.3 Ranking results in saturation

本文方法与传统方法的重大区别在于，本文改进PageRank算法的筛选方法是从整个路网角度出发计算出每个交叉口的繁忙程度值，该值隐含了某交叉口对其他相关联交叉口的影响以及在路网中的重要地位.即本文提出的方法不仅能发现显性的问题交叉口，更能挖掘出潜在的问题交叉口，进而能够指导交通管控决策从全局出发，将显性和隐性的问题交叉口系统地进行处理.能够及时发现潜在的问题交叉口，是本文所提方法的重要价值所在.

表4 本文算法排序结果Tab.4 Ranking results by PageRank algorithm

传统的依据饱和度排序方法，关注的是每个孤立的点（交叉口），发现每个孤立点的拥堵问题.该方法的这种局限性导致交通管控策略的制定也基本上是逐点解决问题，因为忽略了潜在问题点，往往导致拥堵点转移.以改进PageRank算法进行排序的方法，关注的是整个路网，在计算过程中考虑了所有交叉口，在全局范围内发现整体中的问题点，更全面和系统地解决问题.

图5 两种方法比较Fig.5 Comparison of ranking results between two algorithms

综上所述，本文提出的基于改进PageRank算法的交叉口筛选方法，突破了传统方法孤立地评价交叉口的局限性，能够从全路网出发，对各交叉口在路网中的重要程度进行排序；此外，本文方法还能够揭示具有逻辑连通关系的交叉口之间的相互影响程度，排序结果能够对交管部门改变及制定交通管控决策提供新的思路和重要的参考依据.

5 结束语

借鉴PageRank网页排序算法，综合考虑城市路网的静态连接关系和动态交通流量对各交叉口的影响，对PageRank算法进行了改进，提出了从全路网角度出发计算各交叉口繁忙程度指标，对城市路网交叉口进行重要性筛选的计算方法；其计算结果一方面能够体现交叉口在路网中的重要程度，另一方面也揭示了该交叉口对与其具有逻辑连通关系的其他交叉口的影响，既能发现显性的问题交叉口，也能够发现隐性的问题交叉口.

在饱和交通时代，道路交通系统时空资源日趋匮乏，全面系统地评价和筛选出路网中的重要交叉口并对其实施科学管控，使有限的时空资源得到最大化的利用是当前及未来城市交通管控所面临的棘手问题，本文对解决该问题提供了一种可操作的理论方法.

［1］ WANG Q，SHAO C F.Evaluationofsignalized intersection service level in the traffic impact assessment［J］.Advanced Materials Research，2014，869：327-333.

［2］ CHAUDHRY M S，RANJITKAR P.Capacity and signal timing analysis of signalized intersections with increasing saturation flow rate［C］∥Transportation Research Board 92nd Annual Meeting. Washington D. C.：Transportation Research Board，2013，Paper Number：13-3396.

［3］ 杨晓光，赵靖，马万经，等.信号控制交叉口通行能力计算方法研究综述［J］.中国公路学报，2014，27（5）：148-157. YANG Xiaoguang，ZHAO Jing，MA Wanjing，et al. Review on calculation method for signalized intersection capacity［J］.China Journal of Highway and Transport，2014，27（5）：148-157.

［4］ 刘娟，孙建平，刘梦涵，等.微观层次城市道路交通拥堵评价指标的研究［C］∥2007第三届中国智能交通年会论文集.南京：东南大学出版社，2007：268-272.

［5］ PAGE L，BRIN S.The anatomy of a large-scale hypertextual web search engine［J］.Computer Networks and ISDN Systems，1998，30（7）：107-117.

［6］ HAVELIWALA T H.Topic-sensitive PageRank：a context-sensitive ranking algorithm for web search［J］. IEEE Transactions on Knowledge and Data Engineering，2003，15（4）：784-796.

［7］ 冯振明.Google核心：PageRank算法探讨［J］.计算机技术与发展，2006，16（7）：82-84.

FENG Zhenming. Google'score：discussion about PageRank algorithm［J］. ComputerTechnologyand Development，2006，16（7）：82-84.

［8］ 姜桂艳，郑祖舵，于妍霞.交通诱导系统中道路网络的表达与存储方法［J］.吉林大学学报，2008，38（4）：797-801.

JIANG Guiyan， ZHENG Zuduo，YU Yanxia. Representation and storage method for road network of traffic guidance system［J］.Journal of Jilin University，2008，38（4）：797-801.

［9］ DIAL R，GLOVERF，KARNEYD，etal.A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees［J］. Networks，1979，9（3）：215-248.

［10］ 徐吉谦，陈学武.交通工程总论［M］.北京：人民交通出版社，2008：120-124.

基于改进PageRank算法的路网重要交叉口筛选方法

郭海锋1， 张昌世1， 穆元杰1， 郑雅羽1， 贡 伟2

Dynamic Sorting Method for Road Network Primary Intersections Based on PageRank Algorithm

GUO Haifeng1， ZHANG Changshi1， MU Yuanjie1， ZHENG Yayu1， GONG Wei2
（1.College of Information Engineering，Zhejiang University of Technology，Hangzhou 310023，China；2.Hangzhou Tongwu Technology Ltd.，Hangzhou 310000，China）

In order to classify intersections of a city under saturated traffic operating conditions，sortby-importance measures for intersections should be provided.Considering the static connections and dynamic influences of traffic volume between intersections，a key busyness index that can reflect the busy degree of each intersection in the road network is proposed on the basis of a modified PageRank algorithm.This busyness index is then used for sorting important intersections in the road network and analyzing their situations.Results show that the intersections that are sorted in the front are very busy and important.By taking into consideration of the whole intersections in a road network，the busyness index can make up the disadvantage of the saturation index that can only evaluate the situation of single intersections，and therefore is capable of reflecting accurately the mutual influences of the connection relations among intersections under saturated conditions.Compared with the sorted results by saturation index，the ranking orders by business index of 40%intersections change within 3 positions，30%drop by 7 positions，and 30%rise by 8 positions.The obtained findings can be used to classify intersections of a city under saturated traffic conditions to timely find the key intersections.

book=926,ebook=115

intersections；connected relations；PageRank；sorting

0258-2724（2016）05-0925-06

10.3969/j.issn.0258-2724.2016.05.015

U491.232

A

2015-04-29

浙江省自然科学基金资助项目（LY14F030012）；中国博士后基金资助项目（2012M511387）

郭海锋（1977—），男，博士，副教授，研究方向为智能交通系统、交通信息处理，E-mail：guohf@zjut.edu.cn

郑雅羽（1978—），男，博士，副研究员，研究方向为智能辅助驾驶、车联网系统，E-mail：yayuzheng@zjut.edu.cn

郭海锋，张昌世，穆元杰，等.基于改进PageRank算法的路网重要交叉口筛选方法［J］.西南交通大学学报，2016，51（5）：925-930.

（中文编辑：秦萍玲 英文编辑：兰俊思）