基于模擬退火改進(jìn)人工魚(yú)群算法的交通信號(hào)配時(shí)優(yōu)化

許佳佳,李雪梅

(安徽三聯(lián)學(xué)院 1 交通工程學(xué)院,2 電子電氣工程學(xué)院,安徽 合肥,230601)

交通信號(hào)配時(shí)優(yōu)化對(duì)于減小交叉口的車均延誤和提升其通行能力有著重要的作用?；诖?相關(guān)學(xué)者對(duì)交叉口信號(hào)配時(shí)做了諸多研究和改進(jìn)。如:運(yùn)用傳統(tǒng)的信號(hào)周期配時(shí)方法進(jìn)行交叉信號(hào)配時(shí)優(yōu)化及通過(guò)軟件進(jìn)行仿真評(píng)價(jià)[1～3];通過(guò)建立動(dòng)優(yōu)化控制模型對(duì)交叉口的信號(hào)方案進(jìn)行動(dòng)態(tài)控制研究[4,5];基于交叉口平均延誤最小化目標(biāo)運(yùn)用遺傳算法進(jìn)行交叉口信號(hào)配時(shí)方案的求解與運(yùn)行效果評(píng)價(jià)[6～8];以及運(yùn)用熒火蟲(chóng)算法、蜜蜂算法和粒子群算法等智能算法進(jìn)行信號(hào)配時(shí)優(yōu)化[9～11]。由于傳統(tǒng)的信號(hào)配時(shí)方法無(wú)法適用過(guò)飽和流量的交叉口優(yōu)化[12],而單一智能算法在求解信號(hào)配時(shí)在解決實(shí)際問(wèn)題時(shí)因自身的不足影響計(jì)算結(jié)果和工作效率,如遺傳算法存在編碼不規(guī)范和粒子群算法易于陷入局部最優(yōu)解等問(wèn)題[6,7]。為此,筆者綜合考慮周期時(shí)長(zhǎng)和綠燈時(shí)間及飽和度等約束條件,以交叉口車均延誤最小為目標(biāo)函數(shù)構(gòu)建信號(hào)配時(shí)優(yōu)化模型,選擇收斂精度高的模擬退火算法和初值魯棒性強(qiáng)的人工魚(yú)群算法組合構(gòu)建模擬退火改進(jìn)人工魚(yú)群算法,對(duì)信號(hào)配時(shí)優(yōu)化模型進(jìn)行求解,并對(duì)現(xiàn)狀方案和3種不同智能算法求解方案情況下的交叉口整體車均延誤進(jìn)行對(duì)比,驗(yàn)證模擬退火改進(jìn)人工魚(yú)群算法的可行性與適用性。

1 模擬退火改進(jìn)人工魚(yú)群算法

模擬退火(Simulated Annealing,SA)算法是根據(jù)物理知識(shí)中固體退火原理所開(kāi)發(fā)的應(yīng)用于求解最優(yōu)化模型的一種通用的仿自然優(yōu)化算法,SA算法中將物質(zhì)的能量達(dá)到最低狀態(tài)的設(shè)定模擬成目標(biāo)函數(shù)并根據(jù)固體物質(zhì)的退火過(guò)程包括加溫、等溫和冷卻等3個(gè)過(guò)程進(jìn)行求解[13]。SA算法由于在等溫過(guò)程中采用了Metropolis準(zhǔn)則,能夠有一定的概率去接受惡化解,使其能夠跳出局部最優(yōu)而有著較好的全局搜索能力。

人工魚(yú)群(Artificial Fish-Swarm,AF)算法是基于魚(yú)的覓食、聚群、追尾、隨機(jī)活動(dòng)等行為所提出的一種應(yīng)用于求解最優(yōu)化模型的群智能優(yōu)化算法,在迭代優(yōu)化的過(guò)程中人工魚(yú)個(gè)體的最優(yōu)狀態(tài)會(huì)被進(jìn)行跟蹤和記錄,并且人工魚(yú)往往會(huì)在極值點(diǎn)特別是全局極值點(diǎn)進(jìn)行聚集從而找到最優(yōu)解[14～16],AF算法相較于傳統(tǒng)的求解方法具有分布處理的能力及參數(shù)和初值魯棒性強(qiáng)等特點(diǎn)。

