基于改進(jìn)PageRank算法的路網(wǎng)重要交叉口篩選方法

（1.浙江工業(yè)大學(xué)信息工程學(xué)院，浙江杭州310023；2.杭州通悟科技有限公司，浙江杭州310000）

（1.浙江工業(yè)大學(xué)信息工程學(xué)院，浙江杭州310023；2.杭州通悟科技有限公司，浙江杭州310000）

為便于對飽和交通狀況下的城市道路交叉口進(jìn)行分級管理，需解決城市道路交叉口的重要性排序問題，綜合考慮全路網(wǎng)中各交叉口之間的靜態(tài)結(jié)構(gòu)連接關(guān)系和動態(tài)流量影響，在改進(jìn)PageRank算法的基礎(chǔ)上，提出了能夠反應(yīng)全路網(wǎng)動態(tài)變化的交叉口繁忙程度指標(biāo)，并將該指標(biāo)用于路網(wǎng)重要交叉口排序篩選來分析交叉口的狀態(tài).研究結(jié)果表明：排序越靠前的交叉口越繁忙也越重要，交叉口繁忙程度指標(biāo)綜合考慮了全路網(wǎng)交叉口狀況，彌補(bǔ)了以飽和度為評價指標(biāo)只能片面衡量單個孤立交叉口狀態(tài)的不足，更準(zhǔn)確地反映了飽和交通狀況下交叉口之間的相互影響；本文方法排序結(jié)果與飽和度評價指標(biāo)排序結(jié)果相比，40%交叉口的排序升降幅度在3位以內(nèi)，30%交叉口的排序平均下降了7位，其余30%交叉口的排序平均上升了8位.該研究結(jié)果為飽和交通狀況下交叉口的合理分級提供了量化手段，有助于及時發(fā)現(xiàn)急需管控的交叉口.

交叉口；連接關(guān)系；PageRank；排序

路網(wǎng)中的交叉口具有兩種屬性.一種屬性是其構(gòu)成路網(wǎng)物理結(jié)構(gòu)的靜態(tài)拓?fù)涮匦?；另一種屬性是其輸送交通流能力的動態(tài)時變特性.拓?fù)涮匦匀Q于路網(wǎng)設(shè)計階段，屬于先天特性.時變特性則既與拓?fù)涮匦杂嘘P(guān)，更受路網(wǎng)交通運(yùn)行狀態(tài)的影響，所以該特性已成為交通管控中的重要因素.

當(dāng)路網(wǎng)交通流量較低、各相鄰交叉口之間的相互影響較弱時，通常采用交叉口飽和度或通行能力等單一指標(biāo)評價各交叉口的當(dāng)前狀態(tài)［1-3］，據(jù)此篩選出需要重點(diǎn)管控的關(guān)鍵交叉口.對交叉口排序的主要依據(jù)是飽和度量化指標(biāo)，僅孤立地觀察各個飽和度較高的交叉口.然而，當(dāng)路網(wǎng)交通運(yùn)行處于飽和狀態(tài)時，各交叉口的動態(tài)特性受到與其具有連通關(guān)系的其他交叉口交通流變化的影響，僅孤立地觀察飽和度高的交叉口難以發(fā)現(xiàn)問題所在.因此，在飽和狀態(tài)下，從路網(wǎng)角度出發(fā)，充分考慮交叉口之間的相互影響關(guān)系，篩選出對路網(wǎng)運(yùn)行效率有重要影響的關(guān)鍵交叉口，并對這些關(guān)鍵交叉口統(tǒng)一采取管控措施具有重要意義.

文獻(xiàn)［4］提供了一些指標(biāo)對路網(wǎng)中的交叉口進(jìn)行量化排序，比如交叉口飽和度、通行能力、平均延誤時間等.但這些評價指標(biāo)只能孤立地反映交叉口本身的動態(tài)特性，難以體現(xiàn)出每個交叉口在靜態(tài)路網(wǎng)中固有的結(jié)構(gòu)特性，更不能體現(xiàn)出路網(wǎng)資源緊張情況下各交叉口之間較強(qiáng)的關(guān)聯(lián)和相互影響特性.而這些因素才是揭示和衡量交叉口在路網(wǎng)中重要性的關(guān)鍵依據(jù).

