修偉杰, 王 力, 張立立, 李 敏, 張玲玉

(1.北方工業(yè)大學(xué) 城市道路交通智能控制技術(shù)北京市重點(diǎn)實驗室, 北京 100144;2.北京石油化工學(xué)院 信息工程學(xué)院, 北京 102617; 3.北京中合云通科技發(fā)展有限公司, 北京 100041)

0 引 言

一個規(guī)模較大城市的路網(wǎng)交通信號控制系統(tǒng)通常會將路網(wǎng)按照轄區(qū)屬性、交叉口關(guān)聯(lián)性或路網(wǎng)控制策略進(jìn)行區(qū)域動態(tài)劃分, 以減小控制系統(tǒng)的復(fù)雜度。近年來，交通子區(qū)動態(tài)劃分的研究主要集中在指標(biāo)的選取和劃分兩方面。

在指標(biāo)選取方面：別一鳴等[1]從交通控制系統(tǒng)整體角度出發(fā), 研究了子區(qū)劃分與信號配時方案優(yōu)化的內(nèi)在聯(lián)系, 以飽和度為指標(biāo)，將交叉口狀態(tài)劃分為4個等級, 并根據(jù)狀態(tài)等級確定交叉口的控制目標(biāo), 由此建立子區(qū)劃分原則; 楊潔等[2]利用協(xié)調(diào)系數(shù)與不均衡系數(shù)兩類路段關(guān)聯(lián)度指標(biāo), 分析交叉口群交通關(guān)聯(lián)特征, 提出交叉口群信號協(xié)調(diào)控制范圍動態(tài)劃分方法; 沈國江等[3]在引入路段車輛容量比和路段交通需求影響度的基礎(chǔ)上, 提出基于路口擁堵等級劃分與相鄰路口關(guān)聯(lián)度的一種子區(qū)分級動態(tài)劃分策略；Liu等[4]利用Pearson相關(guān)系數(shù)和數(shù)據(jù)歸一化, 提出了一種新的組合特征參數(shù)用于聚類劃分算法。

在劃分算法研究領(lǐng)域：首艷芳等[5]建立了一套基于相鄰交叉口間距最大-最小原則和交叉口相聚度分析的控制子區(qū)劃分模型, 設(shè)計了一種交叉口群聚類算法, 實現(xiàn)了對控制子區(qū)劃分方案的綜合分析評價; 馬旭輝等[6]從路網(wǎng)拓?fù)浣Y(jié)構(gòu)入手, 設(shè)計了一種基于路網(wǎng)可達(dá)性的交通子區(qū)劃分方法; 王力等[7]以社區(qū)模塊度為評價指標(biāo), 利用凝聚社區(qū)發(fā)現(xiàn)算法實現(xiàn)了控制子區(qū)劃分; 以此為基礎(chǔ), 張正華等[8]通過分析相鄰路口的路段長度、排隊長度和信號周期等3個因素建立相鄰交叉口總關(guān)聯(lián)度模型, 提出一種基于改進(jìn)社區(qū)發(fā)現(xiàn)算法的交通控制子區(qū)動態(tài)劃分方法; 盧凱等[9]建立了基于關(guān)聯(lián)度分析的子區(qū)動態(tài)劃分模型, 并結(jié)合遺傳算法的優(yōu)化求解模型的解, 但遺傳算法在搜索效率與尋優(yōu)能力方面存在不足, 使得控制子區(qū)劃分算法不能更快更準(zhǔn)地搜索到最優(yōu)或次優(yōu)子區(qū)劃分方案；Cebecauer等[10]根據(jù)路段相鄰性采用聚類方法將大型路網(wǎng)轉(zhuǎn)換成一個具有特定結(jié)構(gòu)的圖, 并提出了一個基于譜聚類的子區(qū)劃分算法；An等[11]設(shè)計了一種包括4個步驟的交通子區(qū)聚類劃分方法, 該方法引入了λ關(guān)聯(lián)度的概念, 采用了基于聚類的區(qū)域增長技術(shù)和啟發(fā)式算法, 解決了譜聚類等圖割方法要求路網(wǎng)信息完整的問題。

