隨機交通網(wǎng)絡(luò)漸近連通可靠性分析

馬洪偉, 周溪召

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

?

隨機交通網(wǎng)絡(luò)漸近連通可靠性分析

馬洪偉1,2, 周溪召1

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

應(yīng)用原有拓?fù)浞ǐ@得城市交通網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)圖,利用對偶拓?fù)浞ǖ玫浇煌ňW(wǎng)絡(luò)的對偶圖，建立交通網(wǎng)絡(luò)的隨機網(wǎng)絡(luò)模型。定義交通網(wǎng)絡(luò)的漸近連通可靠性，得到路段連通可靠性、路網(wǎng)規(guī)模及整個路網(wǎng)連通可靠性之間的定量關(guān)系，結(jié)合隨機圖論、大數(shù)定律、漸近方法等證明所得結(jié)論；通過實例說明結(jié)論的應(yīng)用價值。

隨機交通網(wǎng)絡(luò)；漸近連通；可靠性；對偶拓?fù)浞?/p>

0 引言

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

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

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

1 交通網(wǎng)絡(luò)的隨機網(wǎng)絡(luò)模型

1.1 交通網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖的獲得

交通網(wǎng)絡(luò)連通可靠性分析首要問題是利用一定的規(guī)則處理現(xiàn)實中的交通網(wǎng)絡(luò)。一個交通網(wǎng)絡(luò)由交叉口和路段(或稱為邊) 組成，常用刻畫靜態(tài)交通網(wǎng)絡(luò)的網(wǎng)絡(luò)拓?fù)浞椒ㄖ饕?原有拓?fù)浞?，以邊為拓?fù)浣Y(jié)構(gòu)的邊，交叉口為節(jié)點；對偶拓?fù)浞?，以道路編號或者路名為?jié)點，即相同的路名可用一個節(jié)點代替，交叉口為節(jié)點之間的連線。利用對偶拓?fù)浞ㄞD(zhuǎn)化路網(wǎng)的拓?fù)鋱D實質(zhì)是進行點和邊的相互轉(zhuǎn)化來表達網(wǎng)絡(luò)的連通性。在進行邊轉(zhuǎn)化為點時，原圖中一條邊就轉(zhuǎn)化為對偶圖中的一個點，而在點(交叉口)轉(zhuǎn)化為邊時，要根據(jù)網(wǎng)絡(luò)的連通性而定，通過轉(zhuǎn)化原圖中邊和交叉口的連通概率完全轉(zhuǎn)化為對偶圖中邊出現(xiàn)的概率。

本文首先利用原有拓?fù)浞ń⒔煌ňW(wǎng)絡(luò)圖，然后通過不同路段交通流量和通行能力整合網(wǎng)絡(luò)圖，合并交通流量v和通行能力c接近的路段，拆分交通流量和通行能力差別過大的路徑。具體做法，設(shè)定兩個閾值l和?，對具有同一路名的不同路段s和t，若滿足|vs-vt|>l或|cs-ct|>?，則在網(wǎng)絡(luò)圖中路段s和t作為兩條邊看待，否則可把路段s和t合并為一條邊；對不同路名的相同方向路段s和t若|vs-vt|≤l且|cs-ct|≤?，則兩條道路s和t在網(wǎng)絡(luò)圖中視為一條邊。經(jīng)過上述整合之后，再利用對偶拓?fù)浞梢缘玫剿枰慕煌ňW(wǎng)絡(luò)圖。

1.2 城市交通網(wǎng)絡(luò)的隨機網(wǎng)絡(luò)模型

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

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

2 交通網(wǎng)絡(luò)漸近連通可靠性定義

以下分別從兩個角度，定義交通網(wǎng)絡(luò)的漸近連通可靠性。

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

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

3 交通網(wǎng)絡(luò)漸近連通可靠性證明

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

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

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

先證xn的方差是有界的：考慮E[(xn)(xn-1)]是孤立節(jié)點有序?qū)Φ钠谕麄€數(shù)，因此，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 交通網(wǎng)絡(luò)漸近連通可靠性的應(yīng)用示例

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

圖1 寧波高新區(qū)交通網(wǎng)絡(luò)原始圖

圖2 寧波高新區(qū)交通網(wǎng)絡(luò)對偶圖

圖3 連通概率為0.1時對應(yīng)的隨機網(wǎng)絡(luò)圖

5 結(jié)語

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

本文的研究是基于隨機網(wǎng)絡(luò)模型得到的，有一定的局限性，城市交通網(wǎng)絡(luò)每條道路的連通概率不可能完全相等，因此，不同道路的連通概率將構(gòu)成向量P=(p1,p2,…pi…,pN)，顯然，當(dāng)min{p1,p2,…pi…,pN}≥lnn/n時，結(jié)論3成立，對于min{p1,p2,…,pi,…,pN}≤lnn/n時，整個交通網(wǎng)絡(luò)的連通可靠性會變得更加復(fù)雜，需要繼續(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] 朱順應(yīng),王煒,鄧衛(wèi),唐勇,王波.交通網(wǎng)絡(luò)可靠度及其通路算法研究[J].中國公路學(xué)報,2000,13(1):91-94.

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

[6] 呂斌,牛惠民.信號控制交叉口可靠度建模與仿真[J].交通運輸系統(tǒng)工程與信息,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

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

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

U113

A

1007-3221(2015)03- 0045- 06