突發(fā)環(huán)境下城市道路網(wǎng)關(guān)鍵路段集識(shí)別

李彥瑾，羅 霞

(西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院，成都610031)

0 引言

自然災(zāi)害、交通事故等突發(fā)事件具有隨機(jī)性強(qiáng)、涉及面廣和負(fù)擴(kuò)散效應(yīng)顯著等特點(diǎn).當(dāng)城市道路網(wǎng)中單條或多條脆弱路段出現(xiàn)突發(fā)事件時(shí)，極易引發(fā)相關(guān)路段連鎖排隊(duì)，造成大面積的交通擁堵.這不僅阻礙了受困人群的疏散，而且延誤了救援人員的到達(dá)和應(yīng)急物資的輸送.因此，合理運(yùn)用路網(wǎng)脆弱性分析方法，識(shí)別突發(fā)環(huán)境下影響路網(wǎng)運(yùn)行的關(guān)鍵路段集合，對(duì)于道路交通防災(zāi)減災(zāi)規(guī)劃和災(zāi)后應(yīng)急救援資源調(diào)度等有重要的實(shí)踐意義.

關(guān)鍵路段的識(shí)別是路網(wǎng)脆弱性分析的基礎(chǔ)[1]，傳統(tǒng)研究思路為：先構(gòu)建關(guān)鍵路段識(shí)別指標(biāo)，運(yùn)用“遍歷法”輪流從路網(wǎng)中刪除某一路段，再依據(jù)識(shí)別指標(biāo)的變化情況來(lái)衡量該路段對(duì)整個(gè)路網(wǎng)的影響.沿用這一思路，Berdica[1]、D’Este[2]、Jenelius[3]、Sullivan[4]等分別采用路段飽和度、連通性、路段重要度和網(wǎng)絡(luò)魯棒性指數(shù)等識(shí)別關(guān)鍵路段.這類方法雖可直接比較不同拓?fù)浣Y(jié)構(gòu)的道路網(wǎng)絡(luò)，但對(duì)于大規(guī)模路網(wǎng)，其計(jì)算效率較低，誤判可能性較大[5-8]；對(duì)此，Wang[5]、Farahani[6]等采用對(duì)偶算法壓縮模型可行域；張璽[7]、李彥瑾[8]等運(yùn)用魯棒性分析減少對(duì)關(guān)鍵路段的誤判.

上述研究雖作出了積極地探索，但囿于均以單條路段為研究對(duì)象，不能理清多條路段同時(shí)失效時(shí)，路網(wǎng)與關(guān)鍵路段集之間的內(nèi)在聯(lián)系；另外，突發(fā)環(huán)境下的城市道路網(wǎng)一般擁有以下3個(gè)特征，也使得既有方法不能很好解決這類問(wèn)題：

(1)突發(fā)事故涉及面廣、傳播速度快，在短時(shí)內(nèi)可能造成路網(wǎng)中多條路段失效，失效路段構(gòu)成一個(gè)路段集合；

(2)突發(fā)環(huán)境下，路網(wǎng)中的正常路段一般無(wú)法迅速消解擁堵，其道路通行能力限制會(huì)對(duì)整個(gè)路網(wǎng)的交通流分布產(chǎn)生重要影響[8]；

(3)突發(fā)事件的應(yīng)急響應(yīng)具有緊迫性，需及時(shí)制定救援策略，避免對(duì)關(guān)鍵路段的誤判.

因此，為克服以上3個(gè)問(wèn)題可能帶來(lái)的不足，本文擬從路網(wǎng)特性分析入手，采用線性化手段，構(gòu)建一個(gè)涵蓋單條到多條路段失效的混合0-1規(guī)劃模型，再以分支定界法獲取可行解，并設(shè)計(jì)算例進(jìn)行驗(yàn)證.

1 城市路網(wǎng)特性分析

對(duì)城市道路網(wǎng)進(jìn)行拓?fù)浞治鰰r(shí)，一般采用原始法或?qū)ε挤?考慮到原始法能直觀、簡(jiǎn)明地反映路網(wǎng)拓?fù)浣Y(jié)構(gòu)，且便于研究者分析網(wǎng)絡(luò)效率，故本文選用原始法構(gòu)建路網(wǎng).

1.1 突發(fā)事件的特點(diǎn)

突發(fā)事件的主要特點(diǎn)是發(fā)生的隨機(jī)性與影響的不可預(yù)知.