AF算法雖然有著較好的全局收斂性,但由于感知能力和步長(zhǎng)參數(shù)是固定的,參數(shù)設(shè)置過(guò)大會(huì)導(dǎo)致在接近最優(yōu)解的附近來(lái)回振蕩而影響最終求解的精度,參數(shù)設(shè)置過(guò)小會(huì)導(dǎo)致在局部最優(yōu)解中無(wú)法跳出即未達(dá)到最優(yōu)值區(qū)域結(jié)束算法運(yùn)算,因此可嘗試?yán)肧A算法初值魯棒性和局部收斂精度高的特點(diǎn)對(duì)AF算法進(jìn)行改進(jìn),構(gòu)建模擬退火改進(jìn)人工魚(yú)群(SAAF)算法。首先,通過(guò)AF算法對(duì)每一代人工魚(yú)中的全局最優(yōu)個(gè)體進(jìn)行搜索,再對(duì)其運(yùn)用SA算法進(jìn)行退火模擬運(yùn)算以避免AF算法陷入局部最優(yōu)解的情況,并將SA算法的尋優(yōu)結(jié)果適應(yīng)度與AF算法進(jìn)行對(duì)比以更新人工魚(yú)群進(jìn)行迭代。SAAF算法的運(yùn)算邏輯過(guò)程見(jiàn)圖1。

2 交叉口信號(hào)配時(shí)優(yōu)化模型

根據(jù)美國(guó)通行能力手冊(cè)中對(duì)于交叉口車輛延誤的定義,現(xiàn)有交叉口各進(jìn)口各個(gè)方向車道的車均延誤由均勻延誤和隨機(jī)延誤兩部分組成,其中均勻延誤是指進(jìn)口道車輛均勻到達(dá)所產(chǎn)生的均勻延誤,隨機(jī)延誤是指進(jìn)口道車輛隨機(jī)到達(dá)并引起超飽和周期所產(chǎn)生的延誤,本次研究假設(shè)各交叉口各進(jìn)口車道各個(gè)方向的車輛到達(dá)類型隨機(jī),對(duì)應(yīng)的各個(gè)方向內(nèi)不同車道的車均延誤是相同的。針對(duì)現(xiàn)狀大部分十字型平面交叉口均采用的典型四相位配時(shí)方案,本次研究用di表示第i個(gè)相位的綜合車均信控延誤(i=1,2,3,4,分別代表東西直行、東西左轉(zhuǎn)、南北直行、南北左轉(zhuǎn)相位),單位為s/pcu;di j表示第i個(gè)相位中第j個(gè)進(jìn)口方向?qū)?yīng)車道的綜合車均信控延誤(i=1,2,3,4;j=1,2)(d11,d12,d21,d22,d31,d32,d41,d42), 單位s/pcu;di j z表示第i個(gè)相位中第j個(gè)進(jìn)口方向中第z種單項(xiàng)車均延誤(i=1,2,3,4;j=1,2;z=1,2;其中z=1代表均勻延誤,z=2代表隨機(jī)延誤),單位s/pcu;gi表示第i個(gè)相位的顯示綠燈時(shí)間(i=1,2,3,4),單位s;Si j表示第i個(gè)相位第j個(gè)進(jìn)口方向?qū)?yīng)的平均單一車道的飽和流率,單位pcu/h;yi表示第i個(gè)相位的黃燈時(shí)間(i=1,2,3,4),單位s;li表示第i個(gè)相位的車輛啟動(dòng)損失時(shí)間(i=1,2,3,4),單位s;t表示分析時(shí)段的持續(xù)時(shí)長(zhǎng),單位h,取0.25 h;e表示單個(gè)交叉口信號(hào)控制類型校正系數(shù),定時(shí)信號(hào)取e=0.5。下面以第1個(gè)相位中第1個(gè)進(jìn)口方向中的綜合車均延誤d11的均勻延誤d111和隨機(jī)延誤d112為例說(shuō)明延誤計(jì)算式,具體見(jiàn)式(1)(2)(3),其它相位和進(jìn)口方向車道的均勻延誤和隨機(jī)延誤可同理計(jì)算。

