一種新的多重邊復(fù)雜公交網(wǎng)絡(luò)模型

安新磊，李引珍，馬昌喜

(蘭州交通大學(xué) a.數(shù)理學(xué)院；b.交通運輸學(xué)院,蘭州730070)

一種新的多重邊復(fù)雜公交網(wǎng)絡(luò)模型

安新磊＊a,b，李引珍b，馬昌喜b

(蘭州交通大學(xué) a.數(shù)理學(xué)院；b.交通運輸學(xué)院,蘭州730070)

在現(xiàn)有公交網(wǎng)絡(luò)模型的基礎(chǔ)上,建立了一種新的多重邊公交線路網(wǎng)絡(luò)模型.這種公交線路網(wǎng)絡(luò)模型以公交線路為節(jié)點,公交線路間的若干個相同停靠站點為連邊.同時根據(jù)網(wǎng)絡(luò)拆分的思想，對具有相同站點的三條不同的公交線路,通過引入時滯,將四重邊公交線路網(wǎng)絡(luò)拆分為四個性質(zhì)不同的子網(wǎng)絡(luò),進(jìn)而以Chen系統(tǒng)為網(wǎng)絡(luò)的節(jié)點,研究了四重邊復(fù)雜公交網(wǎng)絡(luò)的全局同步.改變公交車輛之間的控制強度和相同的站點個數(shù),分析了公交車輛的人為調(diào)度和線路優(yōu)化對公交線路網(wǎng)絡(luò)平衡的影響.最后通過Matlab進(jìn)行數(shù)值仿真，為城市公交網(wǎng)絡(luò)的合理調(diào)度提供理論依據(jù).

城市交通；多重邊復(fù)雜網(wǎng)絡(luò);網(wǎng)絡(luò)拆分;復(fù)雜網(wǎng)絡(luò)同步;公交網(wǎng)絡(luò)模型

1 引言

近年來,對復(fù)雜網(wǎng)絡(luò)同步的研究已經(jīng)成為非線性動力學(xué)中的一個熱點問題.大量文獻(xiàn)探討了復(fù)雜網(wǎng)絡(luò)同步的控制條件[1-4].在目前的研究中，對復(fù)雜網(wǎng)絡(luò)的同步研究大多集中在單邊網(wǎng)絡(luò)中,而對具有多重邊的復(fù)雜網(wǎng)絡(luò)同步的研究工作還很少[5-7].而現(xiàn)實生活中,存在很多多重邊復(fù)雜網(wǎng)絡(luò),例如交通網(wǎng)絡(luò),把每個城市看作一個節(jié)點,兩城市間的交通線為邊,兩城市間可能存在多種交通方式,如公路、鐵路、航空線等,這樣的交通網(wǎng)就形成了一個多重邊的復(fù)雜網(wǎng)絡(luò).這種具有多重邊的交通網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和節(jié)點動態(tài)特性會比單邊網(wǎng)絡(luò)更為復(fù)雜,因此更有利于研究交通問題的某些特征.文獻(xiàn)[5-7]根據(jù)邊的性質(zhì)不同,將多重邊復(fù)雜網(wǎng)絡(luò)拆分為若干個性質(zhì)不同的子網(wǎng)絡(luò),進(jìn)而研究了拆分后的網(wǎng)絡(luò)的同步控制和穩(wěn)定性問題.

同時,復(fù)雜網(wǎng)絡(luò)理論在公共交通中的應(yīng)用越來越普遍[8-13].目前,復(fù)雜網(wǎng)絡(luò)在對公交網(wǎng)絡(luò)模型的應(yīng)用研究大都是對網(wǎng)絡(luò)的靜態(tài)特征,如節(jié)點度分布、聚類系數(shù)、最短路徑分布、介數(shù)分布等拓?fù)涮匦赃M(jìn)行實證分析[11,12]，而鮮有文獻(xiàn)對復(fù)雜公交網(wǎng)絡(luò)的動態(tài)特征,如公交網(wǎng)絡(luò)節(jié)點的增長、乘客流量的變化、公交車的人為調(diào)度等對整個網(wǎng)絡(luò)的影響進(jìn)行研究.

