復(fù)雜網(wǎng)絡(luò)同步理論在公交調(diào)度中的應(yīng)用

劉興偉, 張仲榮, 張建剛

(蘭州交通大學(xué) 數(shù)理與軟件工程學(xué)院,蘭州 730070)

復(fù)雜網(wǎng)絡(luò)同步理論在公交調(diào)度中的應(yīng)用

劉興偉, 張仲榮, 張建剛

(蘭州交通大學(xué) 數(shù)理與軟件工程學(xué)院,蘭州 730070)

針對(duì)傳統(tǒng)方法優(yōu)化公交調(diào)度難以保證運(yùn)營(yíng)效率達(dá)到最優(yōu)的實(shí)際情況,基于城市空間結(jié)構(gòu)與交通系統(tǒng)的內(nèi)在運(yùn)行機(jī)制,構(gòu)造了城市公交網(wǎng)絡(luò)模型,利用 N個(gè)等同節(jié)點(diǎn)的時(shí)滯非線性耦合狀態(tài)方程的同步理論,使公交調(diào)度網(wǎng)絡(luò)系統(tǒng)達(dá)到漸進(jìn)穩(wěn)定,即各線路乘客達(dá)到一種均衡狀態(tài)。以蘭州市公交系統(tǒng)的部分線路為例,驗(yàn)證了該模型及方法的有效性。

公交調(diào)度;時(shí)滯;復(fù)雜網(wǎng)絡(luò)同步;城市公共交通網(wǎng)絡(luò)

Abstract:Aimed at seeking an alternative to the conventionalwaywhich fails to ensure bus schedulingwith opt imal operational efficiency,this paper dealswith the development of the urban public transport scheduling network model,based on the urban spatial structure and the transport system of internal operatingmechani sms.The paper introduces the use of the nonlinear simultaneous equation of the coupling state by the same nodeNto realize the asymptotic stability of the entire public transport scheduling ne twork,namely an equilibrium state available for the passengersof the whole bus lines.The paper highlights the part of bus systems which verifies the optional routes of the traveling and the effectiveness of transfer in Lanzhou.

Key words:public transit scheduling;t ime delay;complex ne twork synchronization;urban public traffic network

0 引 言

復(fù)雜系統(tǒng)與復(fù)雜性研究已成為 21世紀(jì)的核心科學(xué)問題之一,復(fù)雜網(wǎng)絡(luò)是復(fù)雜系統(tǒng)的高度抽象[1]。在復(fù)雜網(wǎng)絡(luò)的同步研究中,汪小帆和陳關(guān)榮等[2-3]提出了一個(gè)簡(jiǎn)單的動(dòng)力學(xué)網(wǎng)絡(luò)模型,還給出了無界區(qū)域的同步條件,引起了人們的廣泛關(guān)注。該模型中各節(jié)點(diǎn)相互線性耦合且耦合強(qiáng)度一致,很多學(xué)者對(duì)其做了進(jìn)一步地修改和擴(kuò)展,取得了大量成果[4-5]。

復(fù)雜網(wǎng)絡(luò)理論在交通網(wǎng)絡(luò)中的應(yīng)用也有了很大發(fā)展,高自友等[6]研究了城市公交網(wǎng)絡(luò)的無標(biāo)度特性及度分布指數(shù),以北京市公交網(wǎng)絡(luò)為例完成了實(shí)證分析,并提出了一些今后關(guān)于城市交通網(wǎng)絡(luò)復(fù)雜性問題的研究方向[7]。目前,公交調(diào)度的研究多集中在車輛的靜態(tài)調(diào)度分析,研究方法主要有數(shù)學(xué)解析法、概率方法、經(jīng)驗(yàn)?zāi)Ｐ?、模擬仿真和運(yùn)籌學(xué)等。隨著城市規(guī)模的不斷擴(kuò)大,這些傳統(tǒng)方法遇到了很大的困難而且得不到精確的解。筆者利用時(shí)滯復(fù)雜網(wǎng)絡(luò)的同步理論對(duì)城市常規(guī)公交進(jìn)行調(diào)度,以期達(dá)到更優(yōu)的調(diào)度效果。

