基于小世界模型的交通網(wǎng)絡(luò)擁堵狀態(tài)研究

趙 軍

(江蘇食品職業(yè)技術(shù)學(xué)院信息工程系,江蘇 淮安 223003)

基于小世界模型的交通網(wǎng)絡(luò)擁堵狀態(tài)研究

趙 軍

(江蘇食品職業(yè)技術(shù)學(xué)院信息工程系,江蘇 淮安 223003)

在對海量數(shù)據(jù)進(jìn)行分析和利用的同時，數(shù)據(jù)挖掘作為一種首選的工具已經(jīng)普遍應(yīng)用到各個領(lǐng)域中。為了解決交通網(wǎng)絡(luò)中車輛擁堵的狀態(tài)，在利用復(fù)雜網(wǎng)絡(luò)中的小世界模型建立交通網(wǎng)絡(luò)模型時，借助數(shù)據(jù)挖掘中的譜聚類方法對交通網(wǎng)絡(luò)的擁堵狀態(tài)進(jìn)行分析，通過計(jì)算道路的平均擁堵時間控制交通燈的放行時間，使得整個交通網(wǎng)絡(luò)不出現(xiàn)異常擁堵情況。采用NetLogo 5.0.3作為試驗(yàn)平臺，對模擬交通網(wǎng)絡(luò)進(jìn)行分析，成功實(shí)現(xiàn)對交通流的調(diào)節(jié)，避免了長時間擁堵情況的發(fā)生。

交通網(wǎng)絡(luò) 復(fù)雜網(wǎng)絡(luò) 數(shù)據(jù)挖掘 小世界模型 擁堵 NetLogo

0 引言

隨著城市交通在社會經(jīng)濟(jì)發(fā)展過程中的作用越來越重要，交通帶來的城市擁堵問題也日益突出。為了更好地改善城市交通的整體狀況，研究學(xué)者從多個方面對交通問題進(jìn)行分析，其中一個非常重要的方向是基于數(shù)據(jù)挖掘和系統(tǒng)理論的復(fù)雜網(wǎng)絡(luò)進(jìn)行深入分析。

目前，有關(guān)車輛的數(shù)量增加與交通道路擴(kuò)張的相互影響的研究，主要從以下4個方面展開：①城市交通擁堵的新城以及車輛行為在道路上的擴(kuò)散規(guī)律；②道路的規(guī)劃與車輛行為需求的影響；③交通控制與道路、車輛的分布情況之間的關(guān)系；④緩解城市擁堵的非經(jīng)驗(yàn)型傳播機(jī)制。

通過對以上幾個方面的深入研究，越來越多的研究將車輛行為的復(fù)雜性與交通網(wǎng)絡(luò)的復(fù)雜性相結(jié)合，利用動力學(xué)方法研究城市交通網(wǎng)絡(luò)的擁堵原理、機(jī)制和解決方法。從復(fù)雜網(wǎng)絡(luò)的研究可以看出，利用相互關(guān)聯(lián)節(jié)點(diǎn)以及節(jié)點(diǎn)之間的關(guān)系,可以對互聯(lián)網(wǎng)、蛋白質(zhì)網(wǎng)、流行病網(wǎng)以及交通網(wǎng)等多種現(xiàn)實(shí)問題進(jìn)行研究，設(shè)計(jì)的領(lǐng)域也包括諸如數(shù)學(xué)、生物學(xué)、物理學(xué)、社會科學(xué)、醫(yī)學(xué)等。隨著研究的不斷深入，越來越多的問題都可以借助復(fù)雜網(wǎng)絡(luò)的模型進(jìn)行仿真與分析，成為一門交叉能力較強(qiáng)的學(xué)科。

同時，由于復(fù)雜網(wǎng)絡(luò)中的規(guī)律性往往是通過對大量數(shù)據(jù)的分析后得到的，并且有的規(guī)律性還需要數(shù)據(jù)去驗(yàn)證，因此，借助數(shù)據(jù)挖掘技術(shù)可以對利用復(fù)雜網(wǎng)絡(luò)研究的模型進(jìn)行驗(yàn)證。通過這種結(jié)合的方法,可以在一定程度上提高復(fù)雜網(wǎng)絡(luò)模型的可信度，更加有利于模型的推廣。

1 交通網(wǎng)絡(luò)復(fù)雜網(wǎng)絡(luò)模型

