復雜網絡的交通擁塞緩解策略研究

尹榮榮，王 靜，劉 蕾，鄧玉靜，趙 凝

(燕山大學信息科學與工程學院，河北秦皇島066004)

(燕山大學河北省特種光纖與光纖傳感重點實驗室，河北秦皇島066004)

1 引 言

交通是國民經濟的基礎產業，也是社會發展和人民生活水平提高的基本條件.隨著國民經濟的快速發展，對交通運輸的各種需求明顯增長，交通擁塞問題也隨之產生［1-3］.交通擁塞問題已經嚴重明顯影響人們的正常生活，降低人們的生活質量，因此解決交通擁塞問題十分重要.

近年來，國內外學者針對交通網絡的擁塞問題已經做了許多研究.Jiancheng Long 等［4］利用細胞傳輸模型，模擬交通阻塞的形成和消散，提出一種應用于事故擁塞的細胞傳播模型.在此基礎上利用交通阻塞傳播的空間拓撲結構，結合車輛禁行的概念，提出了有效的控制策略來分散基于事故的交通擁堵［5］.Liang Qi 等［6］在信號交叉口設計了兩層策略，通過增加城市交通警示燈來防止基于事故的城市交通擁堵.Shaohu Tang 等［7］提出了基于城市交通需求的區域劃分方法，結合過飽和區域優化控制方法，建立了基于多學科設計優化的子區域信號優化控制及分布式協同控制模型.Gunasekaran Muthumanickam 等［8］提出了一種交通擁堵控制方法，主要探討了滑動窗與流量密度的關系，以減少交通阻塞控制機制中的時延.Chantong Lam 等［9］利用當地政府提供的在線圖像，提出了一種經濟的實時城市交通擁堵檢測系統.李彥瑾等［10］構建路網的幾何拓撲圖，依次從拓撲圖中刪除擁堵節點，建立評價指標衡量路網通行效率，并計算級聯失效時的路網擁堵度.孫景昊等［11］基于實時演算理論，針對定時和自適應兩類信號控制系統，建立了統一的城市交通網絡形式化模型，控制交通擁塞.Zeng Guanwen［12］對大量的城市交通實測數據進行研究，在不同的流量動態下，兩種臨界滲流行為模式在相同的網絡拓撲結構中發生切換，有利于理解和提高交通彈性.Brennand Celso A R L 等［13］通過道路分類和為車輛提供新路線的方法，提出一種用于控制擁塞的流量服務模型.文獻［4-13］都是從控制信號燈與減少流量等方面對交通擁塞問題進行研究，為交通擁塞問題的解決作出了貢獻.

由于交通網絡存在的一個重要特點——時空分布的復雜性［14］，在解決交通擁塞問題時，需要考慮交通網絡拓撲具有的結構特征.因此，一些研究學者利用復雜網絡理論解決交通擁塞問題.李樹彬等［14］運用改進的中觀交通流模型，研究了網絡拓撲結構對交通擁堵的影響，進而分析復雜網絡上的交通傳播動力學特征和傳播規律.SoléRibalta Albert 等［15］基于復雜網絡中出現的擁塞現象，提出了交通網絡擁塞的預測模型.該模型能夠分析并預測城市環境中的擁堵問題，具有良好的可分析性和可迭代求解性.Shibao Li 等［16］基于復雜網絡模型，提出了一種基于交通優先級擁塞控制路由策略，可用于解決不同交通擁塞情況.陳偉哲等［17］基于大型城市道路網絡具有無標度分布的性質，提出了一個適用于封閉小區開放問題的城市道路網絡模型，提高了城市路網的通行效率.陳曉明等［18］針對城市交通網絡中旅客在公共交通出行路徑選擇時的問題，提出一種基于雙層復雜網絡的城市交通網絡協同優化方法，能夠使網絡全局效率和旅客換乘行為達到最優.Lishan Sun 等［19］基于復雜網絡理論，提出了一種基于耦合映射格的加權級聯失效模型，為緩解交通擁塞提供了理論支撐.上述文獻運用復雜網絡從理論上對交通擁塞問題進行了研究，但是結合交通流入/流出量與行駛過程中隨機性不夠緊密.

