李彥瑾，羅 霞

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

0 引言

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

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

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

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

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

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

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

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

對城市道路網(wǎng)進行拓撲分析時，一般采用原始法或?qū)ε挤?考慮到原始法能直觀、簡明地反映路網(wǎng)拓撲結(jié)構(gòu)，且便于研究者分析網(wǎng)絡(luò)效率，故本文選用原始法構(gòu)建路網(wǎng).

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

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

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

1.2 突發(fā)事件下的路網(wǎng)拓撲變化

暫不考慮交通流等因素，假定某條路段出現(xiàn)突發(fā)事件將立即導(dǎo)致路段失效，其拓撲變化如圖1所示.

圖1 路網(wǎng)拓撲形態(tài)變化Fig.1 Road network’topological morphological changes

進一步地，將突發(fā)事件視為對路網(wǎng)的一次隨機攻擊，則該環(huán)境下的路網(wǎng)拓撲變化可用魯棒性方法進行評估[8-9].

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

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

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

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

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

(2)最大連通子圖.

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

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

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

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

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

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

2.1 符號說明

對路網(wǎng)G(N,L)進行建模，模型運用的符號變量及其意義如表1所示.

表1 模型的符號變量說明Table 1 Notation’s description in the model

2.2 目標函數(shù)

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

2.3 約束條件

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

(1)通行能力約束.

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

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

(2)路徑流量約束.

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

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

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

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

2.4 線性化處理

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

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

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

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

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

(2)約束條件線性化.

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

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

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

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

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

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

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

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

3 求解算法

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

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

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

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

Step 3分支.選擇下標i∈NF，用單純形法解松弛子問題，解為x()i，目標函數(shù)值為 fi；如果無解，則置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個子集，i1,i2∈NF，置轉(zhuǎn)Step3.

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

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

4 算例分析

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

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

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

每次從G(N,L)中刪除1條路段，運用Matlab2012a按式(1)和式(2)計算突發(fā)事件前后路網(wǎng)魯棒性指標的變化量Δ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)魯棒性指標變化Fig.4 Road network’s robustness index changes under emergency environment

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

式中：j為路段編號.

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

設(shè)OD需求為

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

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

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

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

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

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

參考文獻：

[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)脆弱性識別方法[J].交通運輸系統(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]李彥瑾,羅霞,車國鵬.突發(fā)擁擠條件下城市道路網(wǎng)脆弱性識別[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.