在模擬交通狀況的復(fù)雜網(wǎng)絡(luò)模型中，常用小世界模型進(jìn)行分析。小世界模型通過分析臨近節(jié)點(diǎn)之間的關(guān)聯(lián)性，構(gòu)造了具有一定拓?fù)浣Y(jié)構(gòu)的隨機(jī)網(wǎng)絡(luò)，網(wǎng)絡(luò)中的臨近節(jié)點(diǎn)通過某一小概率的幾率相互連接，形成局部無規(guī)律性而整體存在顯著規(guī)律的網(wǎng)絡(luò)。這種模型可以用于描述交通網(wǎng)絡(luò)中的車輛行為，即車輛從一個節(jié)點(diǎn)(通常用路口表示交通網(wǎng)絡(luò)中的節(jié)點(diǎn))出發(fā)達(dá)到另外一個節(jié)點(diǎn)的可能性。

利用這種模型描述的交通網(wǎng)絡(luò)具有以下特點(diǎn)。

① 將交通網(wǎng)絡(luò)的道路復(fù)雜性描述為節(jié)點(diǎn)之間的鏈接關(guān)系，利用節(jié)點(diǎn)的高聚類性可以對交通網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)進(jìn)行可靠性分析，有助于分析交通網(wǎng)絡(luò)在各種交通流的影響下是否具有穩(wěn)定性。

② 小世界網(wǎng)絡(luò)的平均最小距離比較容易分析，可以使得在模擬交通網(wǎng)時保持較好的動態(tài)性和偏好依附性。這一點(diǎn)也比較接近車輛在交通網(wǎng)絡(luò)中的實(shí)際運(yùn)行機(jī)制。

同時，為了描述交通網(wǎng)絡(luò)的動力學(xué)性質(zhì)，很多學(xué)者也對交通網(wǎng)絡(luò)的動力學(xué)特征進(jìn)行了大量研究。其中，最具代表性的是陳克寒[1]對交通網(wǎng)絡(luò)中的節(jié)點(diǎn)平均度進(jìn)行分析，得到了交通網(wǎng)絡(luò)在無標(biāo)度網(wǎng)絡(luò)情況下比隨機(jī)網(wǎng)絡(luò)更加容易發(fā)生擁堵的結(jié)論。而Luo[2]分析了無標(biāo)度網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)發(fā)生變化時交通網(wǎng)絡(luò)擁堵狀況惡化的規(guī)律性。徐楊[3]通過引入網(wǎng)絡(luò)效率的概念，進(jìn)一步分析了在無標(biāo)度情況下的網(wǎng)絡(luò)全局效率與節(jié)點(diǎn)、邊之間的關(guān)系。Seaton[4]通過對波士頓與維也納兩個城市街道網(wǎng)絡(luò)進(jìn)行網(wǎng)絡(luò)模擬發(fā)現(xiàn)，小世界模型的各種性質(zhì)更加符合交通網(wǎng)絡(luò)的實(shí)際情況，對具有高度自組織性的交通網(wǎng)絡(luò)的無標(biāo)度性進(jìn)行了論證。

在深入研究交通網(wǎng)絡(luò)的動力學(xué)特性時，Ghandour[5]對互聯(lián)網(wǎng)和交通網(wǎng)進(jìn)行了對比性研究，發(fā)現(xiàn)兩者均具有明顯的波動性，并且存在的噪聲也具有周期性。因此,利用帶有噪聲的小世界網(wǎng)絡(luò)進(jìn)行交通網(wǎng)絡(luò)動力學(xué)分析是可行的。后來Arenas[6]對交通網(wǎng)絡(luò)中的信息傳遞機(jī)制進(jìn)行了分析，發(fā)現(xiàn)交通網(wǎng)絡(luò)中的車輛符合信息傳播的規(guī)律性，并且隨著網(wǎng)絡(luò)中節(jié)點(diǎn)最大介數(shù)與交通流的狀態(tài)存在一定的位置關(guān)系。為了對交通網(wǎng)絡(luò)的信息傳遞進(jìn)行動態(tài)分析，李遠(yuǎn)成[7]利用二階鄰居搜索路由方法進(jìn)行交通網(wǎng)中的車輛行為信息傳播，也就是1/f噪聲，從而在交通網(wǎng)絡(luò)的信息傳遞與交通擁堵之間建立了關(guān)系。

2 交通網(wǎng)路動態(tài)模型建立

