基于粒子群算法下的交叉口信號配時優(yōu)化

徐明杰，韓 印 （上海理工大學(xué) 管理學(xué)院，上海 200093）

0 引 言

當(dāng)下我國的機(jī)動車保有量日益增加，城市交通問題已經(jīng)成為一大難題。在城市道路網(wǎng)中，交叉口的暢行程度直接影響路網(wǎng)的服務(wù)與通行能力水平，而交叉口卻是發(fā)生擁堵的主要地段，因此對交叉口采取合理的優(yōu)化設(shè)計及控制是提高道路通行能力的重要手段[1]。優(yōu)化交叉口的方法有很多，其中優(yōu)化交叉口信號配時是最直接有效的方法，合理的信號配時可以有效降低交叉口的延誤，因此交叉口的信號配時優(yōu)化顯得尤為重要。

關(guān)于交叉口信號配時優(yōu)化，國內(nèi)外學(xué)者專家進(jìn)行了大量研究?？傮w而言可以分為2類方向，第一類是單純的針對單點交叉口進(jìn)行信號配時優(yōu)化，如：Mohajerpoor[2]等提出了一種基于沖擊波理論的計算交叉口延誤的方法，給出了一種新的最佳信號配時公式；Ceylan[3]通過周期和相位綠信燈時間和周期作為約束，總延誤和總停車次數(shù)最小為目標(biāo)，使用遺傳算法進(jìn)行求解，獲得最優(yōu)解；黃敏[4]通過分析傳統(tǒng)的交叉口信號配時方法，使用改進(jìn)的蟻群算法來進(jìn)行求解優(yōu)化；Yu[5]等將行人和車輛的總延誤作為目標(biāo)函數(shù)，且將目標(biāo)函數(shù)構(gòu)建成為凸函數(shù)獲得了全局最優(yōu)解；付珊[6]通過分析交叉口左轉(zhuǎn)待行區(qū)的設(shè)置條件，建立了交叉口左轉(zhuǎn)車道的延誤模型，并使用了遺傳算法進(jìn)行求解；王秋平[7]等通過分析單點交叉口的車流特性，建立以平均延誤、平均停車次數(shù)最少的多目標(biāo)函數(shù)，并分別使用遺傳算法、遺傳模擬退火算法進(jìn)行求解，上述研究側(cè)重于靜態(tài)交通流下的信號配時研究。第二類是考慮交通流的隨機(jī)性，針對單點交叉口的動態(tài)控制進(jìn)行研究，如：鄒娟[8]等通過改進(jìn)元胞傳輸模型，建立了適用于多個相位控制的交叉口信號配時優(yōu)化模型，采用了蜜蜂算法對其進(jìn)行動態(tài)配時優(yōu)化；王逸[9]等通過建立交叉口平均延誤為優(yōu)化目標(biāo)，以各個相位綠燈時間作為約束條件并采用了自適應(yīng)下的遺傳算法進(jìn)行求解；曹陽[10]則是建立了以交叉口車輛的平均延誤最小的模型，在進(jìn)行神經(jīng)網(wǎng)絡(luò)預(yù)測各進(jìn)口道短時間交通流到達(dá)情況前提下，基于模擬退火算法提出交通信號控制的動態(tài)配時方法；Yang[11]等為了降低車輛延誤，提出了一種基于改進(jìn)遺傳算法的交叉口協(xié)調(diào)控制信號的方法；此外，也有學(xué)者結(jié)合了VISSIM和SYCHRO的優(yōu)點，針對交叉口進(jìn)行信號優(yōu)化，如：陳東芳[12]通過把VISSIM和SYCHRO軟件結(jié)合起來進(jìn)行對交叉口信號優(yōu)化。在上述文獻(xiàn)中，大部分學(xué)者都是構(gòu)建目標(biāo)函數(shù)，使用當(dāng)下發(fā)展迅猛的智能算法進(jìn)行求解或者通過軟件仿真得出結(jié)論。然而，這些算法本身具有一定的復(fù)雜性，理解和操作起來也較為困難。相比而言粒子群算法具有程序簡單、收斂速度快、容易操作等特點；并且通過提高算法系統(tǒng)的穩(wěn)定性，不僅可以提高粒子群算法的穩(wěn)定性避免獲得隨機(jī)解，而且可以提高算法的全局搜索能力，防止早熟。因此本文將構(gòu)建以平均停車次數(shù)和平均延誤最小、交叉口通行能力最大的函數(shù)，并使用動態(tài)的加權(quán)系數(shù)使其成為單一目標(biāo)函數(shù)，然后使用改進(jìn)后的粒子群算法進(jìn)行交叉口信號配時優(yōu)化。

