基于小世界模型的交通網絡擁堵狀態研究

趙 軍

(江蘇食品職業技術學院信息工程系,江蘇 淮安 223003)

基于小世界模型的交通網絡擁堵狀態研究

趙 軍

(江蘇食品職業技術學院信息工程系,江蘇 淮安 223003)

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

交通網絡 復雜網絡 數據挖掘 小世界模型 擁堵 NetLogo

0 引言

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

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

通過對以上幾個方面的深入研究，越來越多的研究將車輛行為的復雜性與交通網絡的復雜性相結合，利用動力學方法研究城市交通網絡的擁堵原理、機制和解決方法。從復雜網絡的研究可以看出，利用相互關聯節點以及節點之間的關系,可以對互聯網、蛋白質網、流行病網以及交通網等多種現實問題進行研究，設計的領域也包括諸如數學、生物學、物理學、社會科學、醫學等。隨著研究的不斷深入，越來越多的問題都可以借助復雜網絡的模型進行仿真與分析，成為一門交叉能力較強的學科。

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

1 交通網絡復雜網絡模型

在模擬交通狀況的復雜網絡模型中，常用小世界模型進行分析。小世界模型通過分析臨近節點之間的關聯性，構造了具有一定拓撲結構的隨機網絡，網絡中的臨近節點通過某一小概率的幾率相互連接，形成局部無規律性而整體存在顯著規律的網絡。這種模型可以用于描述交通網絡中的車輛行為，即車輛從一個節點(通常用路口表示交通網絡中的節點)出發達到另外一個節點的可能性。

利用這種模型描述的交通網絡具有以下特點。

① 將交通網絡的道路復雜性描述為節點之間的鏈接關系，利用節點的高聚類性可以對交通網絡的拓撲結構進行可靠性分析，有助于分析交通網絡在各種交通流的影響下是否具有穩定性。

② 小世界網絡的平均最小距離比較容易分析，可以使得在模擬交通網時保持較好的動態性和偏好依附性。這一點也比較接近車輛在交通網絡中的實際運行機制。

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

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

2 交通網路動態模型建立

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

(1)

當節點i≠j時，如果兩個節點之間存在連接，則元素為1，否則為0。

對網絡的權值也同樣可以利用矩陣B(bij)表示，其中矩陣元素定義為：

(2)

當節點i≠j且兩者之間存在邊的情況下，該邊的權重為wi，否則為+∞。

為了研究車輛在該網絡中的行為規律，對車輛的行為選擇進行了仿真。文獻[9]利用改進的二項分布模擬具有無標度特性的網絡，將節點的最小度的求解方法轉換為小世界網絡度的分布情況，即：

式中：N為網絡中的節點數量；p為節點之間相連接的概率；k為網絡中的邊的數量；K為每個節點的最小度；c為網絡的簇系數。

在該交通網絡中，車輛動態變化的過程可以利用信息在該小世界網絡中進行傳遞的過程來模擬，并且利用信息遲滯的現象模擬交通網絡的交通擁堵狀況。因此，對交通網絡的動力學分析，可以借助無標度特性網絡的最短路由策略進行分析，可以利用局部和全局網絡的信息傳遞特點進行計算。

本文采用局部信息路由策略對網絡模型的信息傳遞進行定義：在擁有信息量為N的網絡中，每個單位時間中的信息都希望從源點向目的點靠近，并且帶有隨機性，每個鄰接節點在單位時間內可以容納的信息量為M。因此，在信息傳遞的過程中，需要建立以一定概率情況下的控制，本文采用靜態局部定義法表示該概率，即：

(3)

可以看出，對于節點度越大的節點，越不容易接收新的信息量。

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

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

(4)

且有：

L=D-H

(5)

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

(6)

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

3 節點距離的相似性

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

首先，通過NP問題代替交通網絡中道路擁堵造成的信息傳遞問題，利用譜聚類的方法尋求最優劃分，也就是尋找一個無線逼近狀態對圖進行劃分。本文的設計思想是利用最小割集準則建立目標函數：

(7)

而規范割集準則的目標函數為：

(8)

建立該目標函數的目的是將交通網絡圖劃分為A、B兩個子圖。其中一個子圖是從節點i到節點j消耗信息量最少的子圖，而另一個子圖是消耗信息量最大的，用于表示交通擁堵的代價。

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

(9)式中：‖vi-vj‖為兩個節點之間的歐式距離；σ為常數。

最后，結合本文提出的小世界網絡模型中局部搜索概率的方法，對圖中的電阻距離進行聚類。步驟如下。

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

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

③ 使用k-means方法對H的行向量進行聚類。

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

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

4 試驗

本文利用NetLogo5.0.3作為試驗平臺，模擬了125輛隨機運行的車輛在30個路口的隨機運動，結合本文提出的小世界模型建立車輛與道路關系網絡。節點表示車輛，兩個節點之間有變化的鏈接說明可以有直接連接的道路。模型如圖1所示。

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

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

圖2 系統仿真結果Fig.2 The system simulation results

在NetLogo中，利用以下4個參數對建立起來的模型進行控制。

① 一個節點重新連接網絡的性能，表示小世界模型中的某個節點的權重，如果不改變初始度，默認為模型中節點的度。

② 聚類系數，這個指標只當模型開始運行后才會變化，表示共有多少聚類產生。

③ 平均路徑長度，表示有向小世界圖中的所有節點達到任何節點的平均路徑長度。每經過一個節點，長度增加1，這里取平均長度。

④ 所有節點重新連接網絡的性能，表示小世界模型中的所有節點的權重平均值，如果不改變初始度，默認為模型中所有節點的平均度。

可以通過3個觀察窗對系統動態運行過程中的參數變化進行觀察，分別為：①在交通網絡中遇到紅燈停止的車輛；②所有車輛的平均速度；③所有車輛的平均等待紅燈時間。

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

5 結束語

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

[1] 陳克寒，韓盼盼，吳健.基于用戶聚類的異構社交網絡推薦算法[J].計算機學報，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] 徐楊,張玉林,孫婷婷,等.基于多智能體交通綠波效應分布式協同控制算法[J].軟件學報，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] 李遠成，陰培培，趙銀亮.基于模糊聚類的推測多線程劃分算法[J].計算機學報，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] 金弟,楊博,劉杰,等.復雜網絡簇結構探測——基于隨機游走的蟻群算法[J].軟件學報,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

江蘇省高等職業院校國內高級訪問學者計劃資助項目(編號：2014FX033)；

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

TP391

A

10.16086/j.cnki.issn1000-0380.201506005

江蘇省住建廳建設科技項目(編號：2014JH20);

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

作者趙軍(1971-)，女，2006年獲江蘇大學計算機技術專業，獲碩士學位，副教授、高級工程師；主要從事網絡安全、數據挖掘的研究。