王 磊，羅 杰

南京郵電大學 自動化學院、人工智能學院，南京 210046

現(xiàn)代社會，隨著經(jīng)濟與城市化的高速發(fā)展，路段交通流不斷增大，使得城市的交通路網(wǎng)擁堵問題日益嚴重[1]?，F(xiàn)有的交通控制系統(tǒng)越來越難以解決交通擁堵問題，因而對于以優(yōu)化區(qū)域協(xié)調(diào)控制為目標的子區(qū)動態(tài)劃分方法的研究越來越受到社會的重視。

Walinchus于1971年首次提出交通路網(wǎng)子區(qū)，認為路段特征、車流飽和度、相鄰交叉口相位差等是子區(qū)劃分時所應考慮的因素[2]，此后在關(guān)于區(qū)域路網(wǎng)劃分的研究上，多是以交叉口關(guān)聯(lián)度指標為基礎，結(jié)合各種算法對子區(qū)進行動態(tài)劃分；Hu等根據(jù)主干道上交叉口間的實時交通流數(shù)據(jù)提出路段間的關(guān)聯(lián)度模型[3]；唐秋生等以離散指標、阻滯指標、主路徑指標為神經(jīng)元輸入，提出一種基于改進自組織神經(jīng)網(wǎng)絡的路網(wǎng)劃分方法[4]；曲大義等考慮了車流離散性、阻滯性和交通流特征規(guī)律，提出了一種相鄰交叉口關(guān)聯(lián)度，并利用聚類分析動態(tài)劃分路網(wǎng)中的交叉口群[5]；Dimitriou等對比了K-mean算法與METIS算法的路網(wǎng)劃分效果，發(fā)現(xiàn)K-mean算法對純數(shù)值對象的聚類性能優(yōu)于METIS算法[6]；Shen等定量分析了交叉口間距、交通流密度、周期時長對交叉口關(guān)聯(lián)度的影響，提出了一種基于模糊算法的路網(wǎng)劃分方法[7]；Tang等采用灰色關(guān)聯(lián)分析和譜聚類的方法對過飽和及其相關(guān)區(qū)域進行劃分，提出了城市過飽和區(qū)及其相關(guān)區(qū)域的交通協(xié)調(diào)控制模型[8]。

以上研究表明，通過對相鄰交叉口關(guān)聯(lián)度進行定量分析，并結(jié)合相關(guān)算法建立子區(qū)劃分方法，在一定程度上能夠優(yōu)化區(qū)域協(xié)調(diào)控制。然而大部分關(guān)聯(lián)度模型并未充分考慮區(qū)域路網(wǎng)的動態(tài)影響因素，多數(shù)指標仍是建立在交叉口間距與交通流量的基礎上，或是交通監(jiān)管者依據(jù)路口間距或交通流特性對路網(wǎng)進行粗糙的劃分，效果總是不盡如人意。因此，對于路網(wǎng)的子區(qū)劃分關(guān)聯(lián)度指標與劃分方法皆有待進一步研究與改進。

本文充分考慮了交叉口間距、路段流量、車隊長度、行駛時間、車隊離散性、車流密度等，建立了改進關(guān)聯(lián)度模型。基于復雜網(wǎng)絡的研究，改進經(jīng)典Newman算法，并基于改進的關(guān)聯(lián)度，對區(qū)域路網(wǎng)進行實時動態(tài)劃分。仿真實驗結(jié)果表明，所提出的子區(qū)劃分方法能夠有效提升劃分效果，為優(yōu)化區(qū)域交通路網(wǎng)協(xié)調(diào)控制提供良好的基礎。

1 區(qū)域交通路網(wǎng)模型

研究表明，在劃分區(qū)域路網(wǎng)時，各相鄰交叉口間距一般不能大于800 m，因為如果交叉口距離過大，如超過1 000 m時，會導致路段上的車流離散性很大，降低了相鄰交叉口間的關(guān)聯(lián)度，不利于區(qū)域交通的協(xié)調(diào)控制[9]。本文中所選取的區(qū)域路網(wǎng)中的“丁”字路口均采用3相位控制模式，“十”字路口均采用4相位控制模式。區(qū)域路網(wǎng)模型如圖1所示。

