基于改進NSGA-Ⅱ的交叉口信號配時多目標優化

陳秀鋒,王瑞聰,陳咨羽,高夢圓,郭玉彤

(青島理工大學 土木工程學院, 青島 266525)

隨著城市化進程的進一步的加快和車輛占有率的增加,居民出行的需求也日益增加,平面交叉口堵塞問題已成為世界眾多城市交通面臨的主要問題之一。交通信號配時是改善城市道路擁堵、優化道路通行效率的重要策略[1]。目前,利用多目標優化措施解決信號交叉口配時優化問題逐漸成為熱點。劉暢等[2]以交叉口延誤、一氧化碳排放為優化指標,建立多目標信號配時優化模型,通過優化的粒子群算法求解模型;牟亮等[3]提出了車輛延誤-尾氣排放聯合優化目標模型,將車輛延誤和尾氣排放放到同一量級進行比較,通過Vissim仿真證實了模型的優越性;CHEN等[4]以延誤、停車和通行能力作為性能指標,約束條件為飽和度,根據交叉口特點賦予權重,通過遺傳算法進行信號配時。牟海維等[5]以車輛延誤、行人延誤、停車率、通行能力、尾氣排放作為性能指標,采用粒子群優化算法求解,仿真結果表明:相對于經典方法,極大地減少了交叉口的總延誤時間以及停車率,增加了路段通行效率;張小雨等[6]以延誤、通行能力、停車次數、汽油車排放及柴油車排放等5個目標建立多目標規劃模型,運用遺傳算法求解,通過實際交叉口驗證獲得了較好的控制效果;JIA等[7]提出了一個新穎的多目標配時模型,以人均延誤、汽車排放和交叉口飽和流量為目標,經過一種啟發式算法證實了模型的優越性;ZHANG等[8]以交通流為基本數據,結合交通流描述理論和尾氣排放估算規則,建立了一個信號配時問題的多目標模型,通過混合約束策略和NSGA-ⅡI框架相結合的方法,有效增加了多目標模型的求解質量和效率。但是,現有研究成果普遍將多個優化目標加權組合成一個綜合目標[9-11],或者通過轉約束法將其他控制目標包含在約束條件中,從優化理論的角度看,這仍屬于單目標優化模型[12],不能夠讓多個目標一起獲得最優解;另外,一些進化算法,如非支配排序的遺傳算法(NSGA-Ⅱ),存在多目標求解耗時、收斂精度差和難以獲得最優解的問題[13-14]。為此,本文設計了車輛延誤、停車次數、通行能力為評價指標的信號配時多目標優化模型,并提出了改進的NSGA-Ⅱ算法(NSGA-Ⅱ-DE)對模型進行求解,有效提升信號配時多目標優化算法的收斂速度和求解精度。

1 信號配時多目標優化模型

1.1 多目標函數

利用車輛平均延誤、平均停車次數和通行能力3個評價目標,來設計信號配時多目標優化模型。為了更好地比較指標的優化程度,采用比值法進行無量綱化處理,多目標函數表達式為

(1)

1.1.1 車輛平均延誤

通過Webster公式中的延誤計算[15],車輛平均延誤的組成可以分為2部分,分別為正常相位延誤、隨機延誤,相位車輛平均延誤模型為

(2)

式中:di為第i相位的車輛平均延誤;C為信號周期;λi為相位綠信比;xi為飽和度,即到達交通量與通行能力的比值;qi為進口道車流量。

隨機延誤相對較小,在實際計算中常忽略不計,本文采用式(2)前2項,得出相位車輛平均延誤為

(3)

相位車輛平均延誤加權得出周期車輛平均延誤:

(4)

1.1.2 平均停車次數

根據Webster相關理論,車輛在交叉口的停車次數為

(5)

式中:hi為相位平均停車次數;yi為進口道車輛到達率和飽和流量之比的比值。

得到加權相位平均停車次數周期平均停車次數為

(6)

1.1.3 通行能力

依據停車線原理[16],周期內通行能力計算公式為

(7)

式中:Si為某一相位的飽和流量。

1.2 約束條件

考慮到信號配時控制的實際情況,多目標優化模型對于目標的約束主要包含以下3個方面:①信號周期時長C介于最大周期和最小周期之間。②有效綠燈時間g處于最短綠燈時間和最長綠燈時間之間,并且周期長等于各相位有效綠燈長加上信號總損失時間L。③根據飽和度的定義,如果飽和度過小,可以采用傳統的信號配時方案解決需求,沒有必要應用多目標優化策略;如果飽和度過高,車輛的運行狀態會因為干擾而不穩定,從而進入過飽和狀態[17],通過以上分析,xi一般在0.75～0.90之間。

綜上,約束條件如下:

(8)

2 改進NSGA-Ⅱ算法

NSGA-Ⅱ算法是依靠遺傳算法并且利用快速非支配排序及精英策略的多目標優化算法,NSGA-Ⅱ中存在模擬二進制交叉算子,這種計算會導致收斂速度較慢、移動空間不足,存在陷入局部的最優解[18]的問題。本文采用DE算法的交叉變異策略改進NSGA-Ⅱ算法的子代生成,并且動態更新種群避免DE算法種群多樣性的不斷降低,在提高算法收斂速度的同時得到全局最優解。

