馬洪偉, 周溪召

(1.上海海事大學 經濟管理學院，上海 200135； 2.上海電機學院 商學院，上海 201306)

?

隨機交通網絡漸近連通可靠性分析

馬洪偉1,2, 周溪召1

(1.上海海事大學 經濟管理學院，上海 200135； 2.上海電機學院 商學院，上海 201306)

應用原有拓撲法獲得城市交通網絡的拓撲結構圖,利用對偶拓撲法得到交通網絡的對偶圖，建立交通網絡的隨機網絡模型。定義交通網絡的漸近連通可靠性，得到路段連通可靠性、路網規(guī)模及整個路網連通可靠性之間的定量關系，結合隨機圖論、大數定律、漸近方法等證明所得結論；通過實例說明結論的應用價值。

隨機交通網絡；漸近連通；可靠性；對偶拓撲法

0 引言

自然災害和交通擁堵使人們越來越重視交通運輸網絡的可靠性，目前對城市道路網絡可靠性研究主要有三類：通行能力可靠性、行程時間可靠性和連通可靠性。其中，連通可靠性是交通網絡可靠性分析研究的基礎，只有在連通的基礎上才能確保各類交通流完成出行。

連通可靠性反映的是交通網絡節(jié)點兩兩間保持連通的概率，它是進行其它可靠性分析的研究基礎，最早是由日本的Mine Kawai在1982年提出的[1]，隨后，各國學者作了進一步的理論探討[2,3]。早期連通可靠性研究的對象主要是系統的物理結構，考慮的是系統連通性，連通可靠性一般只有0,1兩種狀態(tài)，1代表連通，0代表不連通。城市的交通狀態(tài)是隨機變化的，僅用兩個變量不能反映交通網絡連通的不斷變化，常態(tài)環(huán)境下城市道路連通性有多種狀態(tài)。朱順應、陳曉明、呂斌等采用飽和度法(v/c)來刻畫路段連通可靠性的狀態(tài)，連通的概率是流量v和通行能力c的函數，p=F(v,c)，這樣連通可靠性由{0,1}擴展到[0,1]區(qū)間[4～6]，這種擴展使連通可靠性的應用范圍更廣；但同時又面臨新的問題，雖然通過標定函數可以求得F(v,c)路段的連通可靠性，但由于交通網絡的結構往往比較復雜，規(guī)模過大，整個交通網絡連通可靠性的定量研究會變得非常困難。因此，路段連通可靠性、路網規(guī)模及整個路網系統的連通可靠性之間的關系一直沒有定論。

本文在道路狀態(tài)影響因素方面主要考慮交通流量和通行能力。連通可靠性是流量和通行能力的函數，即連通可靠性p=F(v,c)，p∈[0,1]；用對偶拓撲法獲得交通網絡圖，定義隨機交通網絡的漸近連通可靠性，利用隨機網絡模型研究路段連通可靠性、路網規(guī)模及路網連通可靠性之間的定量關系，在一定條件下一定程度上解決兩個基本問題：a.當路段連通可靠性較小的狀態(tài)下(交通擁堵狀態(tài)或路段遭到毀壞)，路網是不是仍然保持連通的；b. 路網結構和規(guī)模確定條件下，路段連通性和整個路網連通性之間的定量關系，即路段的連通概率為多少時才能保證整個路網是連通的。

1 交通網絡的隨機網絡模型

1.1 交通網絡拓撲結構圖的獲得

交通網絡連通可靠性分析首要問題是利用一定的規(guī)則處理現實中的交通網絡。一個交通網絡由交叉口和路段(或稱為邊) 組成，常用刻畫靜態(tài)交通網絡的網絡拓撲方法主要有:原有拓撲法，以邊為拓撲結構的邊，交叉口為節(jié)點；對偶拓撲法，以道路編號或者路名為節(jié)點，即相同的路名可用一個節(jié)點代替，交叉口為節(jié)點之間的連線。利用對偶拓撲法轉化路網的拓撲圖實質是進行點和邊的相互轉化來表達網絡的連通性。在進行邊轉化為點時，原圖中一條邊就轉化為對偶圖中的一個點，而在點(交叉口)轉化為邊時，要根據網絡的連通性而定，通過轉化原圖中邊和交叉口的連通概率完全轉化為對偶圖中邊出現的概率。