圖1 區(qū)域路網(wǎng)模型圖Fig.1 Regional road network model diagram

2 改進交叉口關(guān)聯(lián)度

相鄰交叉口之間的關(guān)聯(lián)特征通常受路段流量、交叉口間距、車速、車流離散性、車輛排隊、車流密度等諸多因素影響。顯然，相鄰交叉口間距屬于靜態(tài)因素，因此其對關(guān)聯(lián)度的影響是固定的，然而當其結(jié)合平均車速后，由于車速為實時變化的，因此會變?yōu)閯討B(tài)因素；路段流量、車流離散性、車輛排隊、車流密度則實時影響交叉口間的關(guān)聯(lián)程度，屬于動態(tài)因素。而現(xiàn)有的關(guān)聯(lián)度模型對以上因素大多并未考慮周全。

2.1 經(jīng)典Whitson關(guān)聯(lián)度模型

其主要考慮了交叉口間距，行程時間，路段流量三種因素，是一種常用的交叉口關(guān)聯(lián)度計算方式，見式（1）：

式中，I(i,j)為兩相鄰交叉口i與j之間的關(guān)聯(lián)度；t為車輛通過兩相鄰交叉口的行駛時間；n為自上游交叉口駛向下游交叉口的車流分支數(shù)，通常對于“丁”字路口而言，n=2，對于“十”字路口而言，n=3；qmax為從上游交叉口i駛?cè)胂掠谓徊婵趈的最大分支流量；為自上游交叉口駛?cè)胂掠谓徊婵诘慕煌靠偤蜑樽陨嫌谓徊婵隈側(cè)胂掠谓徊婵谲嚵髁康牟痪鶆蛑笜恕?/p>

2.2 引入排隊長度的Whitson關(guān)聯(lián)度模型

胡華等認為Whitson關(guān)聯(lián)度模型未考慮下游交叉口車輛排隊長度這一關(guān)鍵因素，因而引入排隊長度這一變量對模型參數(shù)t進行修改[10]，見式（2）：

式中，t為車流自上游交叉口入口至下游交叉口入口排隊車輛尾車（當進口有車輛排隊時）或進口停車線（當進口無車輛排隊時）之間的平均行駛時間；L為兩交叉口間的距離；l為下游交叉口入口車道的車輛排隊長度；vˉ為車流在兩交叉口間的平均速度。

2.3 Whitson關(guān)聯(lián)度模型的進一步改進

由式（1）和式（2）可知，改進的Whitson關(guān)聯(lián)度模型雖然考慮了相鄰交叉口之間的車輛排隊長度與車流不均勻性，但是卻忽略了上游交叉口中不同相位對駛?cè)胂掠谓徊婵谲嚵髁康挠绊懀次纯紤]從上游交叉口駛向下游交叉口的車流在時間上的離散性，此外，該模型也未考慮到如下情況：當駛?cè)肷嫌谓徊婵诘能嚵鱩駛向下游交叉口時，其每一股車流都有可能分別駛?cè)胱筠D(zhuǎn)、直行、右轉(zhuǎn)這三股下游交叉口入口車道，而不同的車流m駛?cè)脒@三股入口車道的流量也不盡相同，即該模型僅將上游交叉口的流入車流作為整體進行分析，而未考慮自上游交叉口駛?cè)胂掠谓徊婵诘能嚵髟诳臻g上的離散性。如圖2所示。

圖2 交叉口信號相位簡化圖Fig.2 Simplified phase diagram of intersection signal

因此，在綜合考慮了以上兩種情況后，本文對已改進的Whitson關(guān)聯(lián)度模型進行進一步改進，提出相鄰交叉口間的車流離散系數(shù)。

定義xi→j為交叉口i在一個周期內(nèi)允許車流駛?cè)虢徊婵趈的相位；Xi→j為交叉口i中允許車流駛?cè)虢徊婵趈的相位總數(shù)；yi→j為從交叉口i到交叉口j的入口車道（包括左轉(zhuǎn)、直行、右轉(zhuǎn)）；Yi→j為從交叉口i到j的入口車道總數(shù)；qxi→jm為駛?cè)虢徊婵趇的各車流m在相位xi→j內(nèi)駛向交叉口j的流量；為各車流m匯入交叉口j的入口車道yi→j的流量；而又由式（1）可知，qm為駛?cè)虢徊婵趇的車流m的流量，因此可求得所有駛?cè)虢徊婵趇的車流m通過相位xi→j匯入下游入口車道yi→j的總流量為：

