基于改進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.

（中文編輯：秦萍玲 英文編輯：蘭俊思）