上述研究多未考慮多交叉口之間總體關(guān)聯(lián)性大小, 也未將影響控制子區(qū)劃分的各種因素進(jìn)行有效綜合，且分區(qū)指標(biāo)選取往往集中在一種或幾種交通參數(shù)的綜合選取上, 并未考慮路網(wǎng)的全局特性，算法缺乏理論支撐。本文通過路網(wǎng)交叉口和路段權(quán)重建模, 將路網(wǎng)抽象成加權(quán)拓?fù)渚W(wǎng)絡(luò), 將城市交通路網(wǎng)子區(qū)劃分轉(zhuǎn)化為圖劃分問題, 按照指定的約束條件將路網(wǎng)劃分為若干個子域并不斷動態(tài)優(yōu)化目標(biāo)函數(shù)，對于劃分結(jié)果, 進(jìn)一步提出多交叉口狀態(tài)可控的判據(jù)為路網(wǎng)協(xié)調(diào)控制策略設(shè)計提供依據(jù)。

1 問題描述

1.1 路網(wǎng)拓?fù)浣?/h3>

1.2 基于均衡k劃分的子區(qū)動態(tài)劃分問題描述

1.3 交叉口權(quán)重模型

各交叉口對區(qū)域總體狀態(tài)影響具有差異性, 交叉口權(quán)重體現(xiàn)對網(wǎng)絡(luò)特定結(jié)構(gòu)和功能的影響。

1.3.1 交叉口節(jié)點(diǎn)阻抗權(quán)重——信號控制相關(guān) 交叉口節(jié)點(diǎn)阻抗主要是指交叉口處車輛產(chǎn)生的延誤, 是反映車輛在信號交叉口的受阻情況以及行駛時間損失情況的指標(biāo)。

(1)

式中:y=1-(1-K/Kj)2，Kj=n/(l+l0);c為信號周期;λ為綠信比;q為該車道車輛到達(dá)率;x0為飽和度臨界值;K為交通密度;Kj為理論阻塞密度;n為單向機(jī)動車車道條數(shù);l0為平均阻塞車間凈距, 取1.5 m;l為平均車身長度, 取5 m。

1.3.3 交叉口綜合權(quán)重 將3個權(quán)重相乘并進(jìn)行歸一化, 得到交叉口的總體權(quán)重模型

(2)

1.4 路段權(quán)重模型

1.4.1 路段綜合長度權(quán)重 路段權(quán)重體現(xiàn)路段狀態(tài)對區(qū)域整體狀態(tài)的影響程度。路段綜合長度權(quán)重反映了不同等級路段在路網(wǎng)中所承擔(dān)的交通運(yùn)輸功能, 承載交通量越大的路段, 對路網(wǎng)整體狀態(tài)影響越大, 應(yīng)賦予其較大的權(quán)重。

1.4.2 BPR路段阻抗函數(shù)權(quán)重 BPR函數(shù)是反映路段行程時間與路段流量相互關(guān)系的函數(shù), 是目前計算道路阻抗中應(yīng)用最廣泛的函數(shù)之一。

wFI=t0[1+α(Q/C)β],

(3)

式中:wFI為兩交叉口間的路段阻抗權(quán)重;t0為自由流狀態(tài)下路段行程時間;Q為路段交通量;C為路段通行能力；α、β為阻抗影響參數(shù), 美國公路局推薦α=0.15和β=4。

1.4.3 路段綜合權(quán)重 權(quán)重越大, 說明路段越重要, 連線上的兩個頂點(diǎn)關(guān)聯(lián)性越大。將以上兩個權(quán)重相乘并歸一化, 得到路段Lij的總體權(quán)重wij模型為

(4)

2 基于禁忌搜索的路網(wǎng)子區(qū)動態(tài)劃分

城市交通網(wǎng)絡(luò)的均衡k劃分[12]的目的是形成規(guī)模相似且關(guān)聯(lián)性較弱的交通子區(qū), 即圖劃分中割權(quán)最小、子集權(quán)值和均衡的目標(biāo)即為路網(wǎng)k劃分的目標(biāo)。選取禁忌搜索算法[13]來求解圖劃分問題, 能夠滿足子區(qū)間交叉口合并和分離的劃分。