1 城市公交網(wǎng)絡(luò)模型構(gòu)造

城市公交網(wǎng)絡(luò)由公交站點(diǎn)和公交線路兩個(gè)基本要素組成,公交線路由若干沿線公交站點(diǎn)連接而成。在實(shí)際公交站點(diǎn)中根據(jù)線路的拓?fù)浣Y(jié)構(gòu)可以分為環(huán)形線路和直線延伸形線路兩種。環(huán)形線路的起始與公交站點(diǎn)是同一個(gè)站點(diǎn),一般位于城市的繁華地段,便于換乘;而直線形線路呈直線狀,延伸到城市的各個(gè)角度。從城市公交網(wǎng)絡(luò)的公交站點(diǎn)、公交線路和公交換乘的角度考慮,可以構(gòu)建三種城市公交網(wǎng)絡(luò)模型。

1.1 公交站點(diǎn)網(wǎng)絡(luò)模型

公交站點(diǎn)網(wǎng)絡(luò)模型是以現(xiàn)實(shí)的城市公交線路中公交站點(diǎn)之間實(shí)際拓?fù)淠Ｐ蜆?gòu)建的,該模型中公交站點(diǎn)是網(wǎng)絡(luò)模型的頂點(diǎn),如果有公交線路 L連接 A點(diǎn)和 B點(diǎn),且 L沿線的 A、B點(diǎn)中不存在其他的公交站點(diǎn),則A和B點(diǎn)間有一條邊。該模型中頂點(diǎn)的度是通過這一頂點(diǎn)的公交線路的數(shù)目,頂點(diǎn)度越大,該頂點(diǎn)越重要,即所謂的樞紐點(diǎn)和換乘站點(diǎn)。

1.2 公交換乘網(wǎng)絡(luò)模型

評(píng)價(jià)公交網(wǎng)絡(luò)的可達(dá)性的一個(gè)重要指標(biāo)就是換乘次數(shù)。在公交換乘模型中,公交站點(diǎn)是網(wǎng)絡(luò)的頂點(diǎn),按照公交線路的走向把線路沿線的站點(diǎn)連接起來。假設(shè)在同一條線路上,所有公交站點(diǎn)是全連通的。網(wǎng)絡(luò)中任一一個(gè)站點(diǎn)換乘次數(shù)為其之間距離減一。

1.3 公交線路網(wǎng)絡(luò)模型

公交線路網(wǎng)絡(luò)模型是以公交線路為頂點(diǎn),如果兩條公交線路之間有部分相同的站點(diǎn),則這兩個(gè)頂點(diǎn)之間有一條邊連接,如果有多條線路在這兩個(gè)站點(diǎn)之間相交或部分重合,則這兩個(gè)頂點(diǎn)之間的權(quán)值表示重合線路的數(shù)目。網(wǎng)絡(luò)中權(quán)值大的邊,在實(shí)際網(wǎng)絡(luò)中就是干線和市區(qū)的繁華路段。兩點(diǎn)中的O-D流大,就要設(shè)置多條公交線路通過。文中利用常規(guī)公交線路網(wǎng)絡(luò)模型建立了時(shí)滯常規(guī)公交線路調(diào)度網(wǎng)絡(luò)模型。

2 時(shí)滯公交網(wǎng)絡(luò)模型及同步判據(jù)

在城市公交系統(tǒng)中,假設(shè)該城市有 N條公交線路且不考慮每條線路運(yùn)行中的交通事故、堵車及車自身等問題。將這N條公交線路抽象成網(wǎng)絡(luò)中的N個(gè)點(diǎn),這N個(gè)點(diǎn)組成一個(gè)統(tǒng)一的網(wǎng)絡(luò)系統(tǒng)。通過對(duì)公交網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的分析可得公交網(wǎng)絡(luò)符合小世界網(wǎng)絡(luò)的特性[8],由 N個(gè)等同節(jié)點(diǎn)非線性耦合時(shí)滯復(fù)雜動(dòng)態(tài)網(wǎng)絡(luò)模型動(dòng)力學(xué)方程[1]為

