基于對偶拓?fù)浣Y(jié)構(gòu)的路網(wǎng)路段重要性評估方法

張喜平，李永樹，劉 剛

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

現(xiàn)實的復(fù)雜路網(wǎng)是非同質(zhì)的拓?fù)浣Y(jié)構(gòu)［1］，這一特征決定復(fù)雜路網(wǎng)的路段的重要性是各不相同的。對路網(wǎng)中路段節(jié)點的重要性評估不僅是研究復(fù)雜路網(wǎng)結(jié)構(gòu)與功能的基礎(chǔ)性工作，也是交通規(guī)劃與控制活動的基礎(chǔ)［2］?？焖?、準(zhǔn)確地發(fā)掘路網(wǎng)中的重要路段不僅能在路網(wǎng)的規(guī)劃設(shè)計中避免因為這些節(jié)點的癱瘓給交通造成大面積的擁堵，還能為級聯(lián)動力學(xué)等路網(wǎng)結(jié)構(gòu)之上的功能性研究提供準(zhǔn)確的數(shù)據(jù)支撐。因此，對復(fù)雜路網(wǎng)的路段節(jié)點重要性的研究已經(jīng)成為復(fù)雜路網(wǎng)研究的重要課題。

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

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

1 復(fù)雜路網(wǎng)路段重要度評估方法

1．1 理論基礎(chǔ)

定義1 路網(wǎng)對偶圖［9－11］。建立基于 GIS路網(wǎng)拓?fù)涞膶ε紙D，對偶拓?fù)浞椒ㄊ菍⒌缆钒吹缆访Q映射為節(jié)點，交叉口映射為邊。

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

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

1．2 路段節(jié)點重要度評估方法

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

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

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

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

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

1．3 算法流程

考慮到路段節(jié)點本身及其m階鄰居節(jié)點在各類指標(biāo)約束下對節(jié)點的重要度貢獻，可以得到較為精確的評價結(jié)果。路段節(jié)點在對偶拓?fù)渲械亩扰c介數(shù)等指標(biāo)可以反映路段節(jié)點的重要程度。已知GIS復(fù)雜路網(wǎng)，所考察鄰居節(jié)點深度m，根據(jù)上述多因素的評估模型，給出評估節(jié)點重要度的具體算法：

1）從GIS路網(wǎng)結(jié)構(gòu)圖映射出對偶拓?fù)浣Y(jié)構(gòu)：G＝｛V ，L｝ 。V是路網(wǎng)的頂點集合，也是路網(wǎng)的路段集合。L是路網(wǎng)邊的集合，也是路網(wǎng)的交叉路口的集合；

2）根據(jù)對偶拓?fù)浣Y(jié)構(gòu)，提取任意路段節(jié)點i＝1，2，…，m 階鄰居節(jié)點集：π（1）（i），π（2）（i），…，π（m）（i）；

3）計算路段節(jié)點i的各階鄰居節(jié)點集的每個指標(biāo)值：

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

5）根據(jù)式（5）計算每個路段節(jié)點的重要度，輸出Ii。

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

2 試驗與仿真

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

圖1 成都市路網(wǎng)十條關(guān)鍵道路

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

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

圖2 道路重要度與度的關(guān)系

表1 道路重要度與度的關(guān)系

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

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

圖3 道路重要度與介數(shù)的關(guān)系

表2 道路重要度與度的關(guān)系

119 1 0．343 490 620

為了驗證本文的評估算法的精確性，抽取圖1中的一條關(guān)鍵道路來驗證本文的算法。這條關(guān)鍵道路的路段節(jié)點的序號為：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是這一關(guān)鍵路徑在基于度的方法基于介數(shù)的方法與本文的評估方法的結(jié)果的對比。表中第五列數(shù)據(jù)是基于度的評估方法的排序結(jié)果，度越大的節(jié)點與周圍節(jié)點的連接分枝越多，那么這種節(jié)點就越重要，但是存在著像1 432與1 416這樣的度相等的路段無法得出評估結(jié)果。表中第六列數(shù)據(jù)是基于介數(shù)的評估結(jié)果，介數(shù)反應(yīng)了路網(wǎng)中的所有最短路徑經(jīng)過該路段的數(shù)量，介數(shù)越大的路段節(jié)點所承載的交通流量也就越大，因此這一評估方法反應(yīng)了路段的承載能力，關(guān)鍵路徑中雖然1 439號路段與1 430號路段相比有著較大的度，但從介數(shù)的計算結(jié)果看1 430的介數(shù)為128 536而1 439的介數(shù)為73 865，這表明在實際的路網(wǎng)中1 430所承載的流量要比1 439大得多，因此從路網(wǎng)的實際流量角度看1 430號路段更為重要。表中最后一列數(shù)據(jù)為本文的評估方法的結(jié)果，這一評估結(jié)果是同時考慮了度和介數(shù)兩大因素并且把路段的重要度看成與其m階鄰接節(jié)點有關(guān)，在該方法的評估結(jié)果中1 432與1 416這樣的度相等的路段節(jié)點在本文方法中能夠進一步取得更精確的評估結(jié)果。在基于介數(shù)的評估結(jié)果中1 448與1 435號路段相比前者的介數(shù)大于后者，但是1 435號路段在本文的評估方法中與周圍m階節(jié)點的影響更大，因此在本文的評估結(jié)果中1 435號路段的重要性更高。

表3 關(guān)鍵路徑上路段重要性評估結(jié)果

3 結(jié) 論

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

［1］ 赫南，李德毅，淦文燕，等．復(fù)雜網(wǎng)絡(luò)中重要性節(jié)點發(fā)掘綜述［J］．計算機科學(xué)，2007（12）：1－5．

［2］ 熊金華，曹亞妮，程越．基于統(tǒng)計分析方法的地理要素顯示重要性確定研究［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］ 王曉麗，溫冬海，張利分．交通網(wǎng)絡(luò)重要路段確定方法研究［J］．山西科技，2007（1）：91－95．

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

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

［7］ 王少華，鐘耳順，張小虎，等．北京交通網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)及可達性格局歷史文化研究［J］．測繪與空間地理信息，2014，37（1）：9－12．

［8］ 周蘭蘭，康建榮．拓?fù)涠噙呅巫韵嘟慌袛嗉凹m正方法［J］．測繪與空間地理信息，2014，37（10）：33－35．

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

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

［11］閆文彩，張玉林，趙茂先，等．基于復(fù)雜網(wǎng)絡(luò)的城市路網(wǎng)可靠性分析［J］．山東科學(xué)，2011（2）：65－70．

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