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

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

0 引 言

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

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

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

1 問題描述

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

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

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

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

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

(1)

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

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

(2)

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

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

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

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

(3)

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

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

(4)

2 基于禁忌搜索的路網(wǎng)子區(qū)動(dòng)態(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ù)、路段長(zhǎng)度、通行能力、路段旅行時(shí)間等基礎(chǔ)參數(shù), 計(jì)算交叉口與路段的權(quán)重系數(shù), 構(gòu)建路網(wǎng)的有權(quán)拓?fù)鋱D。

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

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

Step6: 算法停止準(zhǔn)則。子區(qū)劃分既要保證子區(qū)內(nèi)各交叉口的密度近似, 又要保證各子區(qū)間飽和度具有較大差異。因此選用密度相似性指標(biāo)來評(píng)價(jià)子區(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ū)的動(dòng)態(tài)調(diào)整

3 實(shí)驗(yàn)分析

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

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

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

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

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

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

在相同路網(wǎng)的控制策略下, 本文選取一種基于交叉口關(guān)聯(lián)度模型, 綜合考慮各路段關(guān)聯(lián)度及交叉口相似度值的分區(qū)方法[14]與本文方法進(jìn)行比較, 驗(yàn)證不同分區(qū)方法對(duì)控制效果的影響, 選取路網(wǎng)的平均延誤和平均密度作為評(píng)價(jià)指標(biāo)。引用文獻(xiàn)[15-16]的均衡控制方法來評(píng)價(jià)不同子區(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é)果比較

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

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

4 結(jié) 論

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