本文首先利用原有拓撲法建立交通網絡圖，然后通過不同路段交通流量和通行能力整合網絡圖，合并交通流量v和通行能力c接近的路段，拆分交通流量和通行能力差別過大的路徑。具體做法，設定兩個閾值l和?，對具有同一路名的不同路段s和t，若滿足|vs-vt|>l或|cs-ct|>?，則在網絡圖中路段s和t作為兩條邊看待，否則可把路段s和t合并為一條邊；對不同路名的相同方向路段s和t若|vs-vt|≤l且|cs-ct|≤?，則兩條道路s和t在網絡圖中視為一條邊。經過上述整合之后，再利用對偶拓撲法可以得到所需要的交通網絡圖。

1.2 城市交通網絡的隨機網絡模型

利用上述方法得到一個交通網絡圖G(A,E)，其中A={a1,a2,…,ai,…,an}表示對偶圖中節(jié)點的集合，實際代表路網道路的集合；記E={e1,e2,…,ei,…,en}為對偶圖中邊的集合，實際表示交通網絡中道路的連通關系。以下討論皆在G(A,E)對偶圖中進行。若要確定網絡圖G(A,E)的連通性，需要確定網絡圖G(A,E)是以何種結構出現的，即圖G(A,E)的邊生成規(guī)律。

對交通網絡的結構研究，多是結合規(guī)則網絡、無標度網絡或隨機網絡等相關模型，這類方法從靜態(tài)角度刻畫了交通網絡的平均距離、度分布、連通性等幾何特征，靜態(tài)網絡模型在刻畫交通網絡連通性隨時間變化特性方面顯得不足，特別是現實中隨著交通需求增大，擁堵加??；交通需求隨機性對連通性的影響主要反映在圖G(A,E)中邊出現的概率，本文的研究基礎是基于隨機網絡模型，網絡圖G(A,E)中邊的集合E={e1,e2,…,ei,…,eq}中每條邊的出現，也就是任何兩點連接成邊以概率p出現，并且每兩點連接形成邊是獨立的，相比而言這種模型能較好的反映交通網絡連通性的隨時間變化的規(guī)律。

2 交通網絡漸近連通可靠性定義

以下分別從兩個角度，定義交通網絡的漸近連通可靠性。

定義2：隨機交通網絡G(A,E)，G(A,E)的頂點n為常數，G(A,E)中任意兩點連通的概率(也是每條邊出現的概率)為p，若存在p0，當p≥p0時，隨機交通網絡G(A,E)是連通的，當p≤p0時，隨機交通網絡G(A,E)是不連通，稱交通網絡G(A,E)具連通概率變大時的漸近連通可靠性，同時稱P0為隨機交通網絡G(A,E)連通可靠性的閾值。

從定義1得知，若交通網絡具有網絡規(guī)模變大時的漸近連通可靠性，當網絡規(guī)模大到一定程度時，即使連通的概率很小，交通網絡仍然是連通的。由定義2知，當交通網絡規(guī)模一定時，路段連通的概率不同，整個交通網絡可能連通，也可能不連通；特別的，在滿足隨機網絡模型條件下，一定存在交通網絡連通可靠性的閾值，交通網絡是具有漸近連通可靠性的。下面結合ER隨機圖模型[7,8]，給出閾值的具體表達式。

3 交通網絡漸近連通可靠性證明

結合兩種定義給出三個結論，并進行證明。

以上結論說明當隨機交通網絡的規(guī)模大到一定程度時，雖然某些道路是不連通的，但整個交通網絡是連通的，結論2沒有說明達到何種程度；從另一個角度考慮，如果網絡規(guī)模確定，連通的概率p增大到某種程度也能保證交通網絡是連通的，至于p要達到何種程度，結論3在一定程度上給予解決。

需要證明存在孤立的節(jié)點的概率收斂于1。

先證xn的方差是有界的：考慮E[(xn)(xn-1)]是孤立節(jié)點有序對的期望個數，因此，E[(xn)(xn-1)]=n(n-1)(1-p)2n-3。xn的方差

=n(n-1)(1-p)2n-3+E(xn)-n2(1-p)2n-2

≤E(xn)+pn2(1-p)2n-3≤E(xn)(1+(lnn-f(n))e-lnn+f(n)(1-p)-2)

=2E(xn)

(1)

分別考察(1)式的前后兩項，對(1)式的第一項：

∵e-f(n)<1，e2n-1/4lnn<1，∴(e-f(n)e2n-1/4lnn)2<1，即(1)式的第一項小于1；對(1)式的第二項

∴e(1-f(n)/2)n3/4n(-1/4)n3/4→0，即(1)式的第二項趨于0；

4 交通網絡漸近連通可靠性的應用示例

