趙 軍

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

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

趙 軍

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

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

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

0 引言

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

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

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

同時(shí)，由于復(fù)雜網(wǎng)絡(luò)中的規(guī)律性往往是通過對(duì)大量數(shù)據(jù)的分析后得到的，并且有的規(guī)律性還需要數(shù)據(jù)去驗(yàn)證，因此，借助數(shù)據(jù)挖掘技術(shù)可以對(duì)利用復(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)通過某一小概率的幾率相互連接，形成局部無(wú)規(guī)律性而整體存在顯著規(guī)律的網(wǎng)絡(luò)。這種模型可以用于描述交通網(wǎng)絡(luò)中的車輛行為，即車輛從一個(gè)節(jié)點(diǎn)(通常用路口表示交通網(wǎng)絡(luò)中的節(jié)點(diǎn))出發(fā)達(dá)到另外一個(gè)節(jié)點(diǎn)的可能性。

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

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

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

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

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

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

利用小世界模型對(duì)交通網(wǎng)絡(luò)進(jìn)行模擬時(shí)，首先要對(duì)道路的方向性、路段的長(zhǎng)度和車輛滯留時(shí)間等因素進(jìn)行定義。因此，交通網(wǎng)絡(luò)符合有向加權(quán)圖的基本特點(diǎn)，可以對(duì)該網(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時(shí)，如果兩個(gè)節(jié)點(diǎn)之間存在連接，則元素為1，否則為0。

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

(2)

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

為了研究車輛在該網(wǎng)絡(luò)中的行為規(guī)律，對(duì)車輛的行為選擇進(jìn)行了仿真。文獻(xiàn)[9]利用改進(jìn)的二項(xiàng)分布模擬具有無(wú)標(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為每個(gè)節(jié)點(diǎn)的最小度；c為網(wǎng)絡(luò)的簇系數(shù)。

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

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

(3)

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

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

首先，將交通網(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個(gè)特征值對(duì)應(yīng)特征向量中第i個(gè)元素的個(gè)數(shù)；vkj為第k個(gè)特征值對(duì)應(yīng)特征向量中第j個(gè)元素的個(gè)數(shù)；λk為譜矩陣的特征值第k個(gè)大的特征值。

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

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

首先，通過NP問題代替交通網(wǎng)絡(luò)中道路擁堵造成的信息傳遞問題，利用譜聚類的方法尋求最優(yōu)劃分，也就是尋找一個(gè)無(wú)線逼近狀態(tài)對(duì)圖進(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兩個(gè)子圖。其中一個(gè)子圖是從節(jié)點(diǎn)i到節(jié)點(diǎn)j消耗信息量最少的子圖，而另一個(gè)子圖是消耗信息量最大的，用于表示交通擁堵的代價(jià)。

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

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

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

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

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

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

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

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

4 試驗(yàn)

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

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

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

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

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

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

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

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

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

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

在試驗(yàn)中，共計(jì)運(yùn)行1 220個(gè)單位時(shí)間?？梢钥吹?，每個(gè)路口的等待時(shí)間都比較均勻，也就是沒有造成非常擁堵的狀況。

5 結(jié)束語(yǔ)

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

[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)成，陰培培，趙銀亮.基于模糊聚類的推測(cè)多線程劃分算法[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)探測(cè)——基于隨機(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è)院校國(guó)內(nèi)高級(jí)訪問學(xué)者計(jì)劃資助項(xiàng)目(編號(hào)：2014FX033)；

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

TP391

A

10.16086/j.cnki.issn1000-0380.201506005

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

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

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