2.1 基于禁忌搜索的均衡k劃分算法

Step2: 參數(shù)準(zhǔn)備。采用歷史交通流數(shù)據(jù), 包括各交叉口的流量、路段車道數(shù)、路段長度、通行能力、路段旅行時間等基礎(chǔ)參數(shù), 計算交叉口與路段的權(quán)重系數(shù), 構(gòu)建路網(wǎng)的有權(quán)拓?fù)鋱D。

Step4: 定義禁忌對象和移動操作。算法的移動操作是從當(dāng)前解產(chǎn)生新解的途徑。首先從不同子集中選擇兩交叉口v1∈Vi,v2∈Vj, 且v1(v2)和目標(biāo)子集Vj(Vi)至少有一個交叉口相連，再將交叉口v1(v2)移動到Vj(Vi)。禁忌對象是交叉口v移動到原始的子集, 在本文中禁忌長度為6(經(jīng)過6步搜索之后v可以重新被移動到原始子集)。

Step5: 選擇策略。如果不止一個鄰域有最小割權(quán), 選擇策略設(shè)計為: 先考慮鄰域?qū)ο笫欠裉幱诮蔂顟B(tài); 再考慮移動頻數(shù), 即每個交叉口移動到不同子集的頻數(shù)。將懲罰移動頻數(shù)較高的交叉口給予較高的優(yōu)先選擇權(quán)。

Step6: 算法停止準(zhǔn)則。子區(qū)劃分既要保證子區(qū)內(nèi)各交叉口的密度近似, 又要保證各子區(qū)間飽和度具有較大差異。因此選用密度相似性指標(biāo)來評價子區(qū)的劃分結(jié)果:

(5)

式中:k表示分區(qū)總數(shù)；d表示子區(qū)路段密度；C表示子區(qū)集;NI、NJ分別表示子區(qū)I和J包含的節(jié)點(diǎn)數(shù);DSIk是衡量子區(qū)I劃分合理與否的指標(biāo);DSII表示子區(qū)內(nèi)部密度的相似性;DSNIJ表示相鄰子區(qū)之間密度的相似性;NeiI表示與子區(qū)A相鄰的相似性最大的子區(qū);DSI為所有分區(qū)密度相似性均值, 若DSI<1, 子區(qū)劃分較合理。

2.2 子區(qū)的動態(tài)調(diào)整

3 實驗分析

采集濰坊市部分路網(wǎng)的實際流量數(shù)據(jù), 結(jié)合路網(wǎng)的物理拓?fù)涮匦? 驗證所提劃分方法的有效性, 路網(wǎng)如圖1所示。該路網(wǎng)包含32個燈控交叉口, 104條路段。當(dāng)前路網(wǎng)為分時段固定配時方案, 選取早高峰時段的數(shù)據(jù): 路網(wǎng)中配時方案包含2處兩階段運(yùn)行路口, 6處三階段運(yùn)行路口, 其余14處為四階段運(yùn)行。

圖1 濰坊實際路網(wǎng)(a)與拓?fù)?b)示意圖

路網(wǎng)的交叉口和路段權(quán)重分布如圖2所示?？芍? 不同交叉口和路段, 其權(quán)重大小有明顯的差異。權(quán)重值較高的交叉口5、11、15、30主要集中在醫(yī)院和商圈附近, 一方面負(fù)擔(dān)了大量的交通流量, 另一方面是城市交通量的主要發(fā)生、吸引源, 這些交叉口附近呈現(xiàn)明顯的交通流量聚集性, 故權(quán)重較大。

圖2 交叉口(a)與路段(b)權(quán)重

鄰接節(jié)點(diǎn)之間存在重要依賴性關(guān)系, 結(jié)合交叉口自身的位置信息, 交叉口權(quán)重的大小搭配能夠使路網(wǎng)的節(jié)點(diǎn)群均勻分布, 以避免出現(xiàn)重要性太大的節(jié)點(diǎn)群影響路網(wǎng)的綜合調(diào)控指標(biāo)。