利用小世界模型對交通網(wǎng)絡(luò)進(jìn)行模擬時，首先要對道路的方向性、路段的長度和車輛滯留時間等因素進(jìn)行定義。因此，交通網(wǎng)絡(luò)符合有向加權(quán)圖的基本特點(diǎn)，可以對該網(wǎng)路模型做如下定義[8]。交通網(wǎng)絡(luò)G(V,E,W)表示由交通路口(節(jié)點(diǎn))V、道路E(邊)以及道路的權(quán)重(邊的權(quán)重)W組成。該網(wǎng)絡(luò)可以使用鄰接矩陣A(aij)表示，其中矩陣元素定義為：

(1)

當(dāng)節(jié)點(diǎn)i≠j時，如果兩個節(jié)點(diǎn)之間存在連接，則元素為1，否則為0。

對網(wǎng)絡(luò)的權(quán)值也同樣可以利用矩陣B(bij)表示，其中矩陣元素定義為：

(2)

當(dāng)節(jié)點(diǎn)i≠j且兩者之間存在邊的情況下，該邊的權(quán)重為wi，否則為+∞。

為了研究車輛在該網(wǎng)絡(luò)中的行為規(guī)律，對車輛的行為選擇進(jìn)行了仿真。文獻(xiàn)[9]利用改進(jìn)的二項(xiàng)分布模擬具有無標(biāo)度特性的網(wǎng)絡(luò)，將節(jié)點(diǎn)的最小度的求解方法轉(zhuǎn)換為小世界網(wǎng)絡(luò)度的分布情況，即：

式中：N為網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)量；p為節(jié)點(diǎn)之間相連接的概率；k為網(wǎng)絡(luò)中的邊的數(shù)量；K為每個節(jié)點(diǎn)的最小度；c為網(wǎng)絡(luò)的簇系數(shù)。

在該交通網(wǎng)絡(luò)中，車輛動態(tài)變化的過程可以利用信息在該小世界網(wǎng)絡(luò)中進(jìn)行傳遞的過程來模擬，并且利用信息遲滯的現(xiàn)象模擬交通網(wǎng)絡(luò)的交通擁堵狀況。因此，對交通網(wǎng)絡(luò)的動力學(xué)分析，可以借助無標(biāo)度特性網(wǎng)絡(luò)的最短路由策略進(jìn)行分析，可以利用局部和全局網(wǎng)絡(luò)的信息傳遞特點(diǎn)進(jìn)行計(jì)算。

本文采用局部信息路由策略對網(wǎng)絡(luò)模型的信息傳遞進(jìn)行定義：在擁有信息量為N的網(wǎng)絡(luò)中，每個單位時間中的信息都希望從源點(diǎn)向目的點(diǎn)靠近，并且?guī)в须S機(jī)性，每個鄰接節(jié)點(diǎn)在單位時間內(nèi)可以容納的信息量為M。因此，在信息傳遞的過程中，需要建立以一定概率情況下的控制，本文采用靜態(tài)局部定義法表示該概率，即：

(3)

可以看出，對于節(jié)點(diǎn)度越大的節(jié)點(diǎn)，越不容易接收新的信息量。

同時，為了描述車輛在道路上運(yùn)動的阻礙性，本文利用電阻距離定義兩節(jié)點(diǎn)之間的距離。這種距離模型有效地模擬了交通網(wǎng)絡(luò)中道路擁堵狀況對車輛形式的阻礙性，類似于電流在通過電阻時的熱能損耗。

首先，將交通網(wǎng)絡(luò)G(V,E,W)中的電阻距離矩陣表示為矩陣B(bij)的拉普拉斯譜矩陣L=(lij)，于是兩節(jié)點(diǎn)之間的電阻距離可以表示為：

(4)

且有：

L=D-H

(5)

式中：H為圖G(V,E,W)的鄰接矩陣。

(6)

式中：vki為第k個特征值對應(yīng)特征向量中第i個元素的個數(shù)；vkj為第k個特征值對應(yīng)特征向量中第j個元素的個數(shù)；λk為譜矩陣的特征值第k個大的特征值。

3 節(jié)點(diǎn)距離的相似性

本文在描述交通網(wǎng)絡(luò)的擁堵狀態(tài)時，使用節(jié)點(diǎn)電阻距離的相似性表示道路擁堵的傳遞性，這一概念可以在文獻(xiàn)[10]中得到驗(yàn)證;并給出了節(jié)點(diǎn)之間電阻距離的計(jì)算方法。但是由于該方法在小世界模型中存在局部收斂的特性，造成電阻距離變化引起節(jié)點(diǎn)信息量變化后對電阻距離產(chǎn)生反作用，因此不能描述動態(tài)的交通網(wǎng)絡(luò)。本文引入了利用數(shù)據(jù)挖掘中的聚類分析對節(jié)點(diǎn)的信息量和電阻距離進(jìn)行分類的方法，結(jié)合譜圖理論的劃分原理，量化交通網(wǎng)絡(luò)中道路的擁堵狀態(tài)，即電阻距離的動態(tài)變化。