為了能夠合理地對路網(wǎng)中的交叉口進(jìn)行重要性分析，篩選出關(guān)鍵交叉口，為制定交通管控措施提供科學(xué)依據(jù)，本文借鑒PageRank網(wǎng)頁排序算法，在綜合考慮交叉口之間的靜態(tài)連接關(guān)系和動態(tài)流量影響關(guān)系基礎(chǔ)上，提出一種路網(wǎng)重要交叉口篩選方法，并通過實例對提出的方法進(jìn)行分析驗證.

1 PageRank算法

PageRank算法是Google的兩位創(chuàng)始人Sergey Brin和Larry Page建立的一種搜索引擎算法，該算法將網(wǎng)頁排序與網(wǎng)頁的一些相關(guān)因素相聯(lián)系［5］. PageRank算法的主要思想是，首先，如果一個網(wǎng)頁被很多其他網(wǎng)頁所鏈接，說明它受到普遍的承認(rèn)和信賴，那么它的排序就高；其次，它借鑒了傳統(tǒng)引文分析思想，當(dāng)網(wǎng)頁A有一個鏈接指向網(wǎng)頁B，就認(rèn)為B獲得了A對它貢獻(xiàn)的分值，該值取決于A本身的重要程度，即網(wǎng)頁A的重要性越大，網(wǎng)頁B獲得的貢獻(xiàn)值就越高［6-7］，計算方法見式（1），

式中：DPR（P）為網(wǎng)頁的PageRank值；

d為阻尼因子，取值范圍為0＜d＜1，存在阻尼因子是因為并不是所有用戶都會順著網(wǎng)頁的超鏈接瀏覽，一般取d=0.85；

T1，T2，…，Tn為指向網(wǎng)頁P(yáng)的網(wǎng)頁；

DPR（Ti）為指向網(wǎng)頁P(yáng)的網(wǎng)頁Ti具有的PageRank值；

NTi為網(wǎng)頁Ti具有的導(dǎo)出鏈接數(shù).

2 路網(wǎng)重要交叉口篩選方法

2.1 改進(jìn)PageRank算法的交叉口篩選方法分析

根據(jù)PageRank算法，在對路網(wǎng)交叉口進(jìn)行分析時，本文將交叉口各進(jìn)口道流量作為研究參量，考慮交叉口之間的相互連接及影響關(guān)系，主要指各交叉口各進(jìn)口道的交通流量轉(zhuǎn)向比.

以圖1描述的路網(wǎng)為例，分析路網(wǎng)重要交叉口篩選方法的實現(xiàn)過程.圖1共包含4個交叉口，交叉口之間存在連通關(guān)系，其相互影響主要通過各出入口的流量反映.以交叉口1為例，出口1是交叉口1的出口，同時又是交叉口2的入口.出口1的流量與該交叉口其他方向的入口1、2、3的流量密切相關(guān)（在此暫不考慮掉頭方向）.

圖1 路網(wǎng)示意圖Fig.1 Simplified road network

由圖1中各入口的轉(zhuǎn)向關(guān)系，出口1的流量為

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

RL、RS、RR分別為對應(yīng)入口的左轉(zhuǎn)流量比、直行流量比、右轉(zhuǎn)流量比.

用式（2）計算出每個交叉口的出口流量.根據(jù)交叉口之間的連接及影響關(guān)系，各出口流量對其他交叉口入口流量有所貢獻(xiàn).可以按照PageRank算法的計算過程，考慮交叉口之間的相互連接以及影響關(guān)系，以流量作為參數(shù)計算各交叉口的I值.

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

k（Zi）為交叉口Z第i入口道對應(yīng)的轉(zhuǎn)向比；

I（Zi）為交叉口Z第i入口道對應(yīng)的排名值；

n為與相鄰交叉口Y第j入口道流量相關(guān)聯(lián)的入口道數(shù)目；

CZi為各個入口道Zi的通行能力；

f為流量修正因子，因為駛出上一個交叉口的車輛未必全部駛?cè)胂乱粋€交叉口.

考慮交叉口有多個入口道，且各入口道受通行能力的限制，不能直接地將排名值Ii作為篩選依據(jù)，本文將該指標(biāo)修改為

式中：I（Z）為將交叉口Z各個進(jìn)口道的Ii最大值作為交叉口繁忙程度的排名值.

繁忙程度類似網(wǎng)頁中的PageRank值，某交叉口的繁忙程度是根據(jù)與其關(guān)聯(lián)的其他交叉口繁忙程度綜合計算而獲得的.與傳統(tǒng)的僅針對單個交叉口進(jìn)行分析的飽和度或服務(wù)水平的計算方式不同，本文是在綜合分析整個路網(wǎng)后計算每個交叉口的繁忙程度.

