基于遺傳算法的交叉口信號配時優化研究

張 軍,劉克非

(安徽理工大學 1.人工智能學院;2.機械工程學院,安徽 淮南 232001)

城市道路作為城市中的筋脈,而交叉口更是各種混合車輛,行人聚集、轉向和疏散的必經之處。隨著我國城市化進程的持續推進和經濟的不斷發展,汽車保有量也逐年提升,交叉口處常常出現交通擁堵現狀,尤其是在大城市,現有的空間資源無法滿足現實巨大的交通通行需求,交通擁堵現象尤為突出,迫切需要解決。而平面交叉信號配時優化無需大規模改擴建平面交叉口的空間資源,卻能減小道路交通壓力,不失為一種費用低、見效快的行之有效的方法。所以通過交通信號控制與管理來解決當前交通問題是關鍵。

最基本的單點交叉口信號配時多采用固定信號配時,最經典也是當下最常用的是Webster算法,它是以平均車輛延誤最小作為唯一優化目標的信號配時方法,該方法對于高峰時期的情況存在著實際延誤大于計算延誤的問題。且單目標優化得到的配時方案不能夠滿足真實交叉口通行需求。在交通擁堵現象日趨嚴重以及節能減排意識深入人心的背景下,眾多研究者們便著手進行交通信號配時模型的全新研究。國外Soheil等[1]以車輛和行人總延誤時間最小為目標來優化單個交叉口的信號配時;Zhang等[2]以通行能力、延誤和尾氣排放為目標建立信號配時問題的多目標模型,利用NSGA-III方法對目標模型求解并通過對比證明了該方法的優越性;Yang等[3]人提出了一種基于改進遺傳算法的相鄰交叉口主干道協調信號控制方法,通過分析主干道交叉前車隊車頭和車尾遇到的信號狀態,建立以車輛長度,信號時間和相位差為優化參數的優化模型,優化求解表明改進遺傳算法優于傳統遺傳算法和標準代數方法;Park等[4]提出一種固定信號周期的隨機信號優化方法,以綠信比/周期長度、相位等為多目標進行同時優化。國內眾多研究者在信號配時優化方面也取得了許多進展,如伍尚昆等[5]利用改進的蟻群算法對交叉口平峰和高峰兩個時段進行了多目標信號配時優化并對模型進行了驗證,但平峰階段經典Webster算法所得總延誤時間最短。劉暢等[6]以平面交叉口的平均延誤和平均CO排放為目標,建立多目標信號配時優化模型,用粒子群算法求解信號配時。李振龍等[7]以車輛延誤、排隊長度及尾氣排放量三個評價指標,建立了平面交叉口信號配時最優模型,利用遺傳算法解非線性函數模型。

本文以交叉口車輛平均延誤,車輛平均停車次數和交通行能力為效益評價指標,并以淮南市某一典型交叉口為例,根據交叉口實際交通數據,采用遺傳算法優化交叉口信號配時,對現有方案,Webster算法和遺傳算法方案進行了比較,并分析了不同配時方案下交叉口通行效益變化。

1 建立多目標優化模型

1.1 優化目標的選取

交叉口交通效益的關鍵評價指標包括延誤、飽和度、車輛排隊長度、停車次數、油耗、通行能力和污染物排放等[8]。信號交叉口延誤指由交叉口處信號控制導致交通流不連續造成的車輛通行時間的丟失,包括均勻延誤、隨機延誤、過飽和延誤等。其中均勻延誤是指假設車輛均勻到達時產生的延誤;所謂隨機延誤,就是指信號周期內車輛到達的隨機波動性產生的延誤;過飽和延誤是指車輛數大于交叉口通行能力時,滯留車輛額外產生的延誤[9]。延誤作為評價交叉口服務水平、車輛通行效率的一個重要指標,既體現了交叉口信號控制方案的合理性,也能體現道路渠化設計的優劣。通行能力又稱道路容量,是指道路的某一斷面在單位時間內通過車輛的最大數量,數據表明,交通擁堵大多是由于平面交叉口的通行能力不足造成的,故提高通行能力是提高交通效益和道路利用率的關鍵。停車次數是指車輛通過交叉口時由于信號控制造成停車的次數,即車輛在受阻時的停車程度,停車次數的大小還和延誤、飽和度、道路通行能力、油耗、尾氣排放等指標有著密切的關系。為提高車輛行車效率,節能減排,改善駕駛員的駕駛舒適度,本文將交叉口車輛平均延誤,平均停車次數和通行能力三個評價指標作為優化目標,構建非線性模型,優化交叉口信號配時。

1.2 平均延誤模型

本文選用的延誤模型為Webster延誤,如式(1)所示[10]。

(1)

式(1)中,λ為綠信比;y為實際交通量與飽和流量之比;x為飽和度;q為實際交通量。

根據Webster延誤公式,第i相位每輛車的平均延誤時間如式(2)所示。

