基于對偶拓撲結構的路網路段重要性評估方法

張喜平，李永樹，劉 剛

（1．西南交通大學 地球科學與環境工程學院，四川 成都610031；2．重慶郵電大學 軟件學院，重慶400065）

現實的復雜路網是非同質的拓撲結構［1］，這一特征決定復雜路網的路段的重要性是各不相同的。對路網中路段節點的重要性評估不僅是研究復雜路網結構與功能的基礎性工作，也是交通規劃與控制活動的基礎［2］。快速、準確地發掘路網中的重要路段不僅能在路網的規劃設計中避免因為這些節點的癱瘓給交通造成大面積的擁堵，還能為級聯動力學等路網結構之上的功能性研究提供準確的數據支撐。因此，對復雜路網的路段節點重要性的研究已經成為復雜路網研究的重要課題。

現有的復雜路網的路段重要性的研究主要有：Michael［3］等提出一種基于路段選擇概率的路段重要性評估方法，該方法在考慮出行者對出行時間的感知誤差的前提下，利用算法求出各個路段的選擇概率，選擇概率越大，路段越重要。這是一種從路段所承擔的交通量的角度來評估路段重要性的方法，這種方法在計算路段的選擇概率需要路段的實際交通流量，這種數據難以收集。王曉麗等 在其綜述性的文獻中提到了瑞典的學者Erik Jenal us等人提出的一種路段重要性評估算法，該方法是在路網中，假設路段上已發生使路段降級甚至失效的事件，對路段失效后的后果進行計算，從而根據其確定路段的重要性。這種評估方法把路網的“破壞性等價于重要性”。侯立文等［5］提出一種基于路段可靠性評價的方法用于確定路網中路段的相對重要性評估，這是一種與文獻［4］中提到的方法相反的方法。劉思峰等［6－8］利用網絡的連通性來反映路網中路段節點的重要性，這是利用圖論的方法對路段重要性進行評估。在一定程度上，路段節點自身的度、介數等屬性反映了路段的重要程度，但這并不能準確地刻畫路段在整個路網中的重要度，路段的重要性還跟相鄰路段及其他較遠路段的重要性密切相關。因此，認為路段的重要度是路網上所有路段共同作用、貢獻的結果。

基于這種考慮，引入m階鄰居節點的概念，提出一種基于對偶拓撲的復雜路網路段重要度評價方法，建立具有普適性的評價模型。該方法考慮了路段自身屬性及m階鄰居節點的屬性對路段重要度的貢獻，以度、介數為考察參數，建立同時顧及度值和介數值的評估模型，與傳統的度值法、介數法等評估方法相比，本文方法能更有效地評估復雜路網路段的重要度并確定路網中的關鍵節點與關鍵路徑。

1 復雜路網路段重要度評估方法

1．1 理論基礎

定義1 路網對偶圖［9－11］。建立基于 GIS路網拓撲的對偶圖，對偶拓撲方法是將道路按道路名稱映射為節點，交叉口映射為邊。

定義2 節點度值是指節點直接相連邊的數量，記為D。目前普遍認為節點的度值可以直接反映節點的重要程度。節點的度值越高，則說明該節點越重要。

定義3 m階鄰居節點。對于復雜網絡G＝｛V， L ｝中任意節點i（i∈V），其1階鄰居節點為與節點i之間距離為1的節點，該類節點構成的集合稱作節點i的1階鄰居節點集，記為π（1）（i）；同理，則與節點i之間距離為2的節點為2階鄰居節點，其構成的集合稱作節點i的2階鄰居節點集，記為π（2）（i）；如此類推，則與節點i之間距離為m 的節點稱為m階鄰居節點，其構成的集合稱作節點i的m 階鄰居節點集，記為π（m）（i）。

1．2 路段節點重要度評估方法

在現實生活中對目標對象重要性進行評估時，通常會綜合考慮多方面因素的影響。對于網絡節點而言，其重要性并不是完全取決于節點的度、介數或其他特性，需要同時顧及這些因素，才能對節點的重要性做出較為準確的評估。這里，假設針對每個節點選取n個評價指標，用δi，j表示節點i的第j個指標值。由此，可以定義節點i的重要度評價模型［12］：

式中：Ii為節點i的重要度；A為評估系數矩陣或重要度貢獻矩陣，用于表示節點自身及各階鄰居節點對節點i重要性的貢獻程度，且認為同階鄰居節點對節點i具有相等的貢獻程度，即其評估系數相等；Ei為節點i的評估指標矩陣，包含節點i及各階鄰居節點的指標值；W 為指標權重矩陣，用于表示節點i的重要性對各類指標的依賴程度，這里將n個評價指標所占權重分別記為ω1，ω2，…，ωn。對于多因子情況，保留單因子評價函數中同階鄰居節點對節點i重要度貢獻的計算方法，即

