預(yù)防道路交通網(wǎng)絡(luò)級聯(lián)失效的交叉口擴(kuò)容策略

黃 帥，王正武，周振宇

（長沙理工大學(xué)交通運(yùn)輸工程學(xué)院，湖南長沙 410004）

道路交通網(wǎng)絡(luò)作為城市交通活動(dòng)的載體，是國民經(jīng)濟(jì)和城市運(yùn)行的主動(dòng)脈，是確保城市生命線系統(tǒng)正常運(yùn)轉(zhuǎn)的子系統(tǒng)。然而，當(dāng)網(wǎng)絡(luò)中的一個(gè)或少數(shù)幾個(gè)節(jié)點(diǎn)（邊）受到內(nèi)部、外部因素的干擾而失效或故障后，這些失效節(jié)點(diǎn)（邊）會(huì)通過節(jié)點(diǎn)和邊的耦合關(guān)系引起其周邊的節(jié)點(diǎn)和邊的失效，這種連鎖效應(yīng)可能導(dǎo)致整個(gè)網(wǎng)絡(luò)發(fā)生崩潰，這種現(xiàn)象被稱為級聯(lián)失效。級聯(lián)失效雖然不經(jīng)常發(fā)生，但其后果非常嚴(yán)重［1］。因此，預(yù)防道路交通網(wǎng)絡(luò)的級聯(lián)失效具有重要意義。

目前，復(fù)雜網(wǎng)絡(luò)級聯(lián)失效的預(yù)防與控制措施研究集中在3個(gè)方面：①節(jié)點(diǎn)容量優(yōu)化。李勇［2］等人提出了基于級聯(lián)失效的戰(zhàn)域保障網(wǎng)絡(luò)節(jié)點(diǎn)容量優(yōu)化模型。劉漳輝［3］等人探討了如何選取非線性負(fù)荷－容量模型的參數(shù)，以達(dá)到最大化網(wǎng)絡(luò)魯棒性和最小化網(wǎng)絡(luò)投入代價(jià)的目的。彭晶波［4］等人提出了一種針對無線網(wǎng)絡(luò)的單節(jié)點(diǎn)容量最大化方法，尋找一個(gè)最優(yōu)的歸一化信號幅度γopt，以獲得最大化的節(jié)點(diǎn)容量C。②邊增加或刪除。Motter［5］等人認(rèn)為無標(biāo)度網(wǎng)絡(luò)受到初始攻擊后，可以通過刪除一部分低（高）負(fù)載節(jié)點(diǎn)（邊）來控制級聯(lián)失效的傳播。在此基礎(chǔ)上，Zhao［6］等人獲得了最優(yōu)刪除策略。相反地，Hayashi［7］等人提出了增加邊的級聯(lián)失效控制策略。③均勻負(fù)載等其他方法。Schafer［8］等人提出了一種增加網(wǎng)絡(luò)級聯(lián)失效抗毀性的設(shè)計(jì)方法，并通過減少網(wǎng)絡(luò)總負(fù)載來提高網(wǎng)絡(luò)抗毀性。Motter［9］等人認(rèn)為，網(wǎng)絡(luò)的抗毀魯棒性與節(jié)點(diǎn)介數(shù)分布相關(guān)，介數(shù)分布越同質(zhì)，其魯棒性越強(qiáng)；可通過保護(hù)介數(shù)較大的節(jié)點(diǎn)或均勻負(fù)載分布來預(yù)防級聯(lián)失效。趙暉［10］提出了通過導(dǎo)航策略來預(yù)防輸運(yùn)網(wǎng)絡(luò)的級聯(lián)失效。這3種方法中，節(jié)點(diǎn)容量優(yōu)化和邊增加或刪除是通過對網(wǎng)絡(luò)中節(jié)點(diǎn)（邊）重要度的測算、排序，找到網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)（邊）。然后再對關(guān)鍵節(jié)點(diǎn)（邊）采取保護(hù)策略，從而達(dá)到預(yù)防級聯(lián)失效的目的。這2種方法針對性較強(qiáng)，能夠有效利用有限的資源，較大程度地改善了路網(wǎng)通行能力。而均勻負(fù)載則是通過研究網(wǎng)絡(luò)中負(fù)載和容量的分布特點(diǎn)以及節(jié)點(diǎn)之間的路由規(guī)則和負(fù)載分配原則，控制整個(gè)網(wǎng)絡(luò)的“承載極限”來達(dá)到預(yù)防級聯(lián)失效的目的。該方法資源消耗較大，但能更為徹底地改善整個(gè)路網(wǎng)的通行能力。

