慕飛飛,　張惠珍

(上海理工大學(xué) 管理學(xué)院,上?！?00093)

?

基于遺傳算法的單點交叉口信號配時優(yōu)化

慕飛飛,張惠珍

(上海理工大學(xué) 管理學(xué)院,上海200093)

隨著社會的發(fā)展和人們生活水平的提高,中國的城市化進(jìn)程持續(xù)推進(jìn),機(jī)動車數(shù)量與日俱增,給人們帶來出行便利的同時也導(dǎo)致了許多交通問題,特別是交通擁堵嚴(yán)重困擾著人們的日常生活.交叉口是城市交通的瓶頸,其交通問題尤為嚴(yán)重[1].然而,受城市土地的限制,擴(kuò)建道路面臨著極大困難.因此,對交叉口信號控制進(jìn)行研究,是解決交通擁堵問題的有效途徑之一.雖然,國內(nèi)外很多學(xué)者已經(jīng)開始對線控、面控進(jìn)行研究,但缺乏實際應(yīng)用,單點交叉口交通信號控制系統(tǒng)依然在城市交叉口控制中廣泛使用[2-3].因此,解決交通問題的主要出發(fā)點依然是單個交叉口.另外,雖然對實時信號控制的研究開始得比較早,但是,目前很多道路信號配時還是根據(jù)簡單的Webster算法計算得到,計算結(jié)果不夠精確.相比較,智能優(yōu)化算法具有一定的先進(jìn)性,大量學(xué)者將各種優(yōu)化算法應(yīng)用到智能交通研究領(lǐng)域中,在理論研究方面取得了較多的成果.

20世紀(jì)70年代,英國學(xué)者Webster提出了ARRB,TRRL等優(yōu)化方法[4].此外還有一種應(yīng)用比較廣泛的YD模型,它考慮的信號配時指標(biāo)除了車輛的延誤外,還將信號周期、相位關(guān)鍵車流量、停車率及排隊長度考慮在內(nèi).除了建模方法上的創(chuàng)新,國外還開發(fā)了很多信號配時軟件系統(tǒng),如TRANSYT,Cabal[5],Synchro,SCOOT[6],MOTION以及SCAT等.

自2000年以來,國內(nèi)學(xué)者對交叉口信號配時方面的研究也獲得了很多成果.孫超等[7]分析了Synchro仿真系統(tǒng)中的信號配時優(yōu)化模型,并以廣州市天河北路與天河?xùn)|路交叉口為例對優(yōu)化模型進(jìn)行了驗證和分析.田豐等[8]針對單交叉口多相位交通流建立了動態(tài)信號配時模型,以交叉口車輛平均延誤最小為控制目標(biāo)并運用自適應(yīng)遺傳算法對信號配時問題進(jìn)行了優(yōu)化.程方[9]通過對城市交叉口交通流微觀仿真模型的分析,針對給定城市交叉口各路口的一些幾何參數(shù)和交通量,運用VISSIM進(jìn)行交通系統(tǒng)的建模和仿真,得到了最佳配時方案,并最終減少了路口的交通延誤.陳利紅等[10]將VISSIM仿真軟件與信號配時相結(jié)合而形成的信號交叉口優(yōu)化方法,對交叉口進(jìn)行了實例分析.朱曉寧等[11]建立了針對交叉口配時優(yōu)化的雙層規(guī)劃模型.

通過比較這些方法的可操作性及優(yōu)缺點,本文選取平均停車次數(shù)、交叉口平均延誤為效益評價指標(biāo),采用實數(shù)編碼的遺傳算法對單點交叉口信號配時進(jìn)行優(yōu)化,最后,以上海某一交叉口為例進(jìn)行了優(yōu)化和分析,證明了該方法的實用性.

1建立目標(biāo)函數(shù)

交通效益的評價指標(biāo)主要有:飽和度或道路的通行能力(實際到達(dá)交通量與通行能力之比)、停車次數(shù)、停車率、油耗、行程時間、延誤等.通常來說,對道路進(jìn)行交通信號控制的目的是要使交通網(wǎng)絡(luò)或單個交叉口獲得較好的交通效益[12].傳統(tǒng)的干道協(xié)調(diào)控制設(shè)計的目標(biāo)是獲取最大綠波寬度,針對現(xiàn)今社會大多數(shù)城市交叉口經(jīng)常出現(xiàn)交通擁堵的情況,可以采取減少車輛通過協(xié)調(diào)控制范圍內(nèi)各交叉口的總停車次數(shù)或總延誤時間[13]來改善交通擁堵問題.

綜上考慮,目標(biāo)函數(shù)包含兩部分:一部分為交叉口車輛的平均延誤;另一部分為交叉口的平均停車次數(shù).

1.1平均延誤