表1為不同子區(qū)劃分結(jié)果根據(jù)2.1節(jié)k值的選取原則, 在濰坊實際路網(wǎng)中, 計算所得的k=4為最優(yōu)的劃分形式。如圖3所示, 在選取k=4進(jìn)行路網(wǎng)子區(qū)劃分時可有兩種劃分結(jié)果適應(yīng)路網(wǎng)不同交通流量規(guī)模和交通狀態(tài), 可以看出, 路口13、16和17是劃分子區(qū)的重要邊界節(jié)點(diǎn), 在交通流量變化時會發(fā)生子區(qū)歸屬變化。

圖3 k=4子區(qū)劃分結(jié)果

表1 不同分區(qū)數(shù)的子區(qū)劃分結(jié)果

由表2的劃分結(jié)果可知, 對于節(jié)點(diǎn)權(quán)重較大的關(guān)鍵路口, 選擇較小權(quán)重的交叉口與其組成控制子區(qū), 通常權(quán)重較大的路口需要更多的空間來分散其交通流, 因此，本文一方面將路網(wǎng)劃分為權(quán)重較均衡的交叉口群；另一方面能夠為均衡控制策略提供初始解, 使得系統(tǒng)更快收斂至控制目標(biāo)。

表2 k=4各項指標(biāo)結(jié)果

在相同路網(wǎng)的控制策略下, 本文選取一種基于交叉口關(guān)聯(lián)度模型, 綜合考慮各路段關(guān)聯(lián)度及交叉口相似度值的分區(qū)方法[14]與本文方法進(jìn)行比較, 驗證不同分區(qū)方法對控制效果的影響, 選取路網(wǎng)的平均延誤和平均密度作為評價指標(biāo)。引用文獻(xiàn)[15-16]的均衡控制方法來評價不同子區(qū)劃分的路網(wǎng)控制效果(表3)?？梢钥闯? 傳統(tǒng)劃分方法的子區(qū)均衡指數(shù)偏高, 說明子區(qū)內(nèi)交叉口的密度方差較大; 從控制效果來看, 本文的分區(qū)方法能夠降低路網(wǎng)的平均延誤, 而且路網(wǎng)內(nèi)各路段的密度較傳統(tǒng)方法更均衡, 能夠有效緩解路網(wǎng)流量不均衡分布的現(xiàn)象, 提高了路網(wǎng)的效率。

表3 兩種方法劃分結(jié)果比較

同時, 將本文采用的啟發(fā)式方法與傳統(tǒng)k-means方法進(jìn)行比對, 在算法運(yùn)行過程中選取8個計算點(diǎn)對算法運(yùn)行的時間復(fù)雜度進(jìn)行計算, 如圖4所示?？梢钥闯? 采用啟發(fā)式方法在計算初始中心選取方法計算初始近似解時具有更低的時間復(fù)雜度, 即在相同計算精度下該方法用時更少, 尤其是隨著算法運(yùn)行了兩種方法的時間復(fù)雜度差持續(xù)增加, 表明啟發(fā)式方法具有更好的實時性。

圖4 兩種算法的時間復(fù)雜度對比

4 結(jié) 論

本文從交通路網(wǎng)控制子區(qū)劃分問題入手, 提出基于均衡k劃分的動態(tài)子區(qū)劃分方法。首先, 構(gòu)建交叉口和路段權(quán)重模型,并將路網(wǎng)抽象成為帶權(quán)拓?fù)鋱D; 再采用改進(jìn)的禁忌搜索算法進(jìn)行優(yōu)化求解;最后,利用實際數(shù)據(jù)將所提方法與已有方法進(jìn)行對比。結(jié)果顯示,由于采用啟發(fā)式方法為禁忌搜索算法提供初始近似解能夠有效降低其復(fù)雜度, 提高計算的實時性; 以任意子區(qū)內(nèi)節(jié)點(diǎn)權(quán)重之和差異最小及連接不同子區(qū)的邊權(quán)之和最小為目標(biāo), 從全局角度考慮路網(wǎng)均衡劃分, 能夠避免擁堵路口集中分布在一個子區(qū)的現(xiàn)象, 更好降低路網(wǎng)協(xié)調(diào)控制的難度, 避免多個高負(fù)荷交叉口聚集而影響路網(wǎng)運(yùn)行效率。