1 模型建立

交叉口信號配時的目標(biāo)就是要求獲得最大的通行能力、最小延誤、最小的停車次數(shù)、最短的排隊長度、車輛的油耗最低等，其中，最小延誤、停車次數(shù)、通行能力是評價交叉口運行狀況的重要指標(biāo)。韋伯斯特給出的最佳周期計算公式，是建立在以交叉口最小延誤為目標(biāo)的基礎(chǔ)上通過求導(dǎo)和近似計算得出的，并沒有綜合考慮到上述指標(biāo)，因此選取延誤、停車次數(shù)、通行能力作為模型的構(gòu)建部分。

1.1 韋伯斯特延誤模型

延誤是指車輛在受阻的情況下通過交叉口所需時間與正常行駛所需要的時間之差。計算交叉口延誤的模型有很多，常見的有HCM2000模型、韋氏延誤模型等。其中韋氏模型及其相應(yīng)的改進(jìn)模型被使用的頻率較高，其主要由2部分組成，一部分稱為均衡相位延誤，使用符號表示，它是根據(jù)穩(wěn)態(tài)理論得到的。另外一部分是隨機(jī)延誤，使用符號表示。計算公式分別為：

dij表示第i相位j個車道組的平均延誤，qij表示第i相位j個車道組的當(dāng)量車流量，那么整個交叉口的平均延誤d表示為：

1.2 平均停車次數(shù)

第i相位j個車道組的平均停車次數(shù)使用符號hij表示，計算公式為：

那么整個交叉口的平均停車次數(shù)h可表示為：

1.3 交叉口通行能力

第i相位j個車道組的通行能力使用符號Qij表示，計算公式為：

那么整個交叉口的通行Q能力計算為：

1.4 動態(tài)權(quán)重系數(shù)

分析上述模型的架構(gòu)過程不難看出，最后的模型是在共同的約束條件下的多目標(biāo)優(yōu)化問題，解決多目標(biāo)優(yōu)化問題一般有二種做法，一是分層序列法，二是把多目標(biāo)轉(zhuǎn)化為單一目標(biāo)的函數(shù)問題，本文采用第二種方法。把多目標(biāo)轉(zhuǎn)換為單目標(biāo)方法一般采取線性加權(quán)組合法，即根據(jù)各個目標(biāo)函數(shù)的重要程度，乘上權(quán)重系數(shù)，構(gòu)成一個目標(biāo)函數(shù)。關(guān)于權(quán)重系數(shù)的選取，大部分的學(xué)者都是人為的設(shè)置加權(quán)系數(shù)，這樣設(shè)置雖然易于求解但是不能反應(yīng)出交通流的動態(tài)性，廖詩琪[13]曾引入了隨著某一相位關(guān)鍵車道變化的動態(tài)權(quán)重系數(shù)，取得了良好的效果，但是不能夠反映出每個車道的變化情況，因此本文為改進(jìn)上述不足對權(quán)重公式進(jìn)行推廣。分別選取動態(tài)延誤權(quán)重系數(shù)、停車權(quán)重系數(shù)和通行能力權(quán)重系數(shù)。由這3個動態(tài)權(quán)重系數(shù)分別對i相位j個車道組的延誤、通行能力和停車次數(shù)進(jìn)行修正，并將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單一目標(biāo)問題。計算公式分別為：

其中：Y是各個相位的關(guān)鍵流量比之和，c是周期（s），是第i相位j個車道組的飽和流量。

1.5 配時模型