首先，通過NP問題代替交通網(wǎng)絡(luò)中道路擁堵造成的信息傳遞問題，利用譜聚類的方法尋求最優(yōu)劃分，也就是尋找一個無線逼近狀態(tài)對圖進(jìn)行劃分。本文的設(shè)計(jì)思想是利用最小割集準(zhǔn)則建立目標(biāo)函數(shù)：

(7)

而規(guī)范割集準(zhǔn)則的目標(biāo)函數(shù)為：

(8)

建立該目標(biāo)函數(shù)的目的是將交通網(wǎng)絡(luò)圖劃分為A、B兩個子圖。其中一個子圖是從節(jié)點(diǎn)i到節(jié)點(diǎn)j消耗信息量最少的子圖，而另一個子圖是消耗信息量最大的，用于表示交通擁堵的代價(jià)。

其次，對子圖劃分采用譜聚類的方法，并利用高斯核函數(shù)表示相似距離：

(9)式中：‖vi-vj‖為兩個節(jié)點(diǎn)之間的歐式距離；σ為常數(shù)。

最后，結(jié)合本文提出的小世界網(wǎng)絡(luò)模型中局部搜索概率的方法，對圖中的電阻距離進(jìn)行聚類。步驟如下。

① 初始化圖G(V,E,W)的鄰接矩陣H與聚類個數(shù)k。

② 利用矩陣H的n個k維行向量作為數(shù)據(jù)對象集。

③ 使用k-means方法對H的行向量進(jìn)行聚類。

④ 只有當(dāng)H的行向量屬于其中一個簇時,才將原始i向量歸為一個電阻聚類。

⑤ 返回第②步執(zhí)行，直到所有行向量被分析。

4 試驗(yàn)

本文利用NetLogo5.0.3作為試驗(yàn)平臺，模擬了125輛隨機(jī)運(yùn)行的車輛在30個路口的隨機(jī)運(yùn)動，結(jié)合本文提出的小世界模型建立車輛與道路關(guān)系網(wǎng)絡(luò)。節(jié)點(diǎn)表示車輛，兩個節(jié)點(diǎn)之間有變化的鏈接說明可以有直接連接的道路。模型如圖1所示。

圖1 初始化小世界模型Fig.1 Initialization of the small world model

在置信度為0.149的情況下，得到平均最小路徑長度為3.958。以該長度作為交通網(wǎng)絡(luò)中道路擁堵時間的最大值，反映到現(xiàn)實(shí)情況為交通燈的平均等待時間，可以驗(yàn)證以某一時刻為基準(zhǔn)以后時刻路口的交通擁堵狀態(tài)。系統(tǒng)仿真結(jié)果如圖2所示。圖2(b)中，縱坐標(biāo)表示車輛平均速度，為一個相對量，其中，0表示車輛靜止，1表示車輛最高限速。圖2(c)中，縱坐標(biāo)表示車輛平均等待時間，也為一個相對量。

圖2 系統(tǒng)仿真結(jié)果Fig.2 The system simulation results

在NetLogo中，利用以下4個參數(shù)對建立起來的模型進(jìn)行控制。

① 一個節(jié)點(diǎn)重新連接網(wǎng)絡(luò)的性能，表示小世界模型中的某個節(jié)點(diǎn)的權(quán)重，如果不改變初始度，默認(rèn)為模型中節(jié)點(diǎn)的度。

② 聚類系數(shù)，這個指標(biāo)只當(dāng)模型開始運(yùn)行后才會變化，表示共有多少聚類產(chǎn)生。

③ 平均路徑長度，表示有向小世界圖中的所有節(jié)點(diǎn)達(dá)到任何節(jié)點(diǎn)的平均路徑長度。每經(jīng)過一個節(jié)點(diǎn)，長度增加1，這里取平均長度。

④ 所有節(jié)點(diǎn)重新連接網(wǎng)絡(luò)的性能，表示小世界模型中的所有節(jié)點(diǎn)的權(quán)重平均值，如果不改變初始度，默認(rèn)為模型中所有節(jié)點(diǎn)的平均度。

可以通過3個觀察窗對系統(tǒng)動態(tài)運(yùn)行過程中的參數(shù)變化進(jìn)行觀察，分別為：①在交通網(wǎng)絡(luò)中遇到紅燈停止的車輛；②所有車輛的平均速度；③所有車輛的平均等待紅燈時間。