本文將城市交通網絡映射為雙向網絡，定義節點的流入、流出量;將道路關閉的策略引入到網絡中，擁塞節點的流入道路從全部關閉逐漸開放，得到擁塞緩解時間，制定擁塞的緩解規則.通過仿真驗證擁塞緩解規則中的多個參數對擁塞緩解時間的影響，能夠得到此擁塞緩解規則對網絡的堵塞有一定緩解的作用.通過擴大整個網絡的節點總數，擁塞緩解規則同樣適用.

2 負載容量模型

城市交通網絡可以看作一種的復雜網絡，對于交通網絡擁塞問題的研究是將交通網絡抽象為雙向網絡.網絡具體的抽象過程為:將路口抽象為節點，基于道路上車輛的行駛規則是按雙向車道行駛，即兩個相反的方向行駛，由此道路抽象為具有流入/流出的雙向的邊.那么對于路口擁堵而言，車輛的流入少于流出時，路口不易發生擁塞;而車輛的流入多于流出時，路口易發生擁塞;由于車輛的流動性，流入的車輛在經過路口之后成為流出的車輛，路口流入/流出的車輛都是來自路口連接的道路，故道路上的車流量就是道路(支路)的負載.本文側重的是路口擁堵之后如何緩解的問題，實際路口具體有幾條流入/流出的道路，是針對路口的道路數而言的，由此將路口的道路數抽象為節點的度.

2.1 節點負載

眾多研究表明，每個節點上的初始流量與其密切相關［20，21］，因此節點的初始負載定義為與節點度有關的函數，表示如下:

2.2 流入/流出量

設定每個支路(道路)的容量為一定的，單位時間內，i 節點的信息通過某一支路達到鄰居節點j.此時，支路上i 節點的流出量也就是j 節點流入量，因此i 節點的支路流出量等于鄰居節點j 的支路流入量.每個節點、每個支路之間的流量是不同的，本文認為路徑長度越長的支路，單位時間內的流入流出量越大，由此定義支路上單位時間內的流入流出量和支路路徑長度成正比的存在，表示如下:

其中，Lin(ij)為節點i 到節點j 支路上每秒的信息流入量，Lout(ij)為節點i 到節點j 支路上每秒的信息流出量，δ 為正比例系數并且δ≥1，Dij表示為節點i 到節點j 的路徑長度。

上述可知，若道路全部開通的情況下，節點的度等于節點的流入度，等于節點的流出度。又因為節點的負載和節點的度成比例存在，所以，節點i 的單位時間內的信息流入量為

同理，單位時間內的信息流出量為

2.3 節點容量

節點容量指的是節點能夠容納負載多少的量值，與節點負載緊密相關.通常情況下，節點的容量定義為與節點初始負載成正比的量［22］，表示如下:

其中，Ci(t)表示為節點的容量，β≥0 是節點容量與節點初始負載的比例參數.

3 擁塞緩解規則

3.1 負載分配規則

交通擁塞發生以后，整個網絡需要按照一定的規則進行負載分配，直至擁塞緩解完畢，并且整個網絡的節點不再擁塞為止.

3.1.1 傳遞概率

負載量在信息傳遞過程中，到達每個節點的可能性不同(即交通行駛過程中的隨機性).節點i 的負載，需要通過鄰居節點傳送到目的節點上，認為節點的度越大，通過該節點的可能性越大，即將從節點i 到節點j 的可能性，設為度的比值:

其中，節點j 是節點i 的鄰居節點，εij為傳送過程中從節點i到達任一鄰居節點j 的可能性。由于節點i 的信息若要流向目的節點，肯定需要通過i 的鄰居節點j，其可能性之和符合全概率公式.

3.1.2 最短緩解時間

假設節點i 當前的負載量為Li(t)(Li(t)＞Ci(t))，即該節點發生擁塞，需要將其多余負載向鄰居節點進行分配.若節點能正常工作，在僅僅只考慮i 節點自身的緩解能力情況下，節點i 緩解這些多余負載需要用一定的時間，即當=0時，此時節點擁塞緩解時間最短為