本文在已有的公交網(wǎng)絡(luò)建模方法(space L、space P和space R方法)的基礎(chǔ)上,采用新的建模方法(space ML方法)建立了一個新的復(fù)雜公交網(wǎng)絡(luò)模型(公交線路多重邊網(wǎng)絡(luò)).根據(jù)網(wǎng)絡(luò)拆分的思想，將多重邊復(fù)雜公交網(wǎng)絡(luò)模型拆分為多個性質(zhì)不同的子網(wǎng)絡(luò)，同時采用自適應(yīng)控制方法,研究了多重邊復(fù)雜公交網(wǎng)絡(luò)的自適應(yīng)同步問題.通過改變網(wǎng)絡(luò)的耦合強度和邊的重數(shù)，討論了公交車輛之間的控制強度和相同的站點個數(shù)對上述模型同步能力的影響,從而為人們對公交車輛的人為調(diào)度和線路合理優(yōu)化提供理論上的依據(jù).本文提出的這種建模方法是在宏觀上，從整個公交網(wǎng)絡(luò)出發(fā)，理解城市交通網(wǎng)絡(luò)演化的內(nèi)在機理和運行規(guī)律.城市交通網(wǎng)絡(luò)具有與其他復(fù)雜網(wǎng)絡(luò)相似的一些特征，但又具有不同于其他復(fù)雜網(wǎng)絡(luò)的顯著特點，如自主性和選擇性，同時人們又認(rèn)識到，解決大城市問題，必須以路線和道路網(wǎng)絡(luò)為對象進(jìn)行全面分析，而常用的公交網(wǎng)絡(luò)在解決某些問題上就顯得有些欠缺，如公交網(wǎng)絡(luò)上的交通流、級聯(lián)失效、擁堵傳播和公交調(diào)度等問題.

2 多重邊復(fù)雜網(wǎng)絡(luò)模型的同步理論

文獻(xiàn)[5，6]通過引入時滯,運用網(wǎng)絡(luò)拆分的思想將多重邊融合復(fù)雜網(wǎng)絡(luò)拆分成多個子網(wǎng)絡(luò),進(jìn)而建立數(shù)學(xué)模型，研究了多重邊復(fù)雜網(wǎng)絡(luò)的局部和全局的自適應(yīng)同步.例如N個相同節(jié)點4重邊的復(fù)雜網(wǎng)絡(luò)

式中 1≤i≤N ，xi=(xi1,xi2,…,xin)T∈Rn為節(jié)點 i的狀態(tài)變量,x˙i為節(jié)點動力學(xué)方程，B∈Rn×n是一個常數(shù)矩陣，g:Ω×R+→Rn是一個平滑的非線性函數(shù).H0,H1,H2,H3∈Rn×n為各個節(jié)點狀態(tài)變量之間的 內(nèi) 部 耦 合 函 數(shù).耦 合 矩 陣Al=)N×N∈Rn×n(l=0,1,2,3)表示第l個子網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu),滿足耗散耦合條件，其中的具體定義如下:若第l個子網(wǎng)絡(luò)中的節(jié)點i和節(jié)點j(i≠j)之間有連邊且連接數(shù)為 q(q≤4),則=q;若兩點之間無連接,則==0(i≠j).這 里 矩 陣 Al的 對 角 元 定 義 為(i=1,2,3,4;l=0,1,2,3,4).τ,1τ2,τ3為拆分網(wǎng)絡(luò)所需而引入的時滯.vi∈Rn是控制輸入項,其目的是使式(1)達(dá)到同步,且滿足

式中 s是系統(tǒng)節(jié)點方程x˙i=f(xi(t))的一個達(dá)到同步的解.

定義1令xi(t;t0,X0)(1≤i≤N)為式(1)的解, X0=,,…,),g:Ω×R+→Rn和(1≤i≤N)是連續(xù)可微的,其中[Ω?Rn].若存在一個非空子集,并且∈Λ(1≤i≤N),則對所有的t≥t0和1≤i≤N,xi(t;t0,X0)∈Ω都成立,且有