由式（3）可求出所有車流m在一個周期內(nèi)通過不同的相位xi→j匯入各個下游入口車道yi→j的最大流量為：

式中，qi→j(max)為所有車流m通過不同的相位xi→j匯入各個下游入口車道yi→j的最大流量。由于考慮了車流在不同相位時間與不同入口車道空間上的離散性，式中xi→j與yi→j都是可變的，而非某一固定值。

再由式（4）可進一步推導出交叉口i到j的車流離散系數(shù)為：

最后，將所提出的車流離散系數(shù)代入式（1），可得改進后的Whitson關(guān)聯(lián)度模型為：

2.4 車流密度影響系數(shù)

相鄰交叉口間的車流密度是指在單位長度（通常為1 km）路段同一方向上單位時間內(nèi)的車輛數(shù)[11]，其大小反映了兩交叉口間路段的擁擠程度，因此也是判斷兩相鄰交叉口是否需要協(xié)調(diào)控制的一個重要因素。本文基于車流密度這一概念，提出交叉口i與交叉口j之間的車流密度影響系數(shù)：

式中，τ為某一時間段；L為兩交叉口i與j之間的距離；qi→j為車流在時間τ內(nèi)從交叉口i駛向j的總流量；si→j為車流從交叉口i駛向j的飽和流率；ρi→j為從交叉口i駛向j的車流在時間τ內(nèi)的平均流量密度；ρs(i→j)為從交叉口i駛向j的車流在飽和狀態(tài)下的流量密度；Fρi→j為車流從交叉口i駛向j的車流密度影響系數(shù)。

綜上，本文基于前人已改進的Whitson關(guān)聯(lián)度模型，提出相鄰交叉口間的車流離散系數(shù)，對模型進一步改進，并基于車流密度提出交叉口間的車流密度影響系數(shù)，建立相鄰交叉口間的離散-密度關(guān)聯(lián)度模型，見式（8）：

式中，I(i→j)為兩交叉口i到j的離散-密度關(guān)聯(lián)度；ni→j為車流從交叉口i駛?cè)雑的分支數(shù)；μi→j為交叉口i到j的車流離散系數(shù)；ti→j為車輛自交叉口i入口行駛至交叉口j入口排隊車輛尾車的平均行駛時間；Fρi→j為交叉口i到交叉口j的車流密度影響系數(shù)。

考慮到相鄰交叉口間的路段交通流通常具有雙向性，因此，根據(jù)式（8）可以求出交叉口j到交叉口i的離散-密度關(guān)聯(lián)度I(j→i)，兩交叉口間關(guān)聯(lián)度取I(i→j)與I(j→i)的平均值，因此交叉口i與交叉口j的最終關(guān)聯(lián)度為：

3 改進子區(qū)劃分方法

根據(jù)復雜網(wǎng)絡中對社團劃分的研究[12]，首先在傳統(tǒng)的Newman算法中引入邊權(quán)，對其模塊度進行改進，其次將區(qū)域路網(wǎng)抽象為社團網(wǎng)絡，路網(wǎng)中的交叉口抽象為節(jié)點，相鄰交叉口間的路段抽象為邊，在改進的Newman快速算法中引入離散-密度關(guān)聯(lián)度，將其作為節(jié)點i與節(jié)點j之間的邊權(quán)，提出改進的子區(qū)劃分方法。

3.1 社團劃分算法中的參數(shù)介紹

節(jié)點度是網(wǎng)絡圖中最基本的概念之一，節(jié)點i的度ki是指在社團網(wǎng)絡中與此節(jié)點相連的總邊數(shù)，可簡單明了地表現(xiàn)節(jié)點的網(wǎng)絡特性，是權(quán)衡一個節(jié)點的重要性的指標之一，ki的值越大，說明節(jié)點i在網(wǎng)絡中越重要，反之則越不重要；邊權(quán)wij是連接節(jié)點i與節(jié)點j之間邊的權(quán)值，以此來衡量兩個節(jié)點之間關(guān)聯(lián)性的強弱，wij的值越大，說明節(jié)點i與j之間的關(guān)聯(lián)性越強，反之則越弱；點權(quán)di是所有與節(jié)點i連邊的權(quán)值之和，即di=，通常用來描述節(jié)點在網(wǎng)絡中的作用性大小，di的值越大，說明節(jié)點i在網(wǎng)絡中所占的權(quán)重越大，則其在網(wǎng)絡中所起的作用越大，反之則越小。