其中，Ti為僅考慮節點的本身的緩解能力下的擁塞緩解時間.

但是在緩解節點擁塞的過程中，需要考慮交通行駛的隨機性。將擁塞節點的流入道路全部關閉時，結合公式(6)按照交通中傳遞的概率εj進行分配代入公式(7)，能夠得到考慮交通傳遞概率時，擁塞緩解節點所需的最短時間，即在流入量為0，節點只向外流出時，節點緩解多余負載所需的時間為:

3.1.3 擁塞緩解時間

下面討論在緩解時間內，鄰居節點到擁塞節點的流入量從全部關閉至逐漸開放，由于分配到各個鄰居節點的負載不同，開放不同的節點(本文中按鄰居節點度從大到小開放道路)，節點擁塞緩解的時間也有所不同，將此思想代入公式(8)，節點擁塞緩解時間定義如下:

由式(10)能夠得到，開放關閉道路個數n 越大，節點擁塞緩解時間越大;路徑正比例系數δ、容量比例β、負載強度 τ 越大，越小，其中 δ 與成反比關系.而失效節點的度ki、鄰居節點的度kj、路徑長度Dij與的關系無法直接從公式中推導出來.

本文重點討論在道路擁塞的情況下，所有流入道路從關閉至逐漸開通時，開通的關閉道路數n 對擁塞緩解時間的影響.從上述的推導式(10)中可知，δ、τ 為影響擁塞緩解時間的次要影響參數:δ 為支路路徑的正比例系數并且δ≥1，對于的影響較小，本文中設δ=1;τ 為控制初始節點負載強度的可調參數，并且τ≥1，本文中設τ=1.β、n 為公式(10)中的主要影響參數:β≥0 是節點容量與節點初始負載的比例參數;n 為開放關閉道路的個數，n≥1.

3.2 擁塞緩解規則

圖1 緩解規則流程圖Fig.1 Flow chart of mitigation rules

對于擁塞緩解的規則，是將路口關閉的策略引入到網絡中.在路口i過載時，將流向節點i的道路從全部關閉至逐漸開放，將節點i 的多余負載按一定規則分配到鄰居節點上，計算此時緩解負載所用的時間.整個擁塞緩解的規則，如圖1所示.

4 仿真驗證

大量的文獻表明城市交通網絡呈現出復雜網絡的特性［23，24］.Wu Jianjun 等［25］對北京市公交網絡進行研究，實驗結果表明，北京公交網絡分布呈冪律分布.Dimitrov Stavri Dimitri 等［26］指出城市交通網絡的度分布服從廣義的冪律分布，即無標度網絡特性.因此，本文仿真在BA 無標度網絡基礎上進行驗證，具體的網絡拓撲參數如表1 所示.

表1 實驗參數Table 1 Experimental parameters

在上述參數的網絡下，將各個參數對擁塞緩解規則的影響分別進行仿真驗證.

4.1 容量比例

由式(10)中理論中可以得到，節點容量與節點初始負載的比例參數β 越大，擁塞緩解時間越小，下面仿真驗證容量比例β 的變化對擁塞緩解時間的影響，結果如圖2 所示.

圖2 容量比例β 的變化對擁塞緩解時間 的影響Fig.2 Impact of capacity ratio β change on congestion mitigation time

由圖2 可以看出，β 由小到大變化時，擁塞緩解時間T1i相應變小，與理論中分析的變化相吻合，β 表示節點的容量比例參數，節點容量越大，緩解擁塞的能力越強，與一般認知相符.由于幾條曲線變化規律一致，但是數值較小，表示容量比例β 的變化對擁塞緩解時間的影響較小，對擁塞緩解時間的影響可以忽略不計，因此，本文選取β=1 作為節點容量與節點初始負載的比例參數.

圖3 開通關閉道路的個數n 對擁塞緩解時間 的影響Fig.3 Impact of the number of open and closed roads n on congestion mitigation time

4.2 開通關閉道路的個數