擴(kuò)大節(jié)點(diǎn)容量預(yù)防級聯(lián)失效的現(xiàn)有研究［11］表明：在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)一定的條件下，節(jié)點(diǎn)容量越大，級聯(lián)失效抗毀性越強(qiáng)，這為通過交叉口擴(kuò)容來預(yù)防道路交通網(wǎng)絡(luò)級聯(lián)失效提供了理論基礎(chǔ)。現(xiàn)有的預(yù)防復(fù)雜網(wǎng)絡(luò)級聯(lián)失效的節(jié)點(diǎn)容量擴(kuò)大措施還只是定性地認(rèn)為擴(kuò)容有利于預(yù)防級聯(lián)失效，但還沒有解決2個(gè)關(guān)鍵問題：①通過擴(kuò)容哪些交叉口來預(yù)防級聯(lián)失效；②交叉口擴(kuò)容多少更有利于減輕級聯(lián)失效的后果。本研究擬構(gòu)建交叉口擴(kuò)容的優(yōu)化算法予以解決。

1 道路交通網(wǎng)絡(luò)級聯(lián)失效模型

道路交通網(wǎng)絡(luò)級聯(lián)失效模型采用負(fù)荷－容量模型［9］，該模型可描述為：

1）初始狀態(tài)：路網(wǎng)中的路段（交叉口）都處于正常狀態(tài)，即各路段（交叉口）的初始流量均小于實(shí)際容量。

2）初始攻擊：刪除某個(gè)路段（交叉口）。

3）流量分配：路段（交叉口）的刪除將導(dǎo)致出行網(wǎng)絡(luò)的OD流在道路網(wǎng)絡(luò)中重新分配，路段（交叉口）流量發(fā)生變化。

4）計(jì)算飽和度并判斷：路段（交叉口）流量的變化導(dǎo)致其交通狀態(tài)也發(fā)生變化。如果所有路段（交叉口）飽和度均小于1，則停止；否則，轉(zhuǎn)5）。

5）更新路網(wǎng)：將飽和度大于1的過載路段（交叉口）刪除，更新路網(wǎng)，并轉(zhuǎn)模型。該模型：邊的容量采用文獻(xiàn)［12］的變化規(guī)律，即

式中：Cj（τ）為節(jié)點(diǎn)j在τ時(shí)間步的容量（假設(shè)交叉口容量是相交道路最大容量的0.9倍）；qj（τ）為節(jié)點(diǎn)j在τ時(shí)間步的流入量，即qj（τ）＝∑iqij（τ）。

6）失效節(jié)點(diǎn)的判斷依據(jù)：以節(jié)點(diǎn)飽和度來描述節(jié)點(diǎn)是否失效。節(jié)點(diǎn)飽和度定義為節(jié)點(diǎn)各關(guān)聯(lián)路段進(jìn)口道的負(fù)荷系數(shù)加權(quán)值，即

式中：λ為整個(gè)節(jié)點(diǎn)的飽和度；n為節(jié)點(diǎn)關(guān)聯(lián)路段進(jìn)口系數(shù)；qi為第i條關(guān)聯(lián)路段進(jìn)口道的負(fù)荷系數(shù)（當(dāng)量交通和通行能力之比），即該關(guān)聯(lián)路段進(jìn)口道的飽和度；Qi為第i條關(guān)聯(lián)路段進(jìn)口道的交通量。