3.2 模塊度介紹

模塊度[13-14]是一種用來評判社團劃分結(jié)果優(yōu)劣的標準，通常用Q來表示，Q值越大，表明劃分結(jié)果越好。在一個特定的社團劃分過程中，當社團模塊度Q最大時，劃分結(jié)果最優(yōu)，此時模塊度為Qmax，其取值范圍一般在0.3～0.7之間。

在無權(quán)網(wǎng)絡中，Q的表達式為：

式中，eii為社團i中的邊數(shù)在整個網(wǎng)絡總邊數(shù)中的占比；Tre為所有社團的內(nèi)部邊數(shù)在整個網(wǎng)絡總邊數(shù)中的占比。

3.3 傳統(tǒng)Newman算法

Newman算法[13-14]是Newman等基于GN算法所提出的社團凝聚算法，該算法實質(zhì)上是一種基于貪婪算法思想的凝聚算法，其算法流程如下：

（1）將初始網(wǎng)絡分成為n個社團，一個節(jié)點表示一個獨立社團。定義一個n階對稱矩陣E和一個一維數(shù)組A，其中，矩陣E的行列數(shù)等于網(wǎng)絡的總節(jié)點數(shù)，其元素eij為社團i與社團j間相連的邊數(shù)在網(wǎng)絡總邊數(shù)中的占比；數(shù)組A的元素個數(shù)等于網(wǎng)絡的節(jié)點總數(shù)，其元素ai為社團i的內(nèi)部節(jié)點與外部節(jié)點相連的邊數(shù)在網(wǎng)絡總邊數(shù)中的占比。則初始的eij與ai滿足：

式中，p為網(wǎng)絡中的總邊數(shù)；ki為節(jié)點i的度。

（2）將相互連接的社團依次合并，然后計算模塊度增量ΔQ，由貪婪算法可知，社團應朝著模塊度增加速度最快的方向合并，ΔQ的計算公式為：

將相應的ΔQ的社團i與j進行合并，并將合并之后的模塊度值記錄下來。在每次的合并之后，分別更新

（3）將步驟（2）反復執(zhí)行，持續(xù)地合并社團，當整個網(wǎng)絡合為一個社團時，停止合并，最多要進行n-1次社團合并。當模塊度最大時，此時的劃分結(jié)果為最優(yōu)結(jié)果。

3.4 改進Newman算法

傳統(tǒng)的Newman算法的提出是基于無權(quán)網(wǎng)絡，為了能夠應用于有權(quán)網(wǎng)絡，現(xiàn)對傳統(tǒng)Newman算法進行改進。

首先對無權(quán)網(wǎng)絡模塊度的表達式進行改進，每個社團網(wǎng)絡中的節(jié)點都代表一個社團，將初始化的n個社團記為(c1,c2,…,cn)，定義矩陣C=[cij]為n階對稱矩陣，其元素cij為社團i與社團j之間相連的邊的邊權(quán)和在整個網(wǎng)絡中總邊權(quán)的占比；矩陣C的各行元素之和為，表示社團i的內(nèi)部節(jié)點與外部節(jié)點相連的邊的邊權(quán)之和在整個網(wǎng)絡中總邊權(quán)的占比，由此可得到改進的模塊度，即有權(quán)網(wǎng)絡的模塊度為：

式中，cii為社團i中的邊權(quán)之和在整個網(wǎng)絡中總邊權(quán)的占比；Tre為矩陣C的對角線元素和，表示所有社團的內(nèi)部邊權(quán)之和在整個社團網(wǎng)絡中總邊權(quán)的占比表示矩陣C2的所有元素之和。

與傳統(tǒng)的Newman算法相比，改進的Newman算法引入了網(wǎng)絡節(jié)點間的關(guān)聯(lián)特性，節(jié)點間的邊權(quán)大小即表征了節(jié)點間的關(guān)聯(lián)度大小，故可將eij與ai改進為：