d11=d111+d112

(1)

(2)

(3)

交叉口整體的車均延誤數(shù)值越小代表交叉口的運(yùn)行效果越好,即車輛在經(jīng)過(guò)交叉口時(shí)平均延誤的時(shí)間越短越好,因此設(shè)定交叉口整體車均延誤最小化目標(biāo)函數(shù)。交叉口的信號(hào)周期的時(shí)長(zhǎng)需要設(shè)置合理。周期時(shí)長(zhǎng)過(guò)短會(huì)直接影響到車輛是否安全通過(guò)和行人能否安全通過(guò);而周期時(shí)長(zhǎng)過(guò)長(zhǎng)雖然能夠提升交叉口的通行能力,但提升的效率不明顯并會(huì)使通行延誤急速增長(zhǎng)。因此,在設(shè)置周期時(shí)長(zhǎng)時(shí)需要考慮下限和上限的約束,一般將周期時(shí)長(zhǎng)的范圍限定在40～180 s之間。同理,對(duì)于各個(gè)相位的綠燈時(shí)間也需要進(jìn)行上限和下限的約束設(shè)置。本次研究將各個(gè)相位綠燈時(shí)間的上限設(shè)置為100 s,下限的設(shè)置需要考慮車輛和行人通過(guò)交叉口的最短時(shí)間,用wimax表示為第i個(gè)相位中兩個(gè)對(duì)向方向車輛或行人通過(guò)交叉口需要經(jīng)過(guò)的最大距離,vc表示車輛通過(guò)的區(qū)間速度,vp表示行人通過(guò)的區(qū)間速度。因大部分情況下通過(guò)交叉口的損失時(shí)間與黃燈時(shí)間相近,此處對(duì)各相位最短綠燈時(shí)間進(jìn)行簡(jiǎn)化處理,對(duì)應(yīng)的直行相位因?yàn)橐紤]行人通行,其綠燈時(shí)長(zhǎng)的下限為wimax/vp,而對(duì)于只需考慮車輛通行的左轉(zhuǎn)相位綠燈時(shí)長(zhǎng)下限為wimax/vc。為了克服經(jīng)典Webster方法只適用于非飽和流量的情況,此處考慮將整個(gè)交叉口的飽和度作為約束條件進(jìn)入模型,根據(jù)交叉口優(yōu)化效果的經(jīng)驗(yàn)將飽和度設(shè)置在0.7～0.9的閉區(qū)間范圍內(nèi)?；谏鲜瞿繕?biāo)函數(shù)和約束條件,結(jié)合前述延誤計(jì)算理論中的定義構(gòu)建交叉口信號(hào)配時(shí)優(yōu)化模型,具體見(jiàn)式(4)。

(4)

式中:z為交叉口整體的車均延誤,單位s/pcu;qi j為第i個(gè)相位中第j個(gè)進(jìn)口方向的交通量,單位pcu;di j為第i個(gè)相位中第j個(gè)進(jìn)口方向的車均延誤,單位s/pcu;gi為第i個(gè)相位的顯示綠燈時(shí)間,單位為s;yi為第i個(gè)相位的黃燈時(shí)間,單位s;wimax為第i個(gè)相位中兩個(gè)對(duì)向方向車輛或行人通過(guò)交叉口需要經(jīng)過(guò)最大的距離,單位m;vc表示車輛通過(guò)交叉口的區(qū)間速度,單位m/s;vp表示行人通過(guò)交叉口人行橫道的區(qū)間速度,單位m/s;yi表示第i個(gè)相位的黃燈時(shí)間,單位s;li為第i個(gè)相位的車輛啟動(dòng)損失時(shí)間,單位s。