式中 s(t;t0,x0)是系統(tǒng)節(jié)點方程x˙i=f(xi(t))的一個達(dá)到同步的解,且.由此可知,式(1)所描述的系統(tǒng)就達(dá)到同步,并且被稱為動態(tài)網(wǎng)絡(luò)系統(tǒng)的同步域.

定義誤差變量為

控制器vi的目標(biāo)是引導(dǎo)控制式(1)趨于同步,即lim=0(1≤i≤N).由于s˙=f(s,t),令式(1)減去s˙=f(s,t)，則誤差系統(tǒng)為

式中

對于線性耦合H0,H1,H2,H3,容易得到結(jié)論:存在一個非負(fù)常數(shù) λij,γij,ψij,ηij(1≤i,j≤N),對于所有的1≤i≤N，滿足

假設(shè)1假設(shè)存在一個非負(fù)的常數(shù)α滿足,其中 J(t)是 g(s,t)的Jacobi矩陣.

引 理對 于 任 意 的 x,y∈Rn,μ＞0,有成立.

假設(shè)2假設(shè)存在一個非負(fù)的常量 μ滿足

定理若假設(shè)1和假設(shè)2成立,選取控制器為

式中

式中 ki為正常數(shù).那么式(1)的一個同步解s(t)在自適應(yīng)控制器式(4)下達(dá)到全局漸近穩(wěn)定.

證明 構(gòu)造Lyapunov穩(wěn)定性方程為

式中 β,μ,λij,γij,ψij和 ωij(1≤i,j≤N)是非負(fù)的常數(shù),可以選取合適的d?i(1≤i≤N)，使2Λ+Υ+Ψ+ W+diag(2β+2μ+2-2d?1,…,2β+2μ+2-2d?N)為一個 負(fù) 定 矩 陣,當(dāng) t→∞ 時,誤 差 變 量.于是式(1)所描述的復(fù)雜網(wǎng)絡(luò)方程的一個同步解s(t)在自適應(yīng)控制器式(4)和式(5)的條件下達(dá)到全局漸近穩(wěn)定.證畢.

3 一種新的城市公交網(wǎng)絡(luò)模型

3.1 新的城市公交網(wǎng)絡(luò)模型的建立

城市公交網(wǎng)絡(luò)由城市公交?？空军c和公交線路兩個基本要素構(gòu)成,城市公交線路把城市公交?？空军c連接起來,而城市公交線路由若干沿線公交?？空军c組成.從城市公交網(wǎng)絡(luò)中的公交站點、公交線路和公交換乘的角度來看,可以構(gòu)建三種城市公交網(wǎng)絡(luò)模型：

（1）公交車站網(wǎng)絡(luò),采用space L建模方法,將交通站點視為節(jié)點,若兩個站點是某一交通線路上相鄰的,那么它們就有連邊;

（2）公交換乘網(wǎng)絡(luò),采用space P建模方法,將交通站點視為節(jié)點,若兩個站點有直達(dá)交通路線,那么它們就有連邊;

（3）公交線路網(wǎng)絡(luò),采用space R建模方法,該網(wǎng)絡(luò)以公交線路為節(jié)點,若兩條公交線路有相同的?？空军c,則在兩個節(jié)點之間連邊.

本文在上述三種公交網(wǎng)絡(luò)建模方法的基礎(chǔ)上,采用新的建模方法(即space ML方法)建立一種新的復(fù)雜公交網(wǎng)絡(luò)模型,稱為公交線路多重邊網(wǎng)絡(luò)模型.這種建模方法以公交線路為節(jié)點,若兩條公交線路之間有k個相同的?？空军c,則在兩個節(jié)點之間有k條連邊.以蘭州市1路、15路、331路公交車為例，1路和15路有兩個相同的站點,1路和33路有三個相同的站點，15路和33路有四個相同的站點,于是三條公交線路的拓?fù)浣Y(jié)構(gòu)圖如圖1所示.

圖1 多重邊融合復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)圖Fig.1 The topology map of complex dynamical networks with multi-links

3.2 新的多重邊城市公交網(wǎng)絡(luò)的拆分

