基于粒子群算法下的交叉口信號配時優化

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

0 引 言

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

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

1 模型建立

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

1.1 韋伯斯特延誤模型

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

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

1.2 平均停車次數

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

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

1.3 交叉口通行能力

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

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

1.4 動態權重系數

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

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

1.5 配時模型

構建如下的目標函數：

即：

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

2 粒子群算法

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

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

2.1 算法系統穩定性改進

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

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

2.2 算法步驟

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

（2）根據定義好的目標函數計算初始化粒子的適應度值。

（3）對適應度值進行擾動，計算方法參考2.1。

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

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

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

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

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

3 算例分析

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

圖1 交叉口現狀渠化圖

表1 交叉口流量調查表

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

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

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

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

表2 算法結果對比表

4 結束語

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