3 實(shí)例分析

以安徽省合肥市紫云路與金寨路相交的典型四相位十字型平面交叉口(以下簡(jiǎn)稱“紫金路口”)的交通流量數(shù)據(jù)為例,相位1對(duì)應(yīng)東西直行,相位2對(duì)應(yīng)東西左轉(zhuǎn),相位3對(duì)應(yīng)南北直行,相位4對(duì)應(yīng)南北左轉(zhuǎn),右轉(zhuǎn)不設(shè)專用相位(即車輛右轉(zhuǎn)不受信號(hào)控制),車道寬度>3 m,道路無(wú)縱坡,無(wú)自行車影響,大車比例很小不作特別分析,因此不考慮對(duì)飽和流率的影響與修正,確定一條直行車道的標(biāo)準(zhǔn)飽和流量為1 650 pch/h,一條直行車道的標(biāo)準(zhǔn)飽和流量為1 550 pch/h。該交叉口各方向流量與配時(shí)基礎(chǔ)數(shù)據(jù)見(jiàn)表1。

表1 安徽省合肥市紫云路與金寨路平面交叉路口各方向流量與配時(shí)數(shù)據(jù)

基于交叉口的現(xiàn)狀交通流量和配時(shí)數(shù)據(jù),考慮交叉口各個(gè)相位的啟動(dòng)損失時(shí)間為3 s,計(jì)算結(jié)果顯示,整體交叉口的車均延誤為202.81 s/pcu,表明車輛通過(guò)該交叉口時(shí)的擁堵情況較為嚴(yán)重。下面試驗(yàn)用SA算法和AF算法及SAAF算法進(jìn)行交叉口的信號(hào)配時(shí)優(yōu)化。

(1)SA算法的相關(guān)參數(shù)設(shè)置:隨機(jī)生成初始解,初始溫度T0=1 000,終止溫度Tend=0.001, 每次退火溫度下的迭代次數(shù)L=500,降溫速率q=0.9, 最大迭代次數(shù)count=100。

(2)AF算法的相關(guān)參數(shù)設(shè)置:人工魚(yú)的數(shù)量fishnum=100, 最大迭代次數(shù)MAXGEN=100,覓食行為中的最多試探次數(shù)try_number=30, 模擬魚(yú)感知半徑的感知距離visual=35, 擁擠度因子(模擬魚(yú)群的擁擠程度的擁擠度因子)delta=0.618, 最大移動(dòng)步長(zhǎng)step=4.5。

(3)交叉口延誤計(jì)算的其他相關(guān)參數(shù)設(shè)置:針對(duì)于交叉口信號(hào)配時(shí)的約束優(yōu)化模型中的約束條件要求,行人過(guò)街步行速度vp取1.5 m/s, 車輛通過(guò)交叉口的速度vc為3 m/s, 4個(gè)相位中兩個(gè)對(duì)向方向車輛或行人通過(guò)交叉口需要經(jīng)過(guò)最大的距離依次取40,50,30,50 m,各相位的綠燈損失時(shí)間均取3 s, 各相位的黃燈時(shí)間也設(shè)置為3 s。

基于交叉口的流量數(shù)據(jù)和相關(guān)的交叉口形式、交通流和信號(hào)配時(shí)的默認(rèn)設(shè)置參數(shù),代入上述交叉口信號(hào)配時(shí)的約束優(yōu)化模型從而實(shí)現(xiàn)模型的實(shí)例化,先分別運(yùn)用SA算法和AF算法對(duì)其進(jìn)行啟發(fā)式求解和計(jì)算延誤,再將兩種方法基于前述模擬退火改進(jìn)人工魚(yú)群算法的思路進(jìn)行組合并進(jìn)行實(shí)例模型的求解,最終得到單一智能算法和組合改進(jìn)算法的信號(hào)配時(shí)方案解及對(duì)應(yīng)的延誤數(shù)據(jù),具體的交叉口信號(hào)配時(shí)現(xiàn)狀與優(yōu)化方案及其運(yùn)行效果評(píng)價(jià)數(shù)據(jù)見(jiàn)表2。