2.2 路網(wǎng)中重要交叉口篩選方法

本文參考PageRank算法，同時考慮流量分配和轉(zhuǎn)向問題，獲得交叉口的指標(biāo)數(shù)據(jù)后，依據(jù)交叉口繁忙程度對交叉口的重要性進(jìn)行排名分析，進(jìn)而篩選出重要的交叉口.該方法步驟如下：

（1）獲得交叉口各入口道流量及轉(zhuǎn)向比

通過檢測器獲得交叉口各入口道的交通流量，用統(tǒng)計方法獲得各入口方向的轉(zhuǎn)向比.通過在交叉口出入口道安置交通檢測器，根據(jù)在一段時間內(nèi)檢測器獲得的數(shù)據(jù)統(tǒng)計入口及出口的流量，便可獲知各方向的轉(zhuǎn)向比.

（2）計算相鄰交叉口各入口道的Ii值

在獲得交叉口各入口道流量及轉(zhuǎn)向比后，可根據(jù)路網(wǎng)中交叉口的相互連接關(guān)系，計算每個相鄰交叉口各入口道的Ii值.

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

在獲得各交叉口入口道的Ii值后，按照路網(wǎng)中交叉口出口道與入口道的關(guān)系，更新入口道Ii值信息.

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

在計算交叉口入口道Ii值時，需要進(jìn)行迭代運(yùn)算，達(dá)到一定的次數(shù)時，Ii值基本維持不變.

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

將交叉口各入口道繁忙程度最大值作為交叉口繁忙程度值，從大到小對路網(wǎng)中各交叉口進(jìn)行排序，排名越靠前，其重要程度越高.

交叉口繁忙程度越高，證明該交叉口擁堵對路網(wǎng)交通運(yùn)行效率的影響越大.

3 路網(wǎng)的存儲

由上述分析可知，在對路網(wǎng)交叉口進(jìn)行篩選時需要獲取交叉口之間的連接關(guān)系以及各個交叉口的屬性（交叉口的通行能力、流量、轉(zhuǎn)向比等）.因此，需要設(shè)計路網(wǎng)的存儲結(jié)構(gòu)來保存路網(wǎng)的連接關(guān)系以及各交叉口的屬性.

在圖論中，圖的存儲方式有鄰接圖、鄰接表和前向關(guān)聯(lián)邊3種基本結(jié)構(gòu).由于道路網(wǎng)絡(luò)屬于大型稀疏網(wǎng)絡(luò)，并且具有節(jié)點(diǎn)權(quán)重等屬性，本文選擇前向關(guān)聯(lián)邊結(jié)構(gòu)存儲路網(wǎng)及節(jié)點(diǎn)權(quán)重［8］.

前向關(guān)聯(lián)邊結(jié)構(gòu)最重要的思想是，將同一個節(jié)點(diǎn)發(fā)出的所有弧放在同一個數(shù)組中，并用長度為n（n為節(jié)點(diǎn)個數(shù)）的指針數(shù)組Pointer表示，數(shù)組中每個指針對應(yīng)一個節(jié)點(diǎn)，指針指向該節(jié)點(diǎn)所發(fā)出的第1條?。挥瞄L度為m（m為弧的條數(shù)）的數(shù)組PointNode存儲指針數(shù)組中指針?biāo)赶虻墓?jié)點(diǎn)；用長度為n的數(shù)組Nature存放節(jié)點(diǎn)對應(yīng)的飽和度和通行能力［9］.圖2和圖3為前向關(guān)聯(lián)結(jié)構(gòu).

圖2 路網(wǎng)關(guān)聯(lián)關(guān)系示意圖Fig.2 Correlations of intersections

在進(jìn)行路網(wǎng)存儲時，首先應(yīng)標(biāo)明每個交叉口的序號，另外還要從序號小的交叉口開始標(biāo)明每個交叉口的前向邊序號（圖2）.將交叉口按序號從小到大存儲到Node數(shù)組；Nature存儲相應(yīng)的交叉口屬性.以圖1中交叉口1為例說明路網(wǎng)存儲的用法.交叉口1與交叉口2、3、4相連，所以PointNode數(shù)組包括交叉口2、3、4，PointNode最先出現(xiàn)的是交叉口2，交叉口1、2之間的前向邊序號為1，所以Pointer數(shù)組中數(shù)為1.其余交叉口以此類推，可得到如圖3所示的前向關(guān)聯(lián)邊結(jié)構(gòu).