式中，wij為節(jié)點i與節(jié)點j之間的邊權(quán)。

3.5 改進的子區(qū)劃分方法

區(qū)域路網(wǎng)是一種典型的復雜網(wǎng)絡，將改進的Newman算法與離散-密度關(guān)聯(lián)度模型相結(jié)合，提出基于引入離散-密度關(guān)聯(lián)度的改進Newman算法的子區(qū)動態(tài)劃分方法，此方法的優(yōu)越之處在于，其結(jié)合了改進Newman算法對邊權(quán)分析的高效性與精確性以及離散-密度關(guān)聯(lián)度對交通數(shù)據(jù)采集的實時性，能夠依據(jù)路網(wǎng)交通流的實時特性對不同時段的路網(wǎng)子區(qū)進行快速而準確的劃分。

在引入離散-密度關(guān)聯(lián)度模型后，可對式（15）與式（16）進行如下改進：

式中，I(i,j)為交叉口i與j之間的離散-密度關(guān)聯(lián)度。

4 仿真實驗

依據(jù)所提出的模型與算法，選取南京市棲霞區(qū)某區(qū)域路網(wǎng)，結(jié)合百度地圖，在網(wǎng)上實時查詢該路網(wǎng)的交通數(shù)據(jù)，以MATLAB為工具對Newman快速算法進行編程，將基于引入離散-密度關(guān)聯(lián)度的改進Newman算法所劃分的結(jié)果，分別與基于傳統(tǒng)Newman算法所劃分的結(jié)果、基于引入胡華等改進Whitson關(guān)聯(lián)度的改進Newman算法所劃分的結(jié)果進行仿真對比。

4.1 路網(wǎng)選取與關(guān)聯(lián)度計算

如圖3，選取了南京市棲霞區(qū)某區(qū)域路網(wǎng)，包含了文瀾路、仙林大道、仙境路等16個交叉路口以及23條路段。

圖3 南京市棲霞區(qū)某區(qū)域路網(wǎng)Fig.3 Regional road network of Qixia District，Nanjing City

在網(wǎng)上查詢到該區(qū)域路網(wǎng)在某天14：00—15：00時段的交通流數(shù)據(jù)，并測得路網(wǎng)中各相鄰交叉口間距，結(jié)合圖4，可求得胡華等改進Whitson關(guān)聯(lián)度與離散-密度關(guān)聯(lián)度，如表1和表2所示。

表1 14：00—15：00胡華等改進Whitson關(guān)聯(lián)度I(i,j)Table 1 Modified Whitson correlation degree I(i,j)by Hu Hua et al at 14：00—15：00

表2 14：00—15：00離散-密度關(guān)聯(lián)度I(i,j)Table 2 Discrete-density correlation degree I(i,j )at 14：00—15：00

圖4 區(qū)域路網(wǎng)簡化圖Fig.4 Simplified map of regional road network

4.2 三種劃分方法對比

方法1基于傳統(tǒng)Newman算法來劃分所選取的區(qū)域路網(wǎng)，其社團合并過程所對應的模塊度點狀圖、子區(qū)劃分結(jié)果樹狀圖與路網(wǎng)車流密度簡化圖分別由圖5（a）、（b）、（c）所示。

由圖5可知，當交叉口合并至14號時，子區(qū)個數(shù)為3，對應的模塊度最大，為0.397 0，此時的子區(qū)劃分結(jié)果最優(yōu)，分別為：子區(qū)一，交叉口1，2，5，6；子區(qū)二，交叉口3，4，7，8，9，13；子區(qū)三，10，11，12，14，15，16。這種基于無權(quán)網(wǎng)絡的劃分方法僅以交叉口間的鄰接矩陣為模型輸入，其劃分結(jié)果是固定不變的，無法隨著交通流的變化而改變，因此沒有實用性。

圖5 方法1仿真圖Fig.5 Method 1 simulation diagram

方法2基于引入胡華等改進Whitson關(guān)聯(lián)度的改進Newman算法來劃分所選取的區(qū)域路網(wǎng)，其模塊度點狀圖、劃分結(jié)果樹狀圖與路網(wǎng)車流密度簡化圖分別由圖6（a）、（b）、（c）所示。