在試驗(yàn)中，共計(jì)運(yùn)行1 220個單位時間。可以看到，每個路口的等待時間都比較均勻，也就是沒有造成非常擁堵的狀況。

5 結(jié)束語

通過利用小世界模型對交通網(wǎng)絡(luò)的車流量進(jìn)行模擬，并借助數(shù)據(jù)挖掘中的譜聚類方法計(jì)算交通流中的節(jié)點(diǎn)擁擠程度，采用節(jié)點(diǎn)電阻距離的相似性表示道路擁堵的傳遞性。給出了節(jié)點(diǎn)之間電阻距離的計(jì)算方法，利用這種方法可以對交通樞紐進(jìn)行流量控制。借助NetLogo平臺對本文提出的方法進(jìn)行仿真，仿真結(jié)果表明，采用該方法對交通進(jìn)行調(diào)節(jié)后，可以有效避免長時間的交通擁堵狀況。

[1] 陳克寒，韓盼盼，吳健.基于用戶聚類的異構(gòu)社交網(wǎng)絡(luò)推薦算法[J].計(jì)算機(jī)學(xué)報(bào)，2013,36(2):349-359.

[2] Luo Y,Packirisamy V,Hsu W C，et al. A dynamic performance tuning for speculative threads[C]∥Proceedings of the 36th ACM/IEEE Annual International Symposium on Computer Architecture,Austin,USA,2009:462-473.

[3] 徐楊,張玉林,孫婷婷,等.基于多智能體交通綠波效應(yīng)分布式協(xié)同控制算法[J].軟件學(xué)報(bào)，2012,23(11):2937-2945.

[4] Seaton K A，Hackett L M.Station trains and small-world networks[J].Physical A,2004,339(3-4):635-644.

[5] Ghandour W J，Skkary H，Masri W.The potential of using dynamic information flow analysis in data value prediction[C]∥Proceedings of the 19th International Conference on Parallel Architectures and Compilation Techniques.Vienna,Austria,2010:422-431.

[6] Arenas A,Iacute,A Az-Guilera,et al.Communication in networks with hierarchical branching[J].Physical Review Letters,2001,86(14):3196.

[7] 李遠(yuǎn)成，陰培培，趙銀亮.基于模糊聚類的推測多線程劃分算法[J].計(jì)算機(jī)學(xué)報(bào)，2014,36(2):589-592.

[8] Zhang X C,You Q Z.Clusterability analysis and incremental sampling for Nystr?m extension based spectral clustering[C]∥Proceedings of the IEEE 11th Int’l Conerence on Data Mining(ICDM),2011:942-951.

[9] 金弟,楊博,劉杰,等.復(fù)雜網(wǎng)絡(luò)簇結(jié)構(gòu)探測——基于隨機(jī)游走的蟻群算法[J].軟件學(xué)報(bào),2012,23(3):451-464.

[10]Yan D H,Huang L,Jordan M I.Fast approximate spectral clustering[C]∥Proceedins of the 15th ACM Conference on Knowledge Discovery and Data Mining(SIGKDD),2009:907-916.

Researching the Congestion Status of Transportation Network Based on Small World Model

In analyzing and applying massive data, as the preferred tool, data mining has been popular used in various areas. In order to solve the problem of congestion status of transportation network, in establishing transportation network model by adopting complex network small world model, the method of spectral clustering in data mining is used to analyze the congestion status of transportation network. Through calculating the average congestion time to control the traffic lights, thus abnormal congestion of the transportation network may not appear. With NetLogo 5.0.3 as the experimental platform, the emulated transportation network is analyzed, and the traffic flow is regulated successfully, and long period congestion is avoided.

Transportation network Complex network Data mining Small world model Congestion NetLogo

江蘇省高等職業(yè)院校國內(nèi)高級訪問學(xué)者計(jì)劃資助項(xiàng)目(編號：2014FX033)；

淮安市科技攻關(guān)基金資助項(xiàng)目(編號：HAG2010065、HAS2014021-2、HAS2014025-3)。

TP391

A

10.16086/j.cnki.issn1000-0380.201506005

江蘇省住建廳建設(shè)科技項(xiàng)目(編號：2014JH20);

修改稿收到日期：2014-12-05。

作者趙軍(1971-)，女，2006年獲江蘇大學(xué)計(jì)算機(jī)技術(shù)專業(yè)，獲碩士學(xué)位，副教授、高級工程師；主要從事網(wǎng)絡(luò)安全、數(shù)據(jù)挖掘的研究。