車輛的延誤時間是指車輛在受阻情況下通過交叉口所需時間與正常行駛同樣距離所需時間之差.在一個信號周期內(nèi),對于某一相位的進(jìn)口道來說,到來的車輛受到的延誤為周期車輛延誤,若一個路口包含了幾個信號相位,那么總延誤時間D可以表示為

(1)

在一個周期內(nèi)交叉口各相位延誤的加權(quán)平均值是車輛平均延誤時間,即

(2)

其中,根據(jù)Webster定時信號交叉口延誤公式,第i相位每輛車的平均延誤時間為

式(3)中,第一項為平均一致性延誤時間,它是由于紅、綠信號燈交替變化而引起的額外延誤,但交通流均勻到達(dá);第二項為平均隨機(jī)延誤時間,它是由交通流飽和度大于1時出現(xiàn)超載現(xiàn)象及交通流到達(dá)的隨機(jī)性引起的延誤.

1.2平均停車次數(shù)

(4)

一個周期內(nèi)交叉口的車輛平均停車次數(shù)為

(5)

1.3目標(biāo)函數(shù)

根據(jù)實際到達(dá)交通量,建立交叉口動態(tài)信號控制優(yōu)化模型,以控制周期內(nèi)平均停車次數(shù)和交叉口車輛的平均延誤作為目標(biāo)函數(shù),以信號周期內(nèi)的綠燈時間及周期時長為優(yōu)化參數(shù).通過運用Webster算法及遺傳算法確定控制周期內(nèi)各相位的最優(yōu)綠燈時間及周期時長,并對結(jié)果進(jìn)行比較,從而使總延誤及總停車次數(shù)目標(biāo)函數(shù)值最小,達(dá)到優(yōu)化的目的.

通過將停車次數(shù)和延誤作為目標(biāo)函數(shù),從而尋找目標(biāo)函數(shù)的最小值[14].目標(biāo)函數(shù)為

約束條件為

(7)

(8)

(9)

2最佳優(yōu)化配時算法

2.1Webster算法

Webster算法是計算信號配時的一種方法,在目前交通信號控制領(lǐng)域中比較常見.它最主要的思想是計算車輛延誤和最佳的周期時長,目標(biāo)函數(shù)為最小的車輛延誤時間,在進(jìn)行周期時長計算時,也是以車輛延誤為基礎(chǔ)的.

通過用近似解法,可以得到定時信號最佳周期時長[15]為

(10)

(11)

2.2遺傳算法

2.2.1實數(shù)編碼遺傳算法

遺傳算法(genetic algorithm,GA)是一種比較先進(jìn)的參數(shù)尋優(yōu)算法,通過運用仿生原理從而實現(xiàn)在解空間的快速搜索.遺傳算法對于不易建立數(shù)學(xué)模型的場合,其實用價值較為突出,現(xiàn)在廣泛應(yīng)用于解決大規(guī)模組合優(yōu)化問題,所以適用于交通系統(tǒng).

傳統(tǒng)的遺傳算法具有很多的優(yōu)點,比如可擴(kuò)充性較強(qiáng),思想簡單,可操作性好,魯棒性好,而且在對路網(wǎng)進(jìn)行協(xié)調(diào)控制時,不會出現(xiàn)“維數(shù)災(zāi)難”的問題.但是,傳統(tǒng)的二進(jìn)制編碼遺傳算法在求解連續(xù)函數(shù)時需編碼和解碼,會影響運行速度和精度,特別在搜索大空間范圍時更明顯.而實數(shù)編碼的編碼長度通常為變量個數(shù),而且適合于表示范圍很大的數(shù),便于較大空間的搜索,從而可以避免以上所涉及的問題,并能改善遺傳算法的計算復(fù)雜性.同時,實數(shù)編碼能夠有效避免二進(jìn)制編碼中所遇到的hamming懸崖問題.

2.2.2算法迭代步驟

a. 基本參數(shù)的設(shè)定:比如最大遺傳代數(shù)、種群大小、交叉概率、個體長度等.

b. 編碼:GA通過使用解空間里面的解數(shù)據(jù)來表示遺傳空間里的基因型串結(jié)構(gòu)數(shù)據(jù),然后再對數(shù)據(jù)進(jìn)行搜索.本文編碼長度為變量個數(shù),對所研究的問題進(jìn)行編碼,編碼采用實數(shù)編碼.

c. 初始種群生成過程:隨機(jī)情況下產(chǎn)生M個串結(jié)構(gòu)數(shù)據(jù)的初值,各個數(shù)據(jù)都是一個個體,這樣,由上述的M個個體便形成了一個種群.本文通過隨機(jī)產(chǎn)生預(yù)定種群數(shù)目的初始群體,將這些串結(jié)構(gòu)數(shù)據(jù)作為初始點開始進(jìn)化.