(2)

一個周期內交叉口的車輛平均延誤時間如式(3)所示。

(3)

1.3 平均停車次數模型

停車次數h是指車輛通過交叉口,由于信號控制導致停車的次數。第i相位車輛平均停車次數hi如式(4)所示[11]。

(4)

一個周期內交叉口的車輛平均停車次數如式(5)所示。

(5)

式(4)和式(5)中,gei為第i相位有效綠燈時間;C為信號周期;xij為第i相位第j進口道飽和度;qi為i相位交叉口實際交通流量。

1.4 車輛通行能力模型

單條車道的通行能力如式(6)所示[12]。

(6)

式(6)中,Qij為i相位第j車道通行能力;Sij為i相位第j車道飽和流量;gi為第i相位有效綠燈時長;C為信號周期。

交叉口通行能力Q為單條車道通行能力的和,如式(7)所示。

(7)

式(7)中,n為相位數,m為車道數。

1.5 目標函數模型

本文根據實際交通需求,將交叉口車輛平均停車延誤,平均停車次數,通行能力作為優化目標,信號周期內各相位綠燈時間及周期時長作為約束,尋找目標函數的最小值。由于交叉口的交通狀態是不斷變化的,考慮到不同的交通流量,其交叉口平均車輛延誤,平均停車次數和通行能力對交叉口綜合效益的影響程度不同,所以引入a、b、c作為加權系數,由于要求的是目標函數的最小值,所以延誤和停車次數應該越小越好,通行能力應該越大越好,故目標函數中取通行能力的倒數。考慮到3個目標的單位均不同,故對三者進行歸一化處理,目標函數如式(8)所示。

(8)

式(8)中,f(x)為目標函數;L為總延誤時間;C為信號總周期時長;gi為各相綠燈時長;gimax和gimin為各相綠燈時長的最大和最小值;Cmax和Cmin為信號燈一個周期時長的最大和最小值;a、b、c分別為優化目標延誤,停車次數和通行能力的權重系數,D0、N0、H0為相應優化目標歸一化的初始值。

2 單點信號交叉口配時優化

2.1 Webster配時優化算法

(1)飽和流量指一次連續時間內連續車輛通過交叉口進口道停車線的最大流量,即連續車隊加速到正常行駛速度時,一定時間內通過進口道停車線的穩定車流量,用S表示,單位為pcu/h。飽和流量S如式(9)所示。

(9)

式(9)中,ht車頭時距,一般為了安全,車頭時距取2s以上。

(2)總損失時間L,如式(10)和式(11)所示[13]。

L=tR+4·tL

(10)

tL=ts+tb

(11)

式(10)和式(11)中,tR為全紅時間;tL為損失時間;ts為汽車起動損失時間;tb為制動損失時間,取1s。本文不設全紅時間。

(3)流量比yi和流量比之和Y,如式(12)和式(13)所示。

(12)

(13)

式(12)和式(13)中,yi為各相位交通流量比;q為實際交通量,單位為pcu/h;Y為所有相位關鍵車流的流量比之和。

(4)最佳周期C0如式(14)所示。

(14)

(5)有效綠燈時間Gei和gei,如式(15)和式(16)所示。

Gei=C0-L

(15)

(16)

式(15)和式(16)中,Gei為總有效綠燈時間;gei為各相位有效綠燈時間。

(6)各相位綠燈時間,如式(17)所示。

gi=gei+tL-ty

(17)

式(17)中,gi為第i相位的綠燈顯示時間;ty為黃燈時長,一般取3s。

2.2 遺傳算法

遺傳算法是受自然界物種進化啟發尋找全局最優解的算法。一般適用于求解比較復雜的多目標優化問題;通過適應度值評價搜索空間中的多個解,避免陷入局部最優;引入交叉算子和變異算子,能夠自適應獲取和指導優化的搜索方向。

遺傳算法優化流程:

(1)確定遺傳參數:種群規模、染色體長度、最大迭代次數、交叉概率、變異概率等。

(2)編碼:選用實數編碼,克服了二進制編碼搜索空間急劇擴大,編碼長度冗長以及尋優、收斂效率低下的問題。

(3)生成初始種群:隨機產生M個個體的集合即為種群,本文初始種群數為50。

(4)計算適應度值:通過適應度函數計算種群中所有個體的適應度,評價個體優劣,選擇適應度值較大的遺傳至下一代,淘汰適應度值小的個體。適應度函數的選擇對遺傳算法的收斂速度及尋優效果會產生直接影響。

由于適應度函數非負,故目標函數不能簡單的等于適應度函數,本文提出改進,如式(18)所示。

(18)