構(gòu)建如下的目標(biāo)函數(shù)：

即：

在模型中k為大于0的常數(shù)，為了求得通行能力的最大值，將其取倒數(shù)并乘上系數(shù)k，這樣就使得求通行能力目標(biāo)函數(shù)最大值變成為求最小值，L表示交叉口總損失時間。

2 粒子群算法

從上面的模型可以看出，信號配時模型是一個非線性的最優(yōu)化問題，解決這個問題有很多有效的辦法，不少學(xué)者使用了遺傳算法、蟻群算法等，這些算法雖然可以求解問題，但方法本身有一定的復(fù)雜性，而粒子群算法具有簡單、收斂速度快等特點，因此可以用于求解此模型。

粒子群算法是一種群體優(yōu)化算法，源自于鳥類捕食的啟發(fā)。粒子群算法首先在約束條件所圍成的可行區(qū)域范圍內(nèi)初始化一群粒子，每個粒子都代表優(yōu)化過程中的潛在解，每一個粒子使用位置、速度、適應(yīng)度值三項指標(biāo)表示該粒子特性，適應(yīng)度值由事先編好的適應(yīng)度函數(shù)計算獲得。適應(yīng)度值的大小用于評價粒子的好壞與否和確定粒子下一次更新位置與速度。粒子在解集域內(nèi)活動，通過追蹤個體極值Pbest和群體極值Gbest更新位置，粒子每更新一次位置，就計算適應(yīng)度值，然后通過比較新粒子適應(yīng)度值、個體極值、群體極值來更新個體極值和群體極值位置。

2.1 算法系統(tǒng)穩(wěn)定性改進(jìn)

和大部分群體智能算法一樣，粒子群算法雖然具有不少優(yōu)點但也存在不少缺點，其中最主要的問題是算法的不穩(wěn)定性。關(guān)于解決算法穩(wěn)定性的相關(guān)研究不是很多，解決辦法可以概括為2種，一種是在主程序中設(shè)置實驗次數(shù)，即將一個程序多次計算，取最后的平均值作為計算結(jié)果，另外一種就是對初始化種群的適應(yīng)度值進(jìn)行擾動，即對適應(yīng)度較大進(jìn)行恰當(dāng)縮小，適應(yīng)度較小進(jìn)行放大以均勻化初代群體，這樣不僅可以提高算法的穩(wěn)定性，還可以在一定程度上避免算法陷入早熟的情況，提高了算法的全局搜索能力。將上述方法結(jié)合起來使用，適應(yīng)度值更新公式為：

（k）表示第k代群體的平均適應(yīng)度值，（k）表示經(jīng)過縮放后j個個體的適應(yīng)度值，fj（k）表示k代群體第j個個體適應(yīng)度值，ε表示縮放度，取值范圍在［0.5,1］。

2.2 算法步驟

（1）首先生成滿足約束條件的粒子群和初始化粒子的速度。

（2）根據(jù)定義好的目標(biāo)函數(shù)計算初始化粒子的適應(yīng)度值。

（3）對適應(yīng)度值進(jìn)行擾動，計算方法參考2.1。

（4）找到并記錄初始化粒子中個體極值Pbest和群體極值Gbest，粒子位置。

（5）粒子通過個體極值和群體極值更新自身的速度和位置，計算更新后粒子的適應(yīng)度值。速度和位置更新公式分別為：

其中：w是慣性權(quán)重參數(shù)，其取值影響算法的收斂速度和全局尋優(yōu)能力；表示第k代粒子速度；表示迭代后粒子的速度；c1、c2是加速度因子（常數(shù)）；r1、r2是隨機(jī)數(shù)其取值范圍在［0,1 ］之間；表示迭代k次后粒子的個體最優(yōu)值；表示迭代k次后粒子的群體最優(yōu)值；表示迭代k次后粒子的位置。

（6）更新個體極值和群體極值。

（7）判斷算法是否滿足終止條件，如果滿足終止條件則輸出結(jié)果，否則重復(fù)執(zhí)行5、6、7步驟，直到滿足終止條件。

3 算例分析