對(duì)于發(fā)生的隨機(jī)性，采用魯棒性分析方法，旨在從中觀層面上得到不同路段失效后路網(wǎng)魯棒性的變化情況.另一方面，由于負(fù)面效應(yīng)越大的突發(fā)事件對(duì)路網(wǎng)的破壞力也越強(qiáng)，這反映在網(wǎng)絡(luò)中則是失效路段數(shù)的增多，故本文嘗試用失效路段數(shù)對(duì)突發(fā)事件的影響進(jìn)行差異化評(píng)價(jià).下面，先量化突發(fā)事件發(fā)生的隨機(jī)性.

1.2 突發(fā)事件下的路網(wǎng)拓?fù)渥兓?/h3>

暫不考慮交通流等因素，假定某條路段出現(xiàn)突發(fā)事件將立即導(dǎo)致路段失效，其拓?fù)渥兓鐖D1所示.

圖1 路網(wǎng)拓?fù)湫螒B(tài)變化Fig.1 Road network’topological morphological changes

進(jìn)一步地，將突發(fā)事件視為對(duì)路網(wǎng)的一次隨機(jī)攻擊，則該環(huán)境下的路網(wǎng)拓?fù)渥兓捎敏敯粜苑椒ㄟM(jìn)行評(píng)估[8-9].

1.3 城市道路網(wǎng)魯棒性分析

路網(wǎng)魯棒性是指路網(wǎng)在遭受隨機(jī)或蓄意攻擊時(shí)，保持正常運(yùn)作的能力，由魯棒性指標(biāo)刻畫(huà).本文從中觀層面選?。壕W(wǎng)絡(luò)效率、最大連通子圖2類與路段相關(guān)的魯棒性指標(biāo)進(jìn)行分析.

(1)網(wǎng)絡(luò)效率.

網(wǎng)絡(luò)效率是利用節(jié)點(diǎn)間最短路的均值衡量路網(wǎng)的通行效率[9].若在路段失效前后其變化量ΔE越大，表明該路段對(duì)路網(wǎng)魯棒性的影響越顯著.ΔE計(jì)算公式為

式中：E為網(wǎng)絡(luò)效率；N為節(jié)點(diǎn)集合；n為路網(wǎng)節(jié)點(diǎn)總數(shù)；分別為路段失效前后連接節(jié)點(diǎn)k1，k2間的最短路.

(2)最大連通子圖.

最大連通子圖是指以最少的邊把網(wǎng)絡(luò)中盡可能多的節(jié)點(diǎn)連接起來(lái)的子圖[9].其相對(duì)大小變化量ΔS反映了路網(wǎng)在遭受隨機(jī)攻擊后，拓?fù)浣Y(jié)構(gòu)發(fā)生的改變.ΔS計(jì)算公式為

對(duì)于路網(wǎng)G(N,L)，N為點(diǎn)集合，L為邊集合.采用遍歷法，輪流去掉G(N,L)中的路段，分別計(jì)算其魯棒性指標(biāo)的變化量：ΔE和ΔS.然后，尋找出ΔE和ΔS均較大的路段，構(gòu)成潛在關(guān)鍵路段集合L′(備選集).

注意：在不考慮路網(wǎng)交通流的條件下，潛在關(guān)鍵路段集L′可視為模型可行域的壓縮.這既有助于簡(jiǎn)化模型求解規(guī)模，又能建立路網(wǎng)魯棒性與關(guān)鍵路段識(shí)別指標(biāo)間的聯(lián)動(dòng)關(guān)系.

接著，完成單條到多條路段失效后的路網(wǎng)關(guān)鍵路段集識(shí)別，以此評(píng)價(jià)不同類型突發(fā)事件對(duì)路網(wǎng)的影響.

2 關(guān)鍵路段集識(shí)別

本文將突發(fā)事件前后路網(wǎng)總阻抗的變化量作為識(shí)別指標(biāo)[1-4,7-8]，研究起訖點(diǎn)(Origin-Destination，OD)需求固定的道路交通網(wǎng)絡(luò)，并在潛在關(guān)鍵路段集L′的基礎(chǔ)上，構(gòu)建一般化的關(guān)鍵路段集識(shí)別模型.

2.1 符號(hào)說(shuō)明

對(duì)路網(wǎng)G(N,L)進(jìn)行建模，模型運(yùn)用的符號(hào)變量及其意義如表1所示.

表1 模型的符號(hào)變量說(shuō)明Table 1 Notation’s description in the model

2.2 目標(biāo)函數(shù)