d. 適應(yīng)度的計算:目標(biāo)函數(shù)為f(x),目標(biāo)函數(shù)通過給每一個個體非負(fù)的價值數(shù),從而實現(xiàn)轉(zhuǎn)換目標(biāo)函數(shù)的函數(shù)值.同時,由于目標(biāo)函數(shù)求解的是最小值,因此可以通過動態(tài)函數(shù)懲罰法來構(gòu)造適應(yīng)度函數(shù),所構(gòu)造的適應(yīng)度函數(shù)為

(12)

式中,ε為任意常數(shù),ε>0,從而確保適應(yīng)度函數(shù)F(x)為正數(shù).

f. 交叉:采用實數(shù)交叉法,第l個染色體al和第k個染色體ak在j位的交叉操作方法為

(13)

式中,b是[0,1]區(qū)間的隨機(jī)數(shù).

g. 變異:采用非均勻變異.第i個個體的第j個基因aij進(jìn)行變異的操作方法為

(14)

式中:amax是基因aij的上界;amin是基因aij的下界;f(g)=r2(1-g/Gmax)2,r2是隨機(jī)數(shù),g是當(dāng)前迭代次數(shù),Gmax是最大進(jìn)化次數(shù),r為[0,1]區(qū)間的隨機(jī)數(shù).

3實例分析

選取上海崧澤大道明珠路十字交叉口,其中明珠路為南北走向,崧澤大道為東西走向.該交叉口為四相位控制,其相位控制方案如圖1所示,交叉口內(nèi)部渠化圖如圖2所示,交叉口現(xiàn)狀數(shù)據(jù)如表1所示.

圖1　相位圖

為了充分證明算法及模型的有效性,首先應(yīng)用傳統(tǒng)的Webster優(yōu)化算法進(jìn)行計算,其中每相位啟動損失時間為2 s,綠燈間隔時間為7 s,黃燈時間為2 s.在計算得出最佳周期及各相位有效綠燈時長后,再進(jìn)一步計算出平均延誤及平均停車次數(shù),最終結(jié)果如表2所示(見下頁).

圖2　交叉口渠化圖

進(jìn)口道名稱流向交通量/(pcu·h-1)東進(jìn)口左轉(zhuǎn)96直行690西進(jìn)口左轉(zhuǎn)174直行828南進(jìn)口左轉(zhuǎn)132直行528北進(jìn)口左轉(zhuǎn)198直行414

應(yīng)用Matlab語言進(jìn)行編程,最小信號周期為40 s,最大信號周期為120 s;第一、三相位最小綠燈時間為20 s,最大綠燈時間為80 s;第二、四相位最小綠燈時間為10 s,最大綠燈時間為40 s.程序中必要的一些參數(shù)分別設(shè)置為:種群大小為50,最大遺傳代數(shù)為500,染色體長度為4,交叉概率為0.8,變異概率為0.01.在500次運行優(yōu)化過程中,第269代開始收斂于最優(yōu)解,運行結(jié)果如表2所示.

從表中可以看出:應(yīng)用了遺傳算法進(jìn)行優(yōu)化之后,周期變?yōu)?18 s,比現(xiàn)狀縮短了19%;平均延誤變?yōu)?6 s/veh,比現(xiàn)狀下降了20%;平均停車次數(shù)變?yōu)?.736 1,比現(xiàn)狀下降了11%.同時還可以看到,遺傳算法所有的優(yōu)化指標(biāo)均優(yōu)于Webster算法的優(yōu)化指標(biāo).

由此可見,遺傳算法得出的優(yōu)化方案優(yōu)于現(xiàn)有控制方案及經(jīng)典的Webster算法得出的方案,在很大程度上提高了交叉口的服務(wù)水平.

表2　兩種優(yōu)化算法優(yōu)化結(jié)果與現(xiàn)狀對比

4結(jié)束語

研究了單點交叉口的信號配時優(yōu)化問題,通過建立一個效益評價目標(biāo)函數(shù),以相位綠燈時間、周期時長作為約束條件,并使用實數(shù)編碼遺傳算法進(jìn)行編程,應(yīng)用Matlab軟件進(jìn)行仿真優(yōu)化,最后得出了優(yōu)于現(xiàn)狀及傳統(tǒng)Webster算法的信號參數(shù),提高了交通效益，從而證明了優(yōu)化模型及遺傳算法的有效性.下一步將會對多相位十字交叉口在有非機(jī)動車和行人影響情況下的配時方案作進(jìn)一步研究,使配時模型可以應(yīng)用于更多的實際交通控制中；也將進(jìn)一步研究交叉口的線控、面控,并將使用更多先進(jìn)的智能算法進(jìn)行優(yōu)化.

參考文獻(xiàn)：

[1]顧靜航.城市軌道交通樞紐一體化布局及換乘研究[D].上海:同濟(jì)大學(xué),2008.