本文選取了德州市臨邑縣的某十字形交叉口作為算例，并調(diào)查了其當(dāng)前的信號配時方案，晚高峰小時流量和路面渠化狀況，現(xiàn)狀的渠化圖如圖1所示，現(xiàn)狀流量如表1所示：

圖1 交叉口現(xiàn)狀渠化圖

表1 交叉口流量調(diào)查表

當(dāng)前的信號相位控制方案簡述如下：第一相位東西方向放行，第二相位南北方向直行，第三相位南北方向左轉(zhuǎn)。

在Matlab中編寫程序語言，相關(guān)約束參數(shù)、算法參數(shù)分別設(shè)置如下：其中第一、二相位最小綠燈時間為20s，第一、二相位最大綠燈時間均設(shè)置為60s，第三相位最小綠燈時間設(shè)置為10s，最大設(shè)置為40s，最小周期時長設(shè)置為36s，最大周期時長設(shè)置為120s，交叉口信號總損失時間L為12s，各個車道組的飽和流率取1 250pcu/h；算法中的參數(shù)做如下設(shè)置：最大的迭代次數(shù)為300代，粒子規(guī)模為200個，每個粒子有3個位置分量，分別表示周期，第一相位有效綠燈時長，第二相位有效綠燈時長，第三相位有效綠燈時長，加速度因子c1、c2均取值為1.49445，慣性權(quán)重w參數(shù)則不是固定值，它隨著迭代次數(shù)的改變而改變，其計算方法如下：

ws取值0.9，wend取值0.5，k表示第k次試驗，maxgen表最大的迭代次數(shù)。其中每個實驗設(shè)置運行100次，并將這100次的平均值作為最后的結(jié)果，這樣可消除群體算法的不穩(wěn)定性得出可靠的結(jié)果，最后的運行結(jié)果如表2所示，粒子群算法的收斂圖像分析如圖2所示，作為對比沒有進(jìn)行穩(wěn)定性改進(jìn)的算法收斂圖像分析如圖3所示。

從圖2可以看出在300次的迭代過程中改進(jìn)的粒子群算法于第216代開始收斂，運算結(jié)果如表2所示，從表2中結(jié)果可以發(fā)現(xiàn)，在使用粒子群算法進(jìn)行配時后交叉口平均延誤變?yōu)?3，較之現(xiàn)狀下降28%；平均停車次數(shù)變?yōu)?.76，較之現(xiàn)狀下降了9%；理論通行能力變?yōu)? 280，較之現(xiàn)狀提升了9%。同時可以看到粒子群在各方面的優(yōu)化結(jié)果均優(yōu)于Webster算法，體現(xiàn)了算法的優(yōu)越性。從表2中結(jié)果和圖2和圖3的算法收斂曲線圖對比中也可以看出，在進(jìn)行算法的穩(wěn)定性改進(jìn)后算法進(jìn)行了216次迭代計算趨于收斂，這驗證了改進(jìn)方法的可靠性，所得出的結(jié)果也基本避免了因為種群的隨機(jī)性而導(dǎo)致結(jié)果的不合理性。

表2 算法結(jié)果對比表

4 結(jié)束語

本文研究分析了交叉口的評價因素，構(gòu)建多目標(biāo)的數(shù)學(xué)模型，且引入各個目標(biāo)的權(quán)重系數(shù)使其轉(zhuǎn)化為單一目標(biāo)函數(shù)，最后使用了粒子群算法進(jìn)行求解，在求解過程考慮了算法系統(tǒng)的穩(wěn)定性，提高了結(jié)果的科學(xué)性，并獲得了良好的信號配時方案，證明了算法和構(gòu)建模型的可靠性。但是回顧研究發(fā)現(xiàn)，本文模型沒有考慮到排隊長度的約束，也沒有考慮到行人安全等因素，另外在求解多目標(biāo)的優(yōu)化問題的方法上還可以做出改進(jìn)，下一步將會對上述研究存在的不足進(jìn)行修正，并繼續(xù)結(jié)合智能算法進(jìn)行交叉口優(yōu)化，以期獲得良好的效益。