對于圖1所示的三節(jié)點多重邊的城市公交網(wǎng)絡(luò)模型，引入時滯，按邊的不同將其拆分為四個不同的子網(wǎng)絡(luò).

令任兩條公交線路間相同站點的第一個站點對應(yīng)的邊和三個節(jié)點組成的網(wǎng)絡(luò)為零子網(wǎng)絡(luò),即τ0=0的網(wǎng)絡(luò).則第二、三、四個相同站點對應(yīng)的邊和三個節(jié)點組成的網(wǎng)絡(luò)分別具有時滯τ1,τ2,τ3.其拆分示意圖如圖2所示.

圖2 多重邊復(fù)雜網(wǎng)絡(luò)的拆分示意圖Fig.2 The split of complex networks with multi-links

4 多重邊城市公交網(wǎng)絡(luò)的同步分析

高自友等在文獻(xiàn)[13]中得到城市公交乘客流量滿足非線性性質(zhì).通過對整個公交網(wǎng)絡(luò)的研究分析，可得整個公交線路網(wǎng)絡(luò)模型具有BA無標(biāo)度網(wǎng)絡(luò)的特性.假設(shè)這三條公交線路客流量變化量滿足非線性Chen系統(tǒng),即節(jié)點動力學(xué)方程為

對于圖2所描述的公交線路網(wǎng)

因為可知假設(shè)2成立.根據(jù)定理1,控制器式(7)使式(1)的同步解s(t)達(dá)到全局漸近穩(wěn)定.

5 數(shù)值仿真

本文研究的是城市公交路線之間的控制強度(人為調(diào)度)和公交線路的優(yōu)化，即多重邊復(fù)雜網(wǎng)絡(luò)子網(wǎng)絡(luò)的耦合強度ε和邊的增減對公交網(wǎng)絡(luò)模型同步效果的影響.城市公交網(wǎng)絡(luò)系統(tǒng)的同步效應(yīng)是指運營車輛和出行乘客達(dá)到一種動態(tài)平衡，即公交車輛的一次運營時間最接近于預(yù)先設(shè)定的時間（堵車時間最短），同時乘客在公交車站滯留時間最 短.假 設(shè) H0=H1=H2=H3=diag{ } 1,1,1,1.令ki=1,di1(0)=(1,2,0.3),di2(0)=(-1,-1,2),di3(0)=(2, 1,3),xi1(0)=(1,0.2,0.3),xi2(0)=(-1,-1,0.5),xi3(0)= (2,1,0.3),s(0)=(0,0,0),i=1,2,3.當(dāng)τ0=τ1=τ2=τ3= 1.5,ε0=ε1=ε2=ε3=0.8時，誤差的仿真圖如圖3