為了判斷整個(gè)時(shí)滯公交網(wǎng)絡(luò)模型的同步下面介紹一些引理及同步定理[9]。

引理 1式 (1)中定義的不可約分耦合矩陣A=(aij)n×n∈Rn×n,存在一個(gè)酉矩陣Φ =(φ1,φ2,…,φN),使得 ATφk=λkφk,k=1,2,…,N成立。式中:λi(i=1,2,…,N)為矩陣 A的特征值。

引理 2假設(shè) H、E和 F為適當(dāng)維數(shù)的實(shí)矩陣,且滿足 FTF≤I,則對(duì)任意標(biāo)量ε>0,有 H FE+ETFTHT<εHHT+ε-1ETE。如果當(dāng) t→∞時(shí),有

定理 1考慮耦合時(shí)滯動(dòng)態(tài)網(wǎng)絡(luò)系統(tǒng) (1),設(shè)0=λ1>λ2≥λ3≥…≥λN,為耦合矩陣 A的特征值。如果一下N個(gè) n維線性時(shí)滯延遲系統(tǒng)關(guān)于 0解是漸進(jìn)穩(wěn)定的 :η·(t)=(F+ΔF)η (t)+cλkΓ η(tτ),k=1,2,…,N,那么同步狀態(tài) (2)是漸進(jìn)穩(wěn)定的。

證明 這里令

由引理 1可知,存在一個(gè)非奇異矩陣Φ =(φ1,φ2,…,φN)∈Rn×n,使得 ATΦ =Φ Λ,其中Λ =diag(λ1,λ2,…,λN)。因此,使用非奇異轉(zhuǎn)換矩陣 e(t)Φ =η(t)=(η1(t),η2(t), …,ηN(t)) ∈Rn×N,結(jié)合式(4)有

至此,把同步狀態(tài) (2)的穩(wěn)定問題轉(zhuǎn)化為了式 (5)中N個(gè)系統(tǒng)的穩(wěn)定問題,也就是當(dāng)式 (5)是漸進(jìn)穩(wěn)定的,那么 e(t)將漸進(jìn)趨于零,即同步狀態(tài) (2)是漸進(jìn)穩(wěn)定的。

3 實(shí)證分析

截至 2010年 6月蘭州市共有公交線路 104條,423個(gè)?？空军c(diǎn),2 293條連邊。數(shù)據(jù)選取說明:假設(shè)在某條線路中,A點(diǎn)可以通達(dá)B點(diǎn),則B點(diǎn)可以通達(dá)A點(diǎn)。假設(shè)網(wǎng)絡(luò)中所有公交線路的服務(wù)開始時(shí)間和結(jié)束時(shí)間一致而且票價(jià)一樣?，F(xiàn)實(shí)中有很多的站點(diǎn)名稱相近,在構(gòu)建的模型中站點(diǎn)名稱不一樣,即視為不同站點(diǎn),只要站點(diǎn)名稱一致,都視為同一個(gè)站點(diǎn),不論站點(diǎn)距離相近與否。

以蘭州市西關(guān)什字公交網(wǎng)絡(luò)為例進(jìn)行實(shí)證分析。經(jīng)過西關(guān)什字的公交線路有 45條,取其中的140、103、138、82四條起始點(diǎn)都在西關(guān)什字的線路為研究對(duì)象。文中將運(yùn)用具有時(shí)滯的超混沌的Chen系統(tǒng)和 Lü系統(tǒng)對(duì)其研究。

這四條公交線路的模型為:

將方程 (6)作為驅(qū)動(dòng)系統(tǒng),方程 (7)作為響應(yīng)系統(tǒng),可以得到時(shí)間延遲的誤差系統(tǒng):