7）采用阻塞程度指標(biāo)J［13］描述級聯(lián)失效的后果，即

式中：qij（τ）為路段（i，j）在τ時(shí)刻的流量，pcu／s；tij（τ）為路段（i，j）在τ時(shí)刻的阻抗，s；qij（0）為初始交通分配后路段（i，j）的流量，pcu／s；tij（0）為初始交通分配后路段（i，j）阻抗，s。

路段阻抗采用BPR等函數(shù)。流量分配可采用用戶最優(yōu)和系統(tǒng)最優(yōu)等交通分配算法。

2 考慮級聯(lián)失效的交叉口擴(kuò)容策略

根據(jù)擴(kuò)容后道路交通網(wǎng)絡(luò)節(jié)點(diǎn)狀態(tài)來判斷應(yīng)該擴(kuò)容哪些交叉口，根據(jù)擴(kuò)容后的阻塞程度指標(biāo)來確定交叉口適合的擴(kuò)容量［4］。提出的擴(kuò)容算法為：

1）初始化。給定道路交通網(wǎng)絡(luò)模型，將出行OD對在道路網(wǎng)絡(luò)中進(jìn)行分配，記錄此時(shí)的阻塞程度指標(biāo)J（0）。

2）攻擊。攻擊路網(wǎng)中的一個(gè)或多個(gè)節(jié)點(diǎn)。

3）調(diào)用級聯(lián)失效流程，判斷級聯(lián)失效后果J1。如果沒有引起級聯(lián)失效，不需擴(kuò)容，結(jié)束算法；否則，轉(zhuǎn)4）（采用擴(kuò)容策略來防止級聯(lián)失效）。

4）擴(kuò)容。

①在攻擊后的網(wǎng)絡(luò)中，選擇飽和度最大的交叉口I1擴(kuò)容K1倍。調(diào)用級聯(lián)失效流程，計(jì)算級聯(lián)失效后果，判斷擴(kuò)容K1倍的效果；繼續(xù)擴(kuò)大擴(kuò)容倍數(shù)至K2＝K1×P，調(diào)用級聯(lián)失效流程，并判斷擴(kuò)容K2的效果；繼續(xù)擴(kuò)容，直至前、后效果不明顯。

②在擴(kuò)容Ke倍后，比較Je和J1。如果效果明顯，則交叉口I1擴(kuò)容Ke倍，并更新網(wǎng)絡(luò)；否則，交叉口I1不擴(kuò)容。

③對更新網(wǎng)絡(luò)進(jìn)行評價(jià)。如果沒有引起大規(guī)模的級聯(lián)失效，則結(jié)束算法；否則，到①中選擇飽和度最大的、未擴(kuò)容的交叉口I2擴(kuò)容K1倍。

算法中，P為交叉口擴(kuò)容倍數(shù)的增長因子，初始取值范圍為1.5＞P＞1；K1為交叉口的初始擴(kuò)容倍數(shù)，初始取值范圍為2＞K1＞1；Ke為交叉口的最佳擴(kuò)容倍數(shù)；Je為交叉口擴(kuò)容最佳倍數(shù)Ke后的路網(wǎng)阻塞程度指標(biāo)。試算時(shí)，取值間隔視具體情況而定，以路網(wǎng)有明顯改善為準(zhǔn)。攻擊可以是單個(gè)節(jié)點(diǎn)（邊）的攻擊、也可以是多個(gè)節(jié)點(diǎn)（邊）的攻擊。本研究的擴(kuò)容量通過試算法優(yōu)化確定，同時(shí)未考慮擴(kuò)容的約束；如果要考慮擴(kuò)容量的約束，則在①中限制最大擴(kuò)容倍數(shù)即可。算法中，若交叉口Ii擴(kuò)容Ke倍（Ke較大）后，Je不收斂或震蕩，考慮資源有限，則結(jié)束算法，擴(kuò)容其他交叉口Ik，并與Ii進(jìn)行比較。若同樣擴(kuò)大Ke倍，擴(kuò)大交叉口Ii的效果好于Ik的，則擴(kuò)容交叉口Ii；反之，則擴(kuò)大交叉口Ik。