所示.當(dāng)ε0=ε1=ε2=ε3=0.3時,誤差的仿真圖如圖4所示.由圖3、圖4可知,圖4的三組圖的同步時間均比圖3延長3-8個時間單位.由此可知，耦合強度的大小對復(fù)雜網(wǎng)絡(luò)同步是有一定影響的,這說明當(dāng)加大對公交線路之間的控制力度,如適當(dāng)?shù)卣{(diào)整發(fā)車時間和頻次，會對公交線路間的平衡有很好的維護(hù)作用,控制力度越大,整個公交網(wǎng)絡(luò)中的滯留人數(shù)就越少，公交網(wǎng)絡(luò)就越快趨于穩(wěn)定.

圖3 復(fù)雜網(wǎng)絡(luò)的誤差收斂曲線 (a)誤差ei1;(b)誤差ei2;(c)誤差ei3Fig.3 Synchronization errors for complex network(a)errorsei1(b)errorsei2(c)errorsei3

圖4 復(fù)雜網(wǎng)絡(luò)的誤差收斂曲線 (a)誤差ei1;(b)誤差ei2;(c)誤差ei3Fig.4 Synchronization errors for complex network(a)errorsei1(b)errorsei2(c)errorsei3

對于圖2所示的復(fù)雜公交網(wǎng)絡(luò)及其拆分,如果在1路和33路公交線間增加一個相同節(jié)點，在1路和15路公交線間增加兩個相同節(jié)點,于是形成一個新的復(fù)雜公交網(wǎng)絡(luò)模型.在拆分方法不變的情況下，新的復(fù)雜公交網(wǎng)絡(luò)可以拆分如圖5所示.

圖5 多重邊復(fù)雜網(wǎng)絡(luò)的拆分示意圖Fig.5 The split of complex networks with multi-links

通過數(shù)值仿真,誤差的仿真圖如圖6所示.圖6的三組圖的同步時間均比圖3縮短了3-6個時間單位，由此可知，當(dāng)公交線路多重邊網(wǎng)絡(luò)的邊越多時，系統(tǒng)的同步時間越短.這說明公交線路間的相同站點越多時，乘客可換乘的車輛越多，滯留時間越短，同時整個公交線路網(wǎng)絡(luò)就越快趨于穩(wěn)定.

圖6 復(fù)雜網(wǎng)絡(luò)的誤差收斂曲線 (a)誤差 ei1;(b)誤差 ei2;(c)誤差 ei3Fig.6 Synchronization errors for complex network(a)errorsei1(b)errorsei2(c)errorsei3

6 研究結(jié)論

首先建立了一種新的城市公交線路多重邊網(wǎng)絡(luò)模型，這種模型以公交線路為節(jié)點，兩條線路間有幾個相同站點,則兩節(jié)點間就有幾條邊.根據(jù)網(wǎng)絡(luò)拆分的思想，將上述多重邊網(wǎng)絡(luò)拆分為多個子網(wǎng)絡(luò)，進(jìn)而研究了多重邊復(fù)雜公交網(wǎng)絡(luò)的全局同步.由同步的結(jié)論可知,對公交車輛的人為控制，如調(diào)整公交車的發(fā)車時間與間隔，及時排除道路故障，都會影響到整個公交網(wǎng)絡(luò)的平衡.又如合理的優(yōu)化公交線路,適當(dāng)?shù)卦黾庸痪€路間的相同站點，會使乘客等車的時間適當(dāng)減少，公交網(wǎng)絡(luò)更快趨于穩(wěn)定.這些結(jié)論都能為公交網(wǎng)絡(luò)的整體協(xié)調(diào)調(diào)度提供理論依據(jù).

[1]陳艷,杜園,吳薇，等.節(jié)點狀態(tài)不同的兩個耦合網(wǎng)絡(luò)的同步[J].應(yīng)用數(shù)學(xué)與計算科學(xué)學(xué)報,2009,23(2):72-78. [CHEN Y,DU Y,WU W,et al.Synchronization of two coupled networks with differrent node inctions[J].Com?munication on Applied Mathematics and Computa?tion.2009,23(2):72-78.]

[2]Li P,Zhang Y.Global synchronization of a class of de?layed complex network[J].Chaos,Solitons&Fractals, 2006,30(4):903-908.

[3]Zou Y L,Chen G R.Pinning－controlled synchroniza?tion of complex networks with bounded or unbounded synchronization regions[J].Chinese Physics B,2009,18 (8):3337-3346.

[4]Liu T,Zhao J,Hill D J.Synchronization of complex de?layed dynamical networks with nonlinearly coupled nodes[J].Chaos Solitons&Fractals,2009,40(3):1506-1519.

[5]高洋,李麗香,彭海朋.多重邊融合復(fù)雜動態(tài)網(wǎng)絡(luò)的自適應(yīng)同步[J],物理學(xué)報,2008,57(4):2081-2091.[GAO Y,LI L X,PENG H P.Adaptive synchronization in unit?ed complex dynamical network with multi-links[J].Acta Physica Sinica,2008,57(4):2081-2091.]

[6]羅群,高雅,齊雅楠.融合復(fù)雜動態(tài)網(wǎng)絡(luò)的模型參考自適應(yīng)同步研究[J],物理學(xué)報,2009,58(10):6810-6817. [LUO Q,GAO Y,QI Y N.Model reference adaptive syn?chronization in integration complex dynamical networks [J].Acta Physica Sinica,2009,58(10):6809-6817.]