與傳統(tǒng)方法[1-4,7-8]不同，本文構(gòu)建的目標(biāo)函數(shù)為“max型”，用于尋找使路網(wǎng)G(N,L)總阻抗變化最大的關(guān)鍵路段，對(duì)應(yīng)的識(shí)別指標(biāo)為

2.3 約束條件

模型的約束條件分為3類：路段通行能力約束、路徑流量約束和路網(wǎng)均衡約束.引入相應(yīng)的0-1變量進(jìn)行描述.

(1)通行能力約束.

首先，利用路段0-1變量ua，ua∈{0,1}、路段a通行能力Ca、失效路段數(shù)k等來(lái)表征路段通行能力約束，即

式(4)實(shí)現(xiàn)了突發(fā)環(huán)境下路網(wǎng)從單條到多條路段失效的情景刻畫(huà)；式(5)描述了路段通行能力限制.

(2)路徑流量約束.

式(6)中，當(dāng)路徑p是均衡狀態(tài)下的可行路徑時(shí)，參數(shù)，從而保證了路徑流量的非負(fù)性.

(3)路網(wǎng)均衡約束.

式(7)保證了路網(wǎng)需求均衡；式(8)刻畫(huà)了路段交通流；式(9)描述了有效路徑阻抗.

綜上，該模型從路段、路徑、路網(wǎng)等3個(gè)方面約束了突發(fā)環(huán)境下的網(wǎng)絡(luò)流量平衡，是一個(gè)混合0-1非線性規(guī)劃，求解算法較為復(fù)雜且不能保證獲得可行解[5]，故需進(jìn)行線性化處理.

2.4 線性化處理

不難發(fā)現(xiàn)：除了目標(biāo)函數(shù)與約束條件的式(9)含有路段阻抗ta，需利用BPR函數(shù)計(jì)算，模型其余部分均為線性形式，故只對(duì)這兩部分進(jìn)行處理.

(1)目標(biāo)函數(shù)線性化.

故，可在前文“路徑流量約束”中增設(shè)表征Wardrop均衡原理的約束條件，即

實(shí)現(xiàn)原始目標(biāo)函數(shù)從路段形式到路徑形式的等價(jià)轉(zhuǎn)換.轉(zhuǎn)換后的目標(biāo)函數(shù)為

其決策變量是grs(參數(shù)drs、均已知).它通過(guò)約束條件式(11)和參數(shù)緊密聯(lián)系，而參數(shù)在“路網(wǎng)均衡約束”中由式(7)～式(9)量化.

(2)約束條件線性化.

路段阻抗ta一般按BPR函數(shù)計(jì)算[5]，即

式中：α為具體參數(shù)，本文取α=0.15.

顯然，式(14)對(duì)于βa是線性的.下面，利用xa對(duì)βa進(jìn)行“分段逼近”，如圖2所示.

圖2 βa的分段線性化逼近Fig.2 Piecewise linear approximation ofβa

圖2中，v為區(qū)間數(shù)；為xa在對(duì)應(yīng)區(qū)間的值.非線性函數(shù)被v個(gè)線性函數(shù)“逼近”.顯然，當(dāng)v越大，函數(shù)逼近的效果越理想.本文取v=50，將逼近方式表述為

式(15)和式(16)用于確定區(qū)間劃分方式；式(17)采用“層層遞加”的方法“逼近”βa.

最后，得到模型的最終形式為

式(19)為通行能力約束；式(20)為路徑流量約束；式(21)為路網(wǎng)均衡約束；式(22)為分段線性約束.目標(biāo)函數(shù)和約束條件均是線性的，且含有ua、等3個(gè)0-1變量，是典型的混合0-1規(guī)劃問(wèn)題.

3 求解算法

利用分支定界法求解通過(guò)線性化處理的混合0-1規(guī)劃問(wèn)題.

Step 0初始化.對(duì)G(N,L)進(jìn)行初始配流，得到正常情況下各路段的初始阻抗、初始交通量及分段線性因子

Step 1事故模擬.確定失效路段數(shù)k(k≤K)，從潛在關(guān)鍵路段集合L′中選擇k個(gè)路段，將它們從G(N,L)刪除，得到更新路網(wǎng)G′(N′,L-k).

Step 2標(biāo)準(zhǔn)化.依據(jù)G′(N′,L-k)將(P0)轉(zhuǎn)變?yōu)椤皹?biāo)準(zhǔn)形式”，便于直接套用單純形法求解，并置Z″初值為+∞.

Step 3分支.選擇下標(biāo)i∈NF，用單純形法解松弛子問(wèn)題，解為x()i，目標(biāo)函數(shù)值為 fi；如果無(wú)解，則置fi=+∞.