[2]曾松林.城市單交叉路口交通信號的控制方法研究[D].成都:西南交通大學(xué),2013.

[3]柴干,趙倩,蔣珉.城市智能交通信號控制系統(tǒng)的設(shè)計與開發(fā)[J].浙江大學(xué)學(xué)報:工學(xué)版,2010,44(7):1241-1246.

[4]李群祖,夏清國,巴明春,等.城市交通信號控制系統(tǒng)現(xiàn)狀與發(fā)展[J].科學(xué)技術(shù)與工程,2009,9(24):7436-7442.

[5]程婉燕.基于多智能體的城市交通信號控制的協(xié)調(diào)與優(yōu)化[D].福州:福建農(nóng)林大學(xué),2009:23-35.

[6]錢海峰.基于短時交通流預(yù)測的交通控制算法研究[D].北京:北京工業(yè)大學(xué),2009:37-45.

[7]孫超,徐建閩.城市單點交叉口的信號配時優(yōu)化研究[J].交通與計算機(jī),2008,26(6):6-10.

[8]田豐,邊婷婷.基于自適應(yīng)遺傳算法的交通信號配時優(yōu)化[J].計算機(jī)仿真,2010,27(6):305-308.

[9]程方.基于VISSIM的單點交叉口微觀模型仿真[J].軟件,2011,32(9):49-50.

[10]陳利紅,鄧璇.應(yīng)用VISSIM仿真進(jìn)行信號交叉口配時優(yōu)化[J].河北交通職業(yè)技術(shù)學(xué)院學(xué)報,2013,10(4):54-57.

[11]朱曉寧,隆冰.多路公交優(yōu)先交叉口配時優(yōu)化的雙層規(guī)劃模型[J].交通運輸工程學(xué)報,2014,14(1):103-111.

[12]姚佼,楊曉光.車路協(xié)同環(huán)境下城市交通控制研究[J].上海理工大學(xué)學(xué)報,2013,35(4):397-403.

[13]常云濤,彭國雄.基于遺傳算法的城市干道協(xié)調(diào)控制[J].交通運輸工程學(xué)報,2003,6(2):106-112.

[14]玄光男,程潤偉.遺傳算法與工程優(yōu)化[M].北京:清華大學(xué)出版社,2004.

[15]宋曉鵬,韓印,姚佼.基于NSGA算法的公交車輛調(diào)度優(yōu)化模型[J].上海理工大學(xué)學(xué)報,2014,36(4):357-361.

(編輯:丁紅藝)

上海理工大學(xué)學(xué)報

2015年第37卷第1～6期

摘要：以相位的周期時長、綠燈時間作為約束條件,平均停車次數(shù)、平均延誤最小作為優(yōu)化目標(biāo)函數(shù),建立了信號配時優(yōu)化非線性模型.以上海某一交叉口作為研究對象,將其交叉口的交通數(shù)據(jù)應(yīng)用于該模型中,以Matlab為模擬環(huán)境,應(yīng)用實數(shù)編碼遺傳算法對其求解.運行結(jié)果顯示:交叉口的信號周期由145 s變?yōu)?18 s,縮短了19%;車輛的平均延誤由45 s/veh變?yōu)?6 s/veh,下降了20%;車輛的平均停車次數(shù)由0.828 2變?yōu)?.736 1,下降了11%.研究結(jié)論表明,該方法得出的信號配時方案可以有效地減少停車延誤和停車次數(shù),優(yōu)于現(xiàn)有控制方案及傳統(tǒng)的Webster算法得出的方案,從而證明了此模型的實用性.

關(guān)鍵詞：交通控制; 單點交叉口; 遺傳算法; 平均延誤

Signal Timing Optimization at Single-Point Intersection Based on Genetic AlgorithmMU Feifei,ZHANG Huizhen

(Business School,University of Shanghai for Science and Technology,Shanghai 200093,China)

Abstract：A non-linear model for signal timing optimization was created to study the problem of four phases signal timing optimization at city’s single-point intersections.The minima of average delay and average stop times were regarded as the optimization objective function,the phase green time and the cycle time were regarded as the constraints and one of the Shanghai intersections was regarded as the research object.With the real-coded genetic algorithm in the Matlab simulation environment,the optimization problem was solved.By applying the method,the intersection cycle time changes from 145 s to 118 s,shortened by 19%,the average vehicle delay changes from 45 s/veh to 36 s/veh,shortened by 20%,and the average stops changes from 0.828 2 to 0.736 1,shortened by 11%.The results show that the signal timing plans drawn by using this method can reduce parking delay and stops effectively,thus it proves the usefulness of the model which is better than the existing control scheme and the Webster optimization algorithm.

Key words：traffic control; single-point intersection; genetic algorithm; average delay

中圖分類號：U 491.51

文獻(xiàn)標(biāo)志碼：A