取誤差系統(tǒng)中的常數(shù) k1=1,k2=2,k3=3,k4=4,d1=d2=d3=d4=1,當(dāng)該系統(tǒng)的耦合強(qiáng)度 c為 0.5,時(shí)滯τ分別為 5和 10時(shí)的同步誤差曲線如圖 1所示。

圖 1 同步誤差曲線Fig.1 Synchron ization error curves

由圖 1可知,當(dāng)時(shí)滯τ為 5時(shí),整個(gè)系統(tǒng)達(dá)到同步速度比τ為 10時(shí)快,也就是當(dāng)調(diào)度時(shí)間為 5 min時(shí)乘客的滯留比較少。

4 結(jié)束語

筆者在整個(gè)公交網(wǎng)絡(luò)系統(tǒng)的基礎(chǔ)上提出了一種新的公交調(diào)度方法,即運(yùn)用含有時(shí)滯的復(fù)雜網(wǎng)絡(luò)的同步理論對(duì)城市常規(guī)公交進(jìn)行調(diào)度,構(gòu)造了城市公交調(diào)度網(wǎng)絡(luò)模型。選取非線性的具有時(shí)滯的超混沌的 Chen系統(tǒng)和Lü系統(tǒng)對(duì)以蘭州市西關(guān)什字為始發(fā)站的四條公交線路進(jìn)行調(diào)度。實(shí)證分析證明該方法正確有效,具有廣泛的應(yīng)用前景。

[1] 周 濤,柏文潔,汪秉宏,等.復(fù)雜網(wǎng)絡(luò)研究概述[J].物理,2005,34(1):31-36.

[2] WANG X F,CHEN G R.Synchronization in small-world dynamical networks[J].Int.J of Bifurcation and Chaos,2002,12(1):187-192.

[3] WANG X F,CHEN G R.Synchronization in scale-free dynamical networks:Robustness and fragility[J].IEEE Transon Circuit System,2002,49(1):54-62.

[4] L IC G,CHEN G R.Synchronization in general complex dynamical networks with coupling delays[J].Physical A,2004,343(15):263-278.

[5] ZHOU J,CHEN T.Synchronization in general complex delayed dynamical networks[J].IEEE Transon Circuit System,2006,53(3):733-744.

[6] 高自友,吳建軍,毛保華,等.交通運(yùn)輸網(wǎng)絡(luò)復(fù)雜性及其相關(guān)問題的研究[J].交通運(yùn)輸系統(tǒng)工程與信息,2005,5(2):79-84.

[7] 高自友,趙小梅,黃海軍,等.復(fù)雜網(wǎng)絡(luò)理論與城市交通復(fù)雜性問題的相關(guān)研究[J].交通運(yùn)輸系統(tǒng)工程與信息,2006,6(3):41-47.

[8] 張 晨,張 寧.上海市公交網(wǎng)絡(luò)拓?fù)湫再|(zhì)研究[J].上海理工大學(xué)學(xué)報(bào),2006,28(5):489-494.

[9] WANGQ Y,CHEN G R,LU Q S,et al.Novel criteria of synchronization stability in complex networks with coupling delays[J].PhysicalA,2007,378(2):527-536.

(編輯 王 冬)

Application of complex networks synchronization theory in public transit scheduling

L IU X ingwei, ZHANG Zhongrong, ZHANG Jian’gang
(School ofMathematics,Physics&Software Engineering,Lanzhou JiaotongUniversity,Lanzhou 730070,China)

O231.2;U491.1

A

1671-0118(2010)05-0376-03

2010-07-02

甘肅省自然科學(xué)基金項(xiàng)目(3ZS-042-B25-049);甘肅省省屬高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)項(xiàng)目(620004)

劉興偉 (1981-),男,河南省開封人,碩士,研究方向:復(fù)雜網(wǎng)絡(luò)理論在交通運(yùn)輸中的應(yīng)用,E-mail:liuxingwei0001@126.com。