Step 4若fi=+∞，則置NF=NF-{i}，轉(zhuǎn)Step8；否則，執(zhí)行Step5.

Step 5若fi≥Z″，則置NF=NF-{}i，轉(zhuǎn)Step8；否則，執(zhí)行Step6.

Step 6定界.若 fi＜Z″，且x()i∈S()P0，則置Z″=fi，xˉ=x()i，NF=NF-{}i，轉(zhuǎn) Step8；否則，執(zhí)行Step7.

Step 7再分支.若 fi＜Z″，且，則將分解成2個(gè)子集，i1,i2∈NF，置轉(zhuǎn)Step3.

Step 8若NF≠?，則轉(zhuǎn)Step3；否則，算法終止，xˉ為(P0)的最優(yōu)解，Z″為目標(biāo)函數(shù)值.

在最后的可行解中，通過(guò)觀察參數(shù)ua中的零元素，即可找到對(duì)應(yīng)的關(guān)鍵路段.至于關(guān)鍵路段的數(shù)目(零元素個(gè)數(shù))則由失效路段數(shù)k決定.

4 算例分析

算例網(wǎng)絡(luò)G(N,L)由4個(gè)OD對(duì)、21個(gè)節(jié)點(diǎn)和33條路段組成，如圖3所示.路段具體參數(shù)如表2所示.網(wǎng)絡(luò)上共 4 個(gè) OD 對(duì)：(1,14)、(1,18)、(4,14)、(4,18).網(wǎng)絡(luò)的各條路段均是雙向的，限于論文篇幅，只列出了正向路段的基本參數(shù)并進(jìn)行了魯棒性分析與網(wǎng)絡(luò)配流.

下面，分別進(jìn)行路網(wǎng)特性分析與關(guān)鍵路段集識(shí)別：

(1)路網(wǎng)特性分析.

每次從G(N,L)中刪除1條路段，運(yùn)用Matlab2012a按式(1)和式(2)計(jì)算突發(fā)事件前后路網(wǎng)魯棒性指標(biāo)的變化量ΔE和ΔS，結(jié)果如圖4所示.

圖3 算例網(wǎng)絡(luò)Fig.3 Example network

表2 路段基本參數(shù)(正向)Table 2 Links’basic parameters(Forward direction)

圖4 突發(fā)環(huán)境下的路網(wǎng)魯棒性指標(biāo)變化Fig.4 Road network’s robustness index changes under emergency environment

將圖 4中ΔE與ΔS的均值：，作為路網(wǎng)潛在關(guān)鍵路段的篩選條件，選擇變化量均大于的路段構(gòu)成潛在關(guān)鍵路段集合L′，即

式中：j為路段編號(hào).

(2)關(guān)鍵路段集識(shí)別.

設(shè)OD需求為

先從單條路段(k=1)失效入手，得到對(duì)應(yīng)的關(guān)鍵路段識(shí)別指標(biāo)(Z″-Z0)，結(jié)果如表3所示(以無(wú)通行能力約束的關(guān)鍵路段識(shí)別模型[1-4]作對(duì)比).

表3 識(shí)別結(jié)果對(duì)比(k=1)Table 3 Comparison of recognition results(k=1)

由表3可知，在k=1的情況下，網(wǎng)絡(luò)能夠滿足相應(yīng)的OD需求，且2種模型對(duì)關(guān)鍵路段的識(shí)別結(jié)果均為：路段5、路段10、路段11和路段23.

接著，將k:2→8逐一取值，進(jìn)行多條路段失效(k＞1)的路網(wǎng)關(guān)鍵路段集識(shí)別，結(jié)果如表4所示.

由表4可知，對(duì)于多路段失效，2種模型的識(shí)別結(jié)果也基本相同.但傳統(tǒng)模型耗時(shí)隨著失效路段數(shù)的增多呈現(xiàn)“指數(shù)增長(zhǎng)”，而本文模型耗時(shí)卻“穩(wěn)中有降”.原因在于：傳統(tǒng)模型需要在備選集中進(jìn)行一次排列組合操作，并遍歷各種可能的關(guān)鍵路段組合，這導(dǎo)致計(jì)算復(fù)雜度顯著增大；而本文模型以零元素個(gè)數(shù)表示關(guān)鍵路段數(shù)，計(jì)算難度會(huì)隨著零元素個(gè)數(shù)的增加而平穩(wěn)下降.

