基于模擬退火改進人工魚群算法的交通信號配時優(yōu)化

許佳佳,李雪梅

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

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

1 模擬退火改進人工魚群算法

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

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

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

2 交叉口信號配時優(yōu)化模型

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

d11=d111+d112

(1)

(2)

(3)

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

(4)

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

3 實例分析

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

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

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

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

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

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

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

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

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

圖2 交通信號配時優(yōu)化3種算法迭代優(yōu)化過程

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

4 結(jié)論與討論

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