表2 安徽省合肥市紫云路與金寨路平面交叉路口信號(hào)配時(shí)現(xiàn)狀與優(yōu)化方案運(yùn)行效果

試驗(yàn)結(jié)果表明,SA算法、AF算法和SAAF算法所得的信時(shí)配時(shí)方案中的時(shí)間數(shù)據(jù)之間較為接近,但相對(duì)于現(xiàn)狀信號(hào)配時(shí)方案有著較大變化,3種算法求解的信號(hào)配時(shí)方案對(duì)應(yīng)的交叉口整體的車均延誤分別為98.94,97.88,96.66 s/pcu,相較于現(xiàn)狀交叉口車均延誤均減小了50%以上,說(shuō)明通過(guò)智能算法進(jìn)行交叉口信號(hào)配時(shí)優(yōu)化的效果較為明顯,并且其中SAAF算法所得方案的車均延誤要更優(yōu)于單一的SA算法和AF算法(圖2)。

圖2 交通信號(hào)配時(shí)優(yōu)化3種算法迭代優(yōu)化過(guò)程

計(jì)算結(jié)果表明,3種不同的算法的迭代過(guò)程變化情況有著較大的差異(圖2)。SA算法因?yàn)槠淙炙阉髂芰Ρ憩F(xiàn)出迭代初期過(guò)程波動(dòng)程度較大,而AF算法基于其較強(qiáng)的搜索能力使得其初期解的結(jié)果較優(yōu)并且下降過(guò)程較為穩(wěn)定。而SAAF算法結(jié)合了兩種方法的優(yōu)點(diǎn),在迭代的初期即非常接近最優(yōu)解,在后續(xù)迭代過(guò)程中也表現(xiàn)非常穩(wěn)定的持續(xù)下降趨勢(shì),并且改進(jìn)后的算法歷代迭代所得到的信號(hào)配時(shí)方案對(duì)應(yīng)的交叉口整體車均延誤均優(yōu)于另兩種算法,表現(xiàn)出SAAF算法求解約束優(yōu)化模型的良好效果。

4 結(jié)論與討論

本次研究以交叉口車均延誤最小為目標(biāo)函數(shù)和周期時(shí)長(zhǎng)及綠燈時(shí)間等為約束條件構(gòu)建信號(hào)配時(shí)優(yōu)化模型,并基于SA算法對(duì)AF算法進(jìn)行改進(jìn)后對(duì)模型進(jìn)行求解與分析交叉口的通行效果改進(jìn)情況,得出以下結(jié)論:(1)AF算法由于其感知能力和步長(zhǎng)參數(shù)是固定的,會(huì)使其容易跳過(guò)最優(yōu)解和陷入局部最優(yōu)解,利用SA算法初值魯棒性和局部收斂精度高的特點(diǎn)進(jìn)行改進(jìn)可以提升其搜索全局最優(yōu)解的能力;(2)SA算法、AF算法和SAAF算法求解所得的信時(shí)配時(shí)方案中的時(shí)間數(shù)據(jù)之間較為接近,相對(duì)于現(xiàn)狀信號(hào)配時(shí)方案有著較大的優(yōu)化效果,并且SAAF算法的效果要優(yōu)于單一算法。(3)SA算法在迭代運(yùn)算的初期過(guò)程波動(dòng)程度較大,而AF算法初期解的結(jié)果較優(yōu)并且下降過(guò)程較為穩(wěn)定,SAAF算法在迭代的初期便能非常接近最優(yōu)解和穩(wěn)定下降趨勢(shì)表現(xiàn)出快速尋優(yōu)的能力。本次研究主要針對(duì)典型的平面單點(diǎn)十字交叉道口,對(duì)于其它類型的交叉口信號(hào)配時(shí)點(diǎn)控和多個(gè)交叉口的線控還有待進(jìn)一步論證和研究。