表4 多條路段失效下的路網(wǎng)關(guān)鍵路段集識(shí)別Table 4 Road network’s critical links set identification with multiple links failure

另外，對(duì)比多路段失效與單條路段失效的識(shí)別結(jié)果，有：①(4,5)、(4,5,10)、(4,5,10,12,28)等集合的路段在幾何拓?fù)渖蠜](méi)有鄰接關(guān)系；②關(guān)鍵路段集并非表3中關(guān)鍵路段的簡(jiǎn)單集成，如表4關(guān)鍵路段集里的路段4、路段12、路段28等，在表3的排名均靠后.

為了解釋上述現(xiàn)象，本文試對(duì)失效路段數(shù)與識(shí)別指標(biāo)值間的關(guān)系進(jìn)行描述：先繪制散點(diǎn)圖，然后利用非線性插值擬合關(guān)系曲線，結(jié)果如圖5所示.

由圖5可知，曲線擬合度很高(97.77%)，且走勢(shì)變化與文獻(xiàn)[7]和[9]中路網(wǎng)魯棒性分析結(jié)果是“逆向”的.這說(shuō)明，突發(fā)環(huán)境下的路網(wǎng)魯棒性與總阻抗變化量之間存在“逆向”曲線關(guān)系：即隨著失效路段增多，路網(wǎng)將變得更為脆弱且漸趨其魯棒性的極限.故可利用擬合曲線實(shí)現(xiàn)兩者的相互轉(zhuǎn)化.

圖5 失效路段數(shù)與指標(biāo)值的關(guān)系Fig.5 Relationship between with the number of links failure and index values

5 結(jié)論

本文針對(duì)突發(fā)環(huán)境下的路網(wǎng)關(guān)鍵路段集識(shí)別，得到相關(guān)結(jié)論如下：

(1)考慮路段通行能力約束，可有效降低對(duì)關(guān)鍵路段的誤判；

(2)關(guān)鍵路段集并非若干關(guān)鍵路段的集成，其構(gòu)成元素一般無(wú)鄰接關(guān)系；

(3)突發(fā)環(huán)境下的路網(wǎng)魯棒性與總阻抗變化量間存在“逆向”曲線關(guān)系.

然而，如何在獲得關(guān)鍵路段的基礎(chǔ)上進(jìn)行路網(wǎng)應(yīng)急控制，則是未來(lái)的研究方向.

參考文獻(xiàn)：

[1]BERDICA K.An introduction to road vulnerability:What has been done,is done and should be done[J].Transport Policy,2002,9(2):117-127.

[2]D'ESTE G M,TAYLOR M A P.Model network vulnerability at the level of the national strategic transport network[J].Journal of the Eastern Asia Society for Transportation Studies,2001,1(2):1-14.

[3]JENELIUS E,PETERSEN T,MATTSSON L G.Road network vulnerability:Identifying important links and exposed regions[J].Transportation Research A,2006,6(40):537-560.

[4]SULLIVAN J L,NOVAK D C,et al.Identifying critical road segments and measuring system-wide robustness in transportation networks with isolating links:A linkbased capacity-reduction approach[J].Transportation Research Part A,2010,44(95):323-336.

[5]WANG D Z W,LIU H,SZETO W Y.Identification of critical combination of vulnerable links in transportation networks:A global optimisation approach[J].Transportmetrica A:Transport Science,2016,12(4):346-364.

[6]FARAHANI R Z,MIANDOABCHI E,SZETO W Y,et al.A review of urban transportation network design problems[J].European Journal of Operational Research,2013,229(2):281-302.

[7]張璽.基于網(wǎng)絡(luò)效率的日變路網(wǎng)脆弱性識(shí)別方法[J].交通運(yùn)輸系統(tǒng)工程與信息，2017,17(2):176-182.[ZHANG X.Day-to-day road network vulnerability identification based on network efficiency[J].Journal of Transportation Systems Engineering and Information Technology,2017,17(2):176-182.]

[8]李彥瑾,羅霞,車國(guó)鵬.突發(fā)擁擠條件下城市道路網(wǎng)脆弱性識(shí)別[J].公路交通科技,2017,34(5):129-136.[LI Y J，LUO X，CHE G P.Vulnerability identification of urban road network underabruptcongestion condition[J].Journal of Highway and Transportation Research and Development,2017,34(5):129-136.]

[9]ZHAO G F,YUAN S W,CI Y S.Analysis of complex network property and robustness of urban road network[J].Journal of Highway and Transportation Research and Development,2016,33(1):119-124.