式(18)中,F(x)為改進后的適應度,f為傳統適應度,α取值在(0,1)之間,fmin為當前迭代種群中個體適應度的最小值,fmax為當前迭代種群中個體適應度的最大值。當前迭代下|fmax-fmin|越小,F(x)取值范圍越大,防止計算時在最優解附近擺動,提高收斂效率;反之F(x)取值范圍越小,防止群體中存在過大個體誤導算法搜索方向而陷入局部最優。

(5)選擇:選用精英保留策略和輪盤賭選擇將結合的方法,保留精英個體以免在遺傳算法過程中被干擾。算法早期精英個體留存數較少,以防留存數過多產生早熟現象,算法后期逐量添加留存數目,讓更多適應度高的個體直接留存至下一代,提高算法的收斂效率。輪盤賭選擇中染色體在種群中被選中的概率如式(19)所示。

(19)

式(19)中,fi為個體i的適應度值,pi為個體i被選中的概率。

(6)交叉、變異:采用固定的交叉概率和變異概率難以保證群體的多樣性和收斂效率,本文采用自適應交叉算子和變異算子。

自適應交叉概率pc如式(20)所示。

(20)

自適應變異概率pm如式(21)所示。

(21)

式(20)和式(21)中,famx為種群中最大適應度;fmin為種群中最小適應度;favg為種群適應度的均值;f′為交叉的兩個個體中較大的適應度;f為變異個體適應度;a1,a2,a3,a4在(0,1)之間。

(7)終止條件:達到終止條件時算法結束,不滿足終止條件時則返回步驟5。本文選擇的終止條件為達到最大迭代次數N=100。

3 實例分析

選擇淮南市區龍湖南路與朝陽中路交叉口作為研究對象,其中東、西、南、北進口道均為4車道且都是1條左轉,2條直行,1條右轉車道。朝陽中路為東西走向,龍湖南路為南北走向,自東向西和自西向東的進口道均設有左轉待行區。由于該交叉口位于淮南市商業中心,周邊有淮南商貿、淮南時代廣場、新世界休閑生活廣場、八佰伴、大金新百購物中心、龍湖中學以及多個小區,特別是在晚高峰人流量大,常發生交通擁堵現象。針對以上問題,本文采用人工觀測法,選擇晚高峰(pm5:30～pm6:30)1小時,實測交叉口交通數據,通過信號配時優化減少車輛延誤和停車次數,提高交叉口通行能力。圖1是使用SUMO軟件繪制的交叉口平面示意圖。交叉口由四個相位控制,信號配時如表1所示。

表1 信號配時

圖1 交叉口平面示意圖

經過實地觀測,第一相位綠燈時間為30s,第二相位綠燈時間為28s,第三相位綠燈時間為37s,第四相位綠燈時間為33s,綠燈間隔時間為3s,交叉口一個周期的時長為40s。根據車輛折算系數(《城市道路設計規范(037CJJ-2012)》),將測得車流按照表2的折算系數折算成標準當量,高峰小時交通流量如表3所示。

表2 車輛折算系數

表3 交叉口高峰小時交通量

3.1 Webster配時優化

首先使用傳統Webster配時優化,通過公式計算得出各相位有效綠燈時長和最佳周期,再利用實測的表3交叉口高峰小時表統計數據,使用SUMO軟件仿真算出各評價指標的值。

3.2 遺傳算法

遺傳參數:群體規模=50,迭代次數=100,個體長度=4,總延誤時間L=12s,約束條件如式(22)所示。Webster和遺傳算法優化結果如表4所示。

表4 算法優化后的結果比較

(22)

從表4中可以看出遺傳算法得出的結果優于傳統Webster算法,且經過遺傳算法優化后,交叉口周期時長由原有配時的140s減少到107s,下降了23.57%,平均延誤時間由原先的52.48s減少到42.03s,下降了19.89%,平均停車次數由0.8629次/輛減少到0.7844次/輛,下降了9.1%,通行能力由4398.3pcu/h提高至4832.2pcu/h,比原有配時方案提高了9.86%。通過應用Matlab編程實現遺傳算法迭代過程如圖2所示。

圖2 遺傳算法迭代過程

結語

本文分別研究了單點交叉口信號配時的Webster和多目標遺傳算法配時優化,構造目標函數模型,以各相位綠燈信號時長和周期時長為約束,以平均延誤、平均停車次數、通行能力為效益評價指標,通過現有配時方案、Webster算法、遺傳算法三種方法計算的評價指標對比分析。研究表明,經遺傳算法優化后的交叉口信號周期從140s變為107s,減少了23.57%,車輛平均延誤時間從52.48s變為42.0371s,減少了19.89%,車輛平均停車次數從0.862次/輛變為0.7844次/輛,減少了9.1%,通行能力從4398.3pcu/h提高至4832.2pcu/h,提高了9.86%,能夠有效減少停車延誤及停車次數,縮短信號周期,比已有控制方案和傳統Webster算法方案更好,使用遺傳算法配時方案可以有效緩解城市交叉口交通擁堵問題。