如圖1所示，為寧波市高新區(qū)交通網絡圖，利用本文第1.2中的方法，根據某一時段的交通流量和通行能力對路段進行整合，利用對偶圖法得到所需網絡圖如圖2。圖2由39個頂點，236條邊構成，頂點代表道路，邊代表39條道路之間的連通關系。由隨機網絡模型求得，寧波高新區(qū)交通網絡對應邊的連通可靠性約為0.2，有39個點構成的隨機網絡，連通的閾值為ln39/39=0.093，所以，當道路暢通的情況下，邊與邊的連通概率較大，此時整個交通網絡具有較好的連通性。但當邊的連通概率降低時，整個路網的連通可靠性也會降低，如當連通的概率為0.1時，得到的隨機網絡圖為圖3，此時就會出現孤立點，孤立點存在表示道路是不連通的。

圖1 寧波高新區(qū)交通網絡原始圖

圖2 寧波高新區(qū)交通網絡對偶圖

圖3 連通概率為0.1時對應的隨機網絡圖

5 結語

本文利用對偶拓撲法得到交通網絡的網絡拓撲圖，構建起交通網絡的隨機網絡模型，從兩個角度，分別定義交通網絡的漸近連通可靠性，得出兩個結論，當路段連通可靠性為常數時，網絡達到一定規(guī)模，整個路網是連通的；當路網規(guī)模確定時，可以通過提高路段的連通可靠性方法，提高整個交通網絡的連通可靠性。本文所得出的結論在路網規(guī)劃設計方面，從交通網絡行駛時間可靠性視角為城市交通網絡節(jié)點規(guī)模的合理確定提供依據，也可避免城市規(guī)模無限制擴張；在日常交通管理方面當交通網絡某個路段的交通流量達到一定的閾值時，需要重點關注，為交通管理和控制提供幫助。

本文的研究是基于隨機網絡模型得到的，有一定的局限性，城市交通網絡每條道路的連通概率不可能完全相等，因此，不同道路的連通概率將構成向量P=(p1,p2,…pi…,pN)，顯然，當min{p1,p2,…pi…,pN}≥lnn/n時，結論3成立，對于min{p1,p2,…,pi,…,pN}≤lnn/n時，整個交通網絡的連通可靠性會變得更加復雜，需要繼續(xù)深入研究。

[1] Mine H, Kawai H. Mathematics for reliability analysis[M]. Asakurashoten, 1982. 12-14;

[2] Bell M G H, Iida Y. Transport network analysis[M]. NewYork: John Wiley & Sons, 1997. 179-191.

[3] Alan Nicholson, Zhen-Ping Du. Degradable transportation systems: an integrated equilibrium model[J]. Transportation Research B .Vol 3, 1997. 209-223.

[4] 朱順應,王煒,鄧衛(wèi),唐勇,王波.交通網絡可靠度及其通路算法研究[J].中國公路學報,2000,13(1):91-94.

[5] 陳曉明,邵春福,熊志華.混合交通信號交叉口的通行能力可靠度[J].中國公路學報,2008,21(4):99-104.

[6] 呂斌,?；菝?信號控制交叉口可靠度建模與仿真[J].交通運輸系統工程與信息,2011,11(6):45-50.

[7] Bollobas B. Modern graph theory[M]. New York: Springer-Verlag, 2001.

The Asymptotic Connect Reliability Analysis of Stochastic Transportation Network

MA Hong-wei1,2, ZHOU Xi-zhao1

(1.School of Economics and Management, Shanghai Maritime University, Shanghai 200135, China; 2.Shanghai Dianji University, Shanghai 201306, China)

The topology map of urban transportation network is gained by using the original topological method, the dual graph of the transportation network is gotten by using the dual topology method, and the random network model of transportation network is thus established. The asymptotic connectivity reliability of the transportation network is defined, and what is be gained is the quantitative relationship among road connectivity reliability, scale of the road network, and the connectivity reliability of the entire road network. The conclusions in this paper are proved by combining the random graph theory with law of large numbers, asymptotic methods and so on. Finally, the application value is illustrated through an example.

stochastic transportation network; asymptotic connectivity; reliability; dual topology method

2013- 08-28

國家自然科學基金資助項目(61273042)；上海市教育委員會科研創(chuàng)新項目(BYS125);上海海事大學研究生創(chuàng)新基金資助項目(YC2011046)

馬洪偉(1982-),男，山東棗莊人，博士研究生,理學學士,工學碩士；周溪召(1964-),男，浙江寧波人，教授、博士生導師，理學碩士，工學博士。

U113

A

1007-3221(2015)03- 0045- 06