2.1 交叉變異策略的改進

利用DE算法中的DE/Rand/1全局變異策略[19],對NSGA-Ⅱ算法的變異策略進行應用改進,在解空間內快速而廣泛地尋找最優解。對于第t代的每個向量xt,隨機選擇3個不同的目標向量x1,x2,x3,通過變異方案生成變異個體:

(9)

式中:F為變異率(差分向量的縮放因子)。

變異個體后,通過二項式分布交叉法得到實驗種群:

(10)

2.2 種群動態更新

(11)

種群動態更新策略有效改善了多樣性降低、局部收斂的情況,經過保留和更新,并不破壞優化過程。

NSGA-Ⅱ-DE算法的全部算法計算過程如圖1所示。

圖1 NSGA-Ⅱ-DE算法流程

1) 初始化種群,利用隨機函數生成多個初始個體種群Pt,根據多目標優化問題的維數,選擇種群數目,一般為n=10d,其中d為問題維數。設置最大迭代次數tmax,初始化迭代次數t=0;

2) 是否達到目標條件(t>tmax),如果達到目標條件則終止計算過程,得到帕累托(Pareto)最優解[20],不滿足會進行下一步;

3) 將快速非支配排序策略應用到種群中,指定每一層的適應度;

4) DE算法交叉變異算子產生下一代,與父代種群合并種群;

5) 定量評價種群多樣性,得到種群多樣度;

6) 若多樣性大于設定值, 執行下一步,否則根據公式(11)進行更新再執行下一步;

7) 在擁擠度距離的設計中,利用精英策略選擇N個個體成為新的父代種群Pt+1;

8)t=t+1,返回第2)步。

3 實例分析

3.1 交叉口數據采集

T形交叉口作為沿海景區常見的交叉口,高峰時段容易發生堵塞,為解決景區交通擁堵,選擇青島市嶗山區某T形交叉口進行實證分析,該交叉口三相位控制。交叉口現狀渠化及相位相序見圖2所示,表1為早高峰和晚高峰各進口道小時流量。

表1 早高峰和晚高峰時段小時流量 pcu/h

圖2 交叉口渠化及信號相位現狀

3.2 信號配時優化

NSGA-Ⅱ算法與NSGA-Ⅱ-DE算法Pareto最優解集如圖3所示,相對于圖3(a),圖3(b)Pareto最優解分布較為集中,因此具備更好的分布性。收斂性在2種算法之間差異不大。這個解集說明了3個目標之間的關系,從圖3可以看出,要想獲得較好的通行能力,車輛延誤與停車次數也需要控制在一定水平內。在多目標優化過程中存在一個最優的解集,即,使模型達到最優。

圖3 NSGA-Ⅱ和NSGA-Ⅱ-DE Pareto最優解

利用NSGA-Ⅱ-DE算法,得到最優信號周期時間為106 s,東西直行相位有效綠燈時間35 s,西進口道左轉相位有效綠燈時間40 s,北進口道左轉相位有效綠燈時間16 s,具體配時方案如圖4所示。

3.3 仿真分析

根據表1的交通數據,飽和流量設定為1650 pcu/h,通過Vissim軟件仿真工具[21-22]仿真交叉口,如圖5所示。為了更準確體現優化算法的優越性,對現狀配時方案、NSGA-Ⅱ配時方案以及本文配時方案進行對比,以平均停車延誤、停車次數和排隊長度作為參數,結果如表2所示。

表2 配時方案效果對比

圖5 交叉口仿真

由表2可知,相比于現狀信號配時方案,NSGA-Ⅱ-DE配時方案交叉口進口道的車輛平均延誤分別降低了27.47%,30.89%,23.31%,排隊長度分別降低了35.39%,33.56%,31.06%,平均停車次數分別降低了25.44%,31.79%,35.10%,優化效果明顯。同時,比較于NSGA-Ⅱ法優化方案,NSGA-Ⅱ-DE配時方案交叉口進口道的車輛平均延誤分別降低了14.76%,16.90%,10.47%,排隊長度分別降低了19.94%,21.05%,14.17%,平均停車次數分別降低了12.27%,20.83%,21.55%。結果表明,改進的NSGA-Ⅱ算法能夠有效實現車輛停車延誤、道路通行能力、車輛停車次數等多項性能指標的最優化控制。

4 結束語

本文將車輛延誤最小、停車次數最少和通行能力最大作為評價尺度對青島市嶗山區某交叉口配時優化。鑒于傳統的優化方法解決多目標問題存在缺陷,設計了一個經過改進的NSGA-Ⅱ算法,以此用來求解配時優化模型,并獲得了良好的Pareto最優解,最后通過Vissim軟件模擬證明了NSGA-Ⅱ-DE多目標優化模型的合理性和有效性。通過差分交叉變異來改進NSGA-Ⅱ子代,算法會增強全局尋優能力,收斂特性與魯棒性更好,而在實際的信號控制系統上,延誤和停車次數均明顯下降。但是本文以T形交叉口為例,普遍性不足,未來還需要以更為常見的十字交叉口作為驗證。