3 仿真試驗(yàn)

以長沙市雨花區(qū)主干路網(wǎng)為例，開展試驗(yàn)研究。該路網(wǎng)共有22條邊，15個(gè)節(jié)點(diǎn)，路網(wǎng)如圖1所示，節(jié)點(diǎn)容量見表1。設(shè)出行網(wǎng)絡(luò)共有8個(gè)OD對，出行網(wǎng)絡(luò)OD見表2。各路段容量和自由流阻抗見表3。

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

表1 各初始節(jié)點(diǎn)容量Table 1 Initial capacity of each node

表2 初始OD流量Table 2 Initial OD flow

表3 各路段容量和自由流阻抗Table 3 Each link capacity and the free flow impedance

案例中，交通分配采用UE準(zhǔn)則，初始路網(wǎng)的阻塞程度指標(biāo)為J（0）＝1.109。節(jié)點(diǎn)2被攻擊失效后，將引起級聯(lián)失效，其阻塞程度指標(biāo)J（1）＝1.593，節(jié)點(diǎn)2失效后各節(jié)點(diǎn)的飽和度見表4。

表4 節(jié)點(diǎn)2失效后各節(jié)點(diǎn)的飽和度Table 4 Each node saturation degree after node 2failed

對飽和度最大的節(jié)點(diǎn)14擴(kuò)容，取K1＝1.5，P＝1.1，擴(kuò)容后阻塞程度的變化如圖2所示。

從圖2中可以看出，當(dāng)Ke＝2.92時(shí)，阻塞程度指標(biāo)J收斂。此時(shí)，J（3）＝1.160，各節(jié)點(diǎn)飽和度見表5。

圖2 節(jié)點(diǎn)14擴(kuò)容后阻塞程度變化的趨勢Fig.2 Changes in trends in the degree of obstruction after expansion of node 14

表5 節(jié)點(diǎn)14擴(kuò)容Ke后各節(jié)點(diǎn)飽和度和阻塞程度指標(biāo)Table 5 Each node saturation degree and obstruction index after expansion Keof node 14

從表5中可以看出，仍有8個(gè)節(jié)點(diǎn)擁堵，還需要繼續(xù)擴(kuò)容。對節(jié)點(diǎn)4行擴(kuò)容，擴(kuò)容后阻塞程度的變化如圖3所示。

圖3 節(jié)點(diǎn)4擴(kuò)容后阻塞程度變化的趨勢Fig.3 Changes in the degree of the obstruction after expansion of node 4

從圖3中可以看出，當(dāng)Ke′＝1.99時(shí)，阻塞程度指標(biāo)J收斂。此時(shí)，J′（3）＝1.06，各節(jié)點(diǎn)飽和度見表6。

此時(shí)，路網(wǎng)只有2個(gè)節(jié)點(diǎn)有輕微的擁堵，不再出現(xiàn)級聯(lián)失效，結(jié)束算法。

若對路網(wǎng)中節(jié)點(diǎn)14擴(kuò)容2.92倍，對節(jié)點(diǎn)4擴(kuò)容1.99倍，能有效預(yù)防節(jié)點(diǎn)2遭受攻擊時(shí)引起的級聯(lián)失效。同樣，若對路網(wǎng)其他節(jié)點(diǎn)或多個(gè)節(jié)點(diǎn)進(jìn)行攻擊，也可以采用該擴(kuò)容策略來預(yù)防級聯(lián)失效的發(fā)生。

表6 節(jié)點(diǎn)4擴(kuò)容Ke后各節(jié)點(diǎn)飽和度和阻塞程度指標(biāo)Table 6 Each node saturation degree and obstruction index after expansion Keof node 4

4 結(jié)論