從公式(10)中可以看出，開放關閉道路的個數n 對擁塞緩解時間有一定的影響，具體的變化結果如圖3 所示:

4.3 失效節點度

從公式(10)中可以看出，除開放關閉道路的個數n 以外，失效節點度的變化對擁塞緩解時間有一定的影響，具體的變化結果如圖4 所示.

圖4 不同的失效節點度下，擁塞緩解時間的變化Fig.4 Changes in congestion mitigation time under different failure node degrees

從圖4 可知，單從一條曲線可以看出，開通關閉道路的個數n 越大，擁塞緩解時間也隨之增大，有明顯的變化趨勢.從多條曲線對比可知，失效節點度ki越大，擁塞緩解時間的拐點越來越明顯.

為了更好的分析圖4，將圖4 局部放大，可得到圖5.

圖5 局部放大的不同度下擁塞緩解時間變化Fig.5 Changes of congestion mitigation time under different degrees of local magnification

由圖5 所示，在 ki=6、ki=10、ki=14、ki=18 每相鄰兩曲線都存在重合點(本文稱為拐點)，以ki=14 和ki=18 曲線為例，兩曲線在n=7 時重合，在該拐點以前，相同的開通關閉道路個數n 下，失效節點度ki越大，擁塞緩解時間越大;在拐點之后，失效節點度ki越大，擁塞緩解時間越小.但是，對于一條曲線在拐點之后，隨著開通關閉道路個數n 越大，擁塞緩解時間迅速變化.進一步可知，ki=6、ki=8、ki=10 的相鄰曲線分別在n=3、n=4 處重合，變化規律同上.由上述規律可得，一般拐點存在于處，對應的擁塞緩解時間都比較小.由此，為保證路口能夠獲得較短的擁塞緩解時間，開通關閉道路個數應為.

4.4 節點總數

上述仿真驗證都是在節點總數一定的情況下，但是仿真環境中的節點總數N 變化對擁塞緩解時間的影響，需要進一步仿真驗證.因此，本文在仿真區域一定的情況下，以失效節點度ki=10 為例，將節點總數N 變化對擁塞緩解時間的影響進行驗證如圖6 所示.

圖6 節點總數N 變化對擁塞緩解時間的影響Fig.6 Impact of total number of nodes N on congestion mitigation time

由圖6 所示，節點總數 N=300，N=500，N=800 對擁塞緩解時間的影響三條曲線幾乎重疊，因此，節點總數N 變化對擁塞緩解時間幾乎沒有影響.由此可知，本文中的擁塞緩解規則對節點疏密分布的區域都可適用.

4.5 仿真小結

上述仿真的結果符合人們平時的認知，關閉擁塞節點的流入量，能夠對節點擁塞起到緩解作用.通常情況下，在交通網絡中可以通過控制紅綠燈的時間配合擁塞的緩解，擁塞緩解時間對應的是紅綠燈的時長，延長鄰居節點紅綠燈的時長，擁塞節點的交通流入量可以得到控制.當流入方向的道路全部關閉時，擁塞緩解所用時間最短，隨著道路逐漸開通，擁塞緩解時間相應增加，為保證路口能夠較快的緩解擁塞，開通關閉道路個數可設定為.

另一方面，將一個節點的堵塞分散到了多點鄰居節點上，單個節點需要分擔的流量會相對減少，可以將擁塞控制在一定時間內，不會造成長時間擁堵.當然，從網絡層面來講，這個過程是一個級聯失效的過程，如何減少整個交通網絡級聯失效的程度和網絡擁塞時間的影響是我們接下來要做的工作.

5 結 論

針對城市交通網絡的擁塞問題，本文基于關閉道路的思想，考慮交通的特點，建立了一種基于復雜網絡的擁塞緩解規則.關閉其他節點流入擁塞節點的負載量，擁塞節點的流出量不變，將一個節點的堵塞分散到了多點鄰居節點上，每個節點需要分擔緩解的負載量會相對減少.仿真分析可知，該擁塞緩解規則不僅能夠減小交通擁塞的緩解時間，可以將擁塞一定程度內控制在一定時間內，而且適用的網絡規模比較廣泛.