圖3 前向關(guān)聯(lián)邊結(jié)構(gòu)Fig.3 Forward star structure

圖3中用長度為6的數(shù)組Pointer存儲與節(jié)點(diǎn)相關(guān)的數(shù)據(jù)；另外用一個長度為15的數(shù)組PointNode存儲與弧相關(guān)的數(shù)據(jù)；長度為6的Nature數(shù)組存儲節(jié)點(diǎn)的屬性.這樣僅用了2n+m的存儲量便可存儲了整個路網(wǎng)以及各節(jié)點(diǎn)的屬性，大大節(jié)省了存儲空間.

4 實驗分析

4.1 實驗方案設(shè)計

為了對改進(jìn)PageRank算法的路網(wǎng)交叉口篩選方法進(jìn)行測試，本文設(shè)計的實驗方案主要體現(xiàn)多交叉口連接關(guān)系對交叉口重要性程度的影響.設(shè)計方案考慮如下因素：首先，對多交叉口進(jìn)行重要性排序，然后考慮各交叉口之間的相互連接及影響關(guān)系，我國城市道路按照功能分為快速路、主干路、次干路及支路［10］，根據(jù)道路類別的不同，各級道路之間的連接關(guān)系也不盡相同.因此，設(shè)計實驗路網(wǎng)（如圖4所示）包含20個交叉口.

圖4中交叉口各進(jìn)口（東、西、南、北）的交通流量、各進(jìn)口各車道（左轉(zhuǎn)、直行及右轉(zhuǎn)）的轉(zhuǎn)向比見表1和表2.

4.2 實驗數(shù)據(jù)分析

為分析本文提出方法的合理性，分別采用傳統(tǒng)的計算交叉口飽和度值的方法與本文基于改進(jìn)PageRank算法計算交叉口繁忙程度的方法，對路網(wǎng)中的交叉口進(jìn)行排序篩選，排序結(jié)果及其對比見表3、表4和圖5.

由表3、表4和圖5可以看出，兩種篩選方法的排序結(jié)果差別明顯.按照飽和度值進(jìn)行排序，突出了各交叉口所轄范圍的飽和程度，其意義是能夠指導(dǎo)管控決策，逐個針對點(diǎn)（交叉口）進(jìn)行處理和改善，但難以從全路網(wǎng)角度做出系統(tǒng)化的決策.因為，某個點(diǎn)（交叉口）飽和度高可能是由于與其關(guān)聯(lián)的其他點(diǎn)（交叉口）飽和度低引起的，但用現(xiàn)有方法難以發(fā)現(xiàn)這種隱藏的原因.比如交叉口A、B相連，前者飽和度為0.6，后者飽和度為0.5，交叉口A車流量流向B，因而交叉口A的飽和度會影響交叉口B，所以最終判定交叉口A、B哪個更重要將比較困難.

圖4 實驗路網(wǎng)Fig.4 Experimental road network

表1 交叉口各進(jìn)口交通流量Tab.1 Traffic volumes of intersection inlets pcu/h

以交叉口1為例，其飽和度為0.36，在飽和度排序方法中排序為20.然而，因其與交叉口2、5相連，而這兩個交叉口飽和度較高，因此車流量勢必會影響交叉口1，造成交叉口1車流量增加.按照本文的方法，計算出其繁忙程度為0.69，排名為第11.

表2 交叉口各進(jìn)口車道轉(zhuǎn)向比Tab.2 Turning rates of intersection inlets

表3 飽和度排序結(jié)果Tab.3 Ranking results in saturation

本文方法與傳統(tǒng)方法的重大區(qū)別在于，本文改進(jìn)PageRank算法的篩選方法是從整個路網(wǎng)角度出發(fā)計算出每個交叉口的繁忙程度值，該值隱含了某交叉口對其他相關(guān)聯(lián)交叉口的影響以及在路網(wǎng)中的重要地位.即本文提出的方法不僅能發(fā)現(xiàn)顯性的問題交叉口，更能挖掘出潛在的問題交叉口，進(jìn)而能夠指導(dǎo)交通管控決策從全局出發(fā)，將顯性和隱性的問題交叉口系統(tǒng)地進(jìn)行處理.能夠及時發(fā)現(xiàn)潛在的問題交叉口，是本文所提方法的重要價值所在.