[7]趙永清,江明輝.混合變時滯二重邊復(fù)雜網(wǎng)絡(luò)自適應(yīng)同步反饋控制[J].山東大學(xué)學(xué)報,2010,40(3):61-68. [ZHAO Y Q，JIANG M H.Adaptive synchronous feed?back control of mixed time-varying delayed and doublelinked complex networks[J].Journal of Shandong Univer?sity,2010,40(3):61-68.]

[8]何迪,嚴(yán)余松,郭守儆,等.基于矩陣分析的公共交通網(wǎng)絡(luò)最優(yōu)路徑算法[J].西南交通大學(xué)學(xué)報，2007，42(3): 315-319.[HE D,YAN Y S,GUO S J,et al.Optimal rout?ing algorithm for public traffic network based on matrix analysis[J].Journal of Southwest Jiaotong University, 2007,42(3):315-319.]

[9]孫鋒,王殿海,馬東方.直線型公交停靠站通行能力計算方法[J].西南交通大學(xué)學(xué)報，2013，48(3):1-7.[SUN F,WANG D H,MA D F.Method for computing on-Line bus stop capacity[J].Journal of Southwest Jiaotong Uni?versity,2013,48(3):1-7.]

[10]王波,王萬良,楊旭華.一種基于加權(quán)復(fù)雜網(wǎng)絡(luò)的最優(yōu)公交換乘算法[J].武漢理工大學(xué)學(xué)報,2008,32(6): 1113-1116.[WANG B,WANG W L,Yang X H.An op?timal bus transport transfer algorithm based on weighted complex networks[J].Journal of Wuhan University of Technology,2008,32(6):1113-1116.]

[11]趙玲，鄧敏,王佳璆,等.基于復(fù)雜網(wǎng)絡(luò)理論的城市路網(wǎng)結(jié)構(gòu)特性分析[J].地理與地理信息科學(xué),2010,26(6): 11-15.[ZHAO L,DENG M,WANG J Q,et al.Structural property analysis of urban street networks based on com?plex network theory[J].Geography and Geo-Information Science,2010,26(5):11-15.]

[12]惠偉,王紅.復(fù)雜網(wǎng)絡(luò)在城市公交網(wǎng)絡(luò)中的實證分析[J].計算機技術(shù)與發(fā)展，2008，18(11):217-222.[HUI W, WANG H.Empirical analysis of complex networks in public traffic networks[J].Computer Technology and De?velopment,2008,18(11):217-222.]

[13]吳建軍,高自友,孫會君,等.城市交通系統(tǒng)復(fù)雜性-復(fù)雜網(wǎng)絡(luò)方法及其應(yīng)用[M].北京:科學(xué)出版社,2010.[WU J J,GAO Z Y,SUN H J,et al.Urban traffic system com?plexity-The method of complex networks and its appli?cation[M].Beijing:Science Press,2010.]

Public Traffic Network Modeling with Multi-links

AN Xin-leia,b,LI Yin-zhenb,MAChang-xib
(a.School of Mathematics and Physics；b.School of Traffic and Transportation, Lanzhou Jiaotong University,Lanzhou 730070,China)

This paper develops a new public traffic network model with multi-links based on the existing public traffic network model.The model takes bus lines as the network nodes,and the same bus stops as the network links.Based on the concept of network split,the paper divides the complex public traffic network with multi-links into four different sub-networks for three public bus routes with time-delay.Then taking“Chen system”as the network node,the paper studies the globalsynchronization of the four-links complex network.Changing control degrees and the same bus stops number of some public transport vehicles,the paper analyses the impact of bus dispatching and bus lines optimization to the public traffic network balance. At last,numerical simulation is conducted by Matlab.This research provides theory basis for the reasonable dispatch of urban public traffic network.

urban traffic;complex networks with multi-links;network split;complex network synchronization;public traffic network model

1009-6744（2014）03-0154-08

U121;O231.5

A

2013-09-03

2013-11-27錄用日期：2014-01-23

國家自然科學(xué)基金項目（61164003）;教育部重點項目（212180）.

安新磊(1983-),男,河南開封人,講師,博士生.*通訊作者：anxin1983@163.com