由圖6可知，當交叉口合并至13號時，子區(qū)個數(shù)為4，對應的模塊度最大，為0.438 4，此時子區(qū)劃分結(jié)果最優(yōu)，分別為：子區(qū)一，交叉口1，2，5，6；子區(qū)二，3，4；子區(qū)三，7，8，9，12，13，16；子區(qū)四，10，11，14，15。與方法1相比，這種劃分方法雖然考慮了相鄰交叉口之間的車輛排隊長度與車流不均勻性，但是并未考慮到其他動態(tài)因素的影響，因此其劃分結(jié)果并不準確。

方法3基于引入本文所提出的離散-密度關(guān)聯(lián)度的改進Newman算法來劃分所選取的區(qū)域路網(wǎng)，其模塊度點狀圖、劃分結(jié)果樹狀圖與路網(wǎng)車流密度簡化圖分別由圖7（a）、（b）、（c）所示。

圖7 方法3仿真圖Fig.7 Method 3 simulation diagram

由圖7可知，當交叉口合并至12號時，子區(qū)個數(shù)為5，對應的模塊度最大，為0.633 3，此時子區(qū)劃分結(jié)果最優(yōu)，分別為：子區(qū)一，1，2，5，6；子區(qū)二，3，4，7；子區(qū)三，8，9，12，13；子區(qū)四，11，15，16；子區(qū)五，10，14。與方法2相比，此方法在考慮相鄰交叉口間車輛排隊長度的基礎上，進一步將車流不均勻指標改進為車流離散系數(shù)，并提出車流密度影響系數(shù)，綜合考慮了車流在時間與空間上的離散性以及車流密度對區(qū)域動態(tài)劃分的影響，使劃分結(jié)果更為合理。

為了進一步驗證方法3的實時性，本文在相同的區(qū)域路網(wǎng)查詢17：00—18：00時段的交通流數(shù)據(jù)，利用方法3進行路網(wǎng)劃分，并將劃分結(jié)果與14：00—15：00時段的劃分結(jié)果進行對比。17：00—18：00的離散-密度關(guān)聯(lián)度如表3所示。

表3 17：00—18：00離散-密度關(guān)聯(lián)度I(i,j)Table 3 Discrete-density correlation degree I(i,j)at 17：00—18：00

其模塊度點狀圖、劃分結(jié)果樹狀圖與路網(wǎng)車流密度簡化圖分別由圖8（a）、（b）、（c）所示。

圖8 方法3在17：00—18：00的仿真圖Fig.8 Method 3 simulation diagram at 17：00—18：00

由圖8可知，當交叉口合并至12號時，子區(qū)個數(shù)為5，對應的模塊度最大，為0.557 1，此時子區(qū)劃分結(jié)果最優(yōu)，分別為：子區(qū)一，1，5，10；子區(qū)二，2，3，6，7；子區(qū)三，4，8，9；子區(qū)四，11，14，15；子區(qū)五，12，13，16。與14：00—15：00時段的劃分結(jié)果相比，該時段為晚高峰時期，車流量驟增，其交通流數(shù)據(jù)也隨之變化，其劃分結(jié)果也隨著不同的交通流數(shù)據(jù)發(fā)生了變化，因此可驗證方法3具有實時性，能夠依據(jù)不同時段的交通數(shù)據(jù)對路網(wǎng)子區(qū)進行動態(tài)劃分。

5 結(jié)束語

在已有的關(guān)聯(lián)度模型和復雜網(wǎng)絡的研究基礎上，以優(yōu)化區(qū)域協(xié)調(diào)控制為目標，綜合考慮了相鄰交叉口間距、路段流量、車流速度、車隊長度、行程時間、車流離散性、車流密度等因素，提出了一種融合改進關(guān)聯(lián)度模型與改進Newman算法的區(qū)域路網(wǎng)動態(tài)劃分方法。通過仿真實驗對比可知，該劃分方法有效地結(jié)合了不同時間段的實時交通流數(shù)據(jù)，使得子區(qū)劃分結(jié)果更加合理，對于優(yōu)化區(qū)域交通不合理配時、解決交通擁堵等問題具有重要的價值。