由于不同指標的取值范圍可能相差很大，例如同一節點的度為幾十，而其介數可能達到幾千。各指標的物理意義和計量單位不一定相同，導致數據的量綱和數量級可能不同。所以，需要對評估指標矩陣Ei做歸一化處理。由式（1）可知，其中每列元素對應一個指標，總共有n個指標。對Ei中的每一個指標值采用式（4）。

式中：δ′（k）i，j為歸一化后的指標值，由δ′（k）i，j可以計算出歸一化評估 指 標 矩 陣 E′i。令 A ＝ ［α，γ，γ2，…，γm］，W ＝ ［ω1，ω2，ω3，…，ωn］T，由此網絡中任意節點i的重要度Ii＝A·E′i·W ，即

式中，指標權重矩陣n個指標集合的取值為1，并且每一個ωj大于等于0，α和γ為兩個參數，其用于調節節點重要度評估對節點自身特性及m階鄰居節點的依賴程度。m為鄰居節點的深度。

1．3 算法流程

考慮到路段節點本身及其m階鄰居節點在各類指標約束下對節點的重要度貢獻，可以得到較為精確的評價結果。路段節點在對偶拓撲中的度與介數等指標可以反映路段節點的重要程度。已知GIS復雜路網，所考察鄰居節點深度m，根據上述多因素的評估模型，給出評估節點重要度的具體算法：

1）從GIS路網結構圖映射出對偶拓撲結構：G＝｛V ，L｝ 。V是路網的頂點集合，也是路網的路段集合。L是路網邊的集合，也是路網的交叉路口的集合；

2）根據對偶拓撲結構，提取任意路段節點i＝1，2，…，m 階鄰居節點集：π（1）（i），π（2）（i），…，π（m）（i）；

3）計算路段節點i的各階鄰居節點集的每個指標值：

4）針對Ei中每類指標做歸一化處理，計算歸一化后的評估指標矩陣E′i；

5）根據式（5）計算每個路段節點的重要度，輸出Ii。

得到每個路段節點的重要度后，將所有路段節點按照重要度值從大到小進行排序。這樣，重要度取值越大的節點就越為重要。根據節點重要度的降序排列結果，可以確定路網中最為重要的路段節點或關鍵路段節點集。

2 試驗與仿真

為了驗證本文的評估方法，選用成都市道路網的GIS圖作為真實網絡的驗證。根據文獻［11］的方法，首先將成都市路網GIS圖轉換成對偶模型，然后利用式（1）的評估模型選取度和介數兩大計算因素計算對偶模型中路段節點的重要度，將重要度取值最大的部分節點作為關鍵道路的候選節點，最后對選取的節點進行連通性的檢查從而生成一條關鍵道路。根據上述方法，在成都市路網中存在的1 484個路段提取10條關鍵道路。具體的提取結果如圖1所示。

圖1 成都市路網十條關鍵道路

在上述實驗條件下，為了得到穩定的仿真結果，m的取值與路網的平均路徑長度有著一定關系。當m取值小于路網平均路徑長度時評估結果是不穩定的，而m取值大于路網平均路徑長度時評估結果趨于穩定。圖2是對成都市路網1 484個路段用本文的評估方法得到的路段重要性的值及度與介數的關系，其中m＝4，m取值為大于路網的平均路徑長度，因為這種情況下評估結果趨于穩定。從這個關系圖中可以看出，整體的趨勢是度大的節點的重要性較大，但是這種線性關系也不是處處成立的，圖2中有大量度相同的節點，這些度相同的節點是無法用基于度的評估方法得出精確的評估結果的，另外特別是在度較大的區域還會出現隨著度的增加重要度降低的情況。

表1是抽取度為1的所有的路段，從表中可知這18個路段采用基于度的評估方法無法得出精確結果，而采用本文的方法，表格的最后一列能得出精確的評估結果。

圖2 道路重要度與度的關系

表1 道路重要度與度的關系

圖3是對1 484個路段用本文的評估方法得到的路段重要性的值與介數的關系。從這個關系圖中可以看出，整體的趨勢是介數較大的節點的重要性較大，但是這種線性關系也不是處處成立的，圖3中也有大量的介數相同的節點，這些節點是無法用基于介數的評估方法得出精確的評估結果的，另外特別是在介數較大的區域還會出現隨著介數的增加重要度降低的情況，如圖3圖形接近頂端的部分。