表4 本文算法排序結(jié)果Tab.4 Ranking results by PageRank algorithm

傳統(tǒng)的依據(jù)飽和度排序方法，關(guān)注的是每個孤立的點(diǎn)（交叉口），發(fā)現(xiàn)每個孤立點(diǎn)的擁堵問題.該方法的這種局限性導(dǎo)致交通管控策略的制定也基本上是逐點(diǎn)解決問題，因為忽略了潛在問題點(diǎn)，往往導(dǎo)致?lián)矶曼c(diǎn)轉(zhuǎn)移.以改進(jìn)PageRank算法進(jìn)行排序的方法，關(guān)注的是整個路網(wǎng)，在計算過程中考慮了所有交叉口，在全局范圍內(nèi)發(fā)現(xiàn)整體中的問題點(diǎn)，更全面和系統(tǒng)地解決問題.

圖5 兩種方法比較Fig.5 Comparison of ranking results between two algorithms

綜上所述，本文提出的基于改進(jìn)PageRank算法的交叉口篩選方法，突破了傳統(tǒng)方法孤立地評價交叉口的局限性，能夠從全路網(wǎng)出發(fā)，對各交叉口在路網(wǎng)中的重要程度進(jìn)行排序；此外，本文方法還能夠揭示具有邏輯連通關(guān)系的交叉口之間的相互影響程度，排序結(jié)果能夠?qū)还懿块T改變及制定交通管控決策提供新的思路和重要的參考依據(jù).

5 結(jié)束語

借鑒PageRank網(wǎng)頁排序算法，綜合考慮城市路網(wǎng)的靜態(tài)連接關(guān)系和動態(tài)交通流量對各交叉口的影響，對PageRank算法進(jìn)行了改進(jìn)，提出了從全路網(wǎng)角度出發(fā)計算各交叉口繁忙程度指標(biāo)，對城市路網(wǎng)交叉口進(jìn)行重要性篩選的計算方法；其計算結(jié)果一方面能夠體現(xiàn)交叉口在路網(wǎng)中的重要程度，另一方面也揭示了該交叉口對與其具有邏輯連通關(guān)系的其他交叉口的影響，既能發(fā)現(xiàn)顯性的問題交叉口，也能夠發(fā)現(xiàn)隱性的問題交叉口.

在飽和交通時代，道路交通系統(tǒng)時空資源日趨匱乏，全面系統(tǒng)地評價和篩選出路網(wǎng)中的重要交叉口并對其實施科學(xué)管控，使有限的時空資源得到最大化的利用是當(dāng)前及未來城市交通管控所面臨的棘手問題，本文對解決該問題提供了一種可操作的理論方法.

［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īng)，等.信號控制交叉口通行能力計算方法研究綜述［J］.中國公路學(xué)報，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］ 劉娟，孫建平，劉夢涵，等.微觀層次城市道路交通擁堵評價指標(biāo)的研究［C］∥2007第三屆中國智能交通年會論文集.南京：東南大學(xué)出版社，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］.計算機(jī)技術(shù)與發(fā)展，2006，16（7）：82-84.

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

［8］ 姜桂艷，鄭祖舵，于妍霞.交通誘導(dǎo)系統(tǒng)中道路網(wǎng)絡(luò)的表達(dá)與存儲方法［J］.吉林大學(xué)學(xué)報，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］ 徐吉謙，陳學(xué)武.交通工程總論［M］.北京：人民交通出版社，2008：120-124.

基于改進(jìn)PageRank算法的路網(wǎng)重要交叉口篩選方法

郭海鋒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

浙江省自然科學(xué)基金資助項目（LY14F030012）；中國博士后基金資助項目（2012M511387）

郭海鋒（1977—），男，博士，副教授，研究方向為智能交通系統(tǒng)、交通信息處理，E-mail：guohf@zjut.edu.cn

鄭雅羽（1978—），男，博士，副研究員，研究方向為智能輔助駕駛、車聯(lián)網(wǎng)系統(tǒng)，E-mail：yayuzheng@zjut.edu.cn

郭海鋒，張昌世，穆元杰，等.基于改進(jìn)PageRank算法的路網(wǎng)重要交叉口篩選方法［J］.西南交通大學(xué)學(xué)報，2016，51（5）：925-930.

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