針對道路交通網(wǎng)絡(luò)的特性，結(jié)合負(fù)荷－容量級聯(lián)失效模型，提出了一種預(yù)防級聯(lián)失效的交叉口擴(kuò)容策略，即在特定攻擊下，通過優(yōu)化擴(kuò)容最擁擠交叉口來避免道路交通網(wǎng)絡(luò)的級聯(lián)失效。這種級聯(lián)失效的預(yù)防策略是特定攻擊下的預(yù)防策略。如何制定隨機(jī)攻擊下道路交通網(wǎng)絡(luò)級聯(lián)失效的預(yù)防策略是下階段的研究重點(diǎn)。

（References）：

［1］吳建軍.城市交通網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)復(fù)雜性研究［D］.北京：北京交通大學(xué)，2008.（WU Jian－jun.Research on the complexity of the urban traffic network topology［D］.Beijing：Beijing Jiaotong University，2008.（in Chinese））

［2］李勇，呂欣，譚躍進(jìn).基于級聯(lián)失效的戰(zhàn)域保障網(wǎng)絡(luò)節(jié)點(diǎn)容量優(yōu)化［J］.復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2009，6（1）：69－76.（LI Yong，LV Xin，TAN Yue－jin.Optimization of battle field support network node capacity based on cascading failures［J］.Complex Systems and Complexity Science，2009，6（1）：69－76.（in Chinese））

［3］劉漳輝，陳國龍，湯振立，等.加權(quán)復(fù)雜網(wǎng)絡(luò)相繼故障的節(jié)點(diǎn)動(dòng)態(tài)模型研究［J］.小型微型計(jì)算機(jī)系統(tǒng)，2013，34（12）：2800－2804.（LIU Zhang－h(huán)ui，CHEN Guo－long，TANG Zhen－li，et al.Research on node dynamic model of weighted complex networks cascading failures［J］.Small Microcomputer System，2013，34（12）：2800－2804.（in Chinese））

［4］彭晶波，衛(wèi)國.無線網(wǎng)絡(luò)的單節(jié)點(diǎn)容量最大化方法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2009（8）：1507－1509.（PENG Jing－bo，WEI Guo.Single－node method to maximize the capacity of wireless networks［J］.Small Microcomputer System，2009（8）：1507－1509.（in Chinese））

［5］Motter A E.Cascade control and defense in complex networks［J］.Physics Review Letter，2004，93（9）：1－4.

［6］Zhao L，Park K，Lai Y C，et al.Tolerance of scale－free networks against attack－induced cascades［J］.Physics Review E，2005，72：25－31.

［7］Hayashi Y，Miyazaki T.Emergent rewirings for cascades on correlated networks［J］.Disordered Systems and Neural Networks，2005，25：1－5.

［8］Sch?fer M，Scholz J，Greiner M.Proactive robustness control of heterogeneously loaded networks［J］.Physical Review Letters，2006，96（10）：108－114.

［9］Motter A E，Lai Y C.Cascade－based attacks on complex networks［J］.Physics Review E，2002，66（6）：65－70.

［10］趙暉.一般輸運(yùn)網(wǎng)絡(luò)演化模型及動(dòng)力學(xué)特征的相關(guān)研究［D］.北京：北京交通大學(xué)，2007.（ZHAO Hui.Research in general transport network evolution model and its kinetic characteristics［D］.Beijing：Beingjing Jiaotong University，2007.（in Chinese））

［11］Wu J，Gao Z，Sun H.Cascade and breakdown in scale－free networks with community structure［J］.Physical Review E，2006，74（6）：66－72.

［12］Zheng J F，Gao Z Y，Zhao X M.Modeling cascading failures in congested complex networks［J］.Physica A：Statistical Mechanics and its Applications，2007，385（2）：700－706.

［13］Li B，Li F，Wang R.Modeling capacity of road network based on level of service of network［A］.Proceedings of 2008International Conference on Intelligent Computation Technology and Automation（ICICTA）［C］.Changsha：［s.n.］，2008：626－630.