表2是抽取了介數為1的所有的路段，從表中可知這36個路段采用基于介數的評估方法無法得出精確結果，而采用本文的方法，表格的最后一列能得出精確的評估結果。

圖3 道路重要度與介數的關系

表2 道路重要度與度的關系

119 1 0．343 490 620

為了驗證本文的評估算法的精確性，抽取圖1中的一條關鍵道路來驗證本文的算法。這條關鍵道路的路段節點的序號為：1 417、1 429、1 430、1 435、1 455、1 448、1 458、1 466、1 460、1 462、1 436、1 439、1 465、1 437、1 432、1 416、1 424、1 441、62、1 421。表3是這一關鍵路徑在基于度的方法基于介數的方法與本文的評估方法的結果的對比。表中第五列數據是基于度的評估方法的排序結果，度越大的節點與周圍節點的連接分枝越多，那么這種節點就越重要，但是存在著像1 432與1 416這樣的度相等的路段無法得出評估結果。表中第六列數據是基于介數的評估結果，介數反應了路網中的所有最短路徑經過該路段的數量，介數越大的路段節點所承載的交通流量也就越大，因此這一評估方法反應了路段的承載能力，關鍵路徑中雖然1 439號路段與1 430號路段相比有著較大的度，但從介數的計算結果看1 430的介數為128 536而1 439的介數為73 865，這表明在實際的路網中1 430所承載的流量要比1 439大得多，因此從路網的實際流量角度看1 430號路段更為重要。表中最后一列數據為本文的評估方法的結果，這一評估結果是同時考慮了度和介數兩大因素并且把路段的重要度看成與其m階鄰接節點有關，在該方法的評估結果中1 432與1 416這樣的度相等的路段節點在本文方法中能夠進一步取得更精確的評估結果。在基于介數的評估結果中1 448與1 435號路段相比前者的介數大于后者，但是1 435號路段在本文的評估方法中與周圍m階節點的影響更大，因此在本文的評估結果中1 435號路段的重要性更高。

表3 關鍵路徑上路段重要性評估結果

3 結 論

路段重要性評估方法是路網規劃、設計與路網可靠性研究中的關鍵技術。目前的路段重要性評估中缺乏考慮全局性的評估方法。本文提出在復雜路網的對偶拓撲結構的基礎上，研究基于m階鄰居節點的路段節點重要性的多因素評估模型。在試驗中選用成都市GIS路網在其對偶拓撲結構上驗證基于度與介數的兩大因素評估模型。實驗結果表明：本文所提出的研究方法與介數法和基于度的方法相比具有較高的評估準確性。該研究進一步揭示路網中路段節點的相互影響和依賴的作用機制，為研究復雜路網的路段重要性提供一種新的研究方法。

［1］ 赫南，李德毅，淦文燕，等．復雜網絡中重要性節點發掘綜述［J］．計算機科學，2007（12）：1－5．

［2］ 熊金華，曹亞妮，程越．基于統計分析方法的地理要素顯示重要性確定研究［J］．測繪工 程，2012，21（3）：26－30．

［3］ TAYLOR M A P．Applying interactive color graphics in traffic planning［J］．Co mputers ＆ Graphics，2007，11（3）：241－248．

［4］ 王曉麗，溫冬海，張利分．交通網絡重要路段確定方法研究［J］．山西科技，2007（1）：91－95．

［5］ 侯立文，蔣馥．城市道路網中路段相對重要性研究［J］．系統工程理論方法與應用，2004，13（5）：425－428．

［6］ 劉思峰，萬壽慶，陸志鵬，等．復雜交通網絡中救援點與事故點間的路段重要性評價模型研究［J］．中國管理科學，2009，17（1）：119－124．

［7］ 王少華，鐘耳順，張小虎，等．北京交通網絡拓撲結構及可達性格局歷史文化研究［J］．測繪與空間地理信息，2014，37（1）：9－12．

［8］ 周蘭蘭，康建榮．拓撲多邊形自相交判斷及糾正方法［J］．測繪與空間地理信息，2014，37（10）：33－35．

［9］ 李玉蘭，李耀堂．城市道路網容量的對偶圖算法［J］．云南大學學報：自然科學版，2006（4）：293－297．

［10］徐英睿，陸鋒，張洪巖．基于對偶圖的城市交叉口延誤分析［J］．公路，2012（9）：149－153．

［11］閆文彩，張玉林，趙茂先，等．基于復雜網絡的城市路網可靠性分析［J］．山東科學，2011（2）：65－70．

［12］劉剛，李永樹，楊駿，等．對偶圖節點重要度的道路網自動選取方法［J］．測繪學報，2014，43（1）：97－104．