基于量子粒子群算法的實(shí)時(shí)多交叉口信號控制

嚴(yán)麗平，張默可，郭成源，朱爐龍

(華東交通大學(xué)軟件學(xué)院，江西 南昌330013)

1 引言

隨著城市交通控制技術(shù)的不斷發(fā)展，目前已達(dá)到車車、車路等之間的信息交互和共享，以及部分感知、決策協(xié)同和數(shù)據(jù)融合，其中交叉口的信號控制在城市交通控制中起到關(guān)鍵作用。國內(nèi)外對交通信號控制的研究主要從點(diǎn)、線、面三個方面展開，其中對于單點(diǎn)交叉口控制以及干道協(xié)調(diào)的研究較為成熟，部分城市開始轉(zhuǎn)向搭建大型的區(qū)域性智能交通控制系統(tǒng)。因此，從單個交叉口的控制，到干道的聯(lián)動以及交叉口群的協(xié)調(diào)控制，都是交通信號控制關(guān)鍵的研究方面。如果按控制范圍劃分，城市交通信號控制可以分為三類[1]：單點(diǎn)控制、干線控制和區(qū)域控制。

本文重點(diǎn)研究多交叉口控制的信號配時(shí)優(yōu)化，能適用于由交錯環(huán)繞的城市干道組成的復(fù)雜道路網(wǎng)結(jié)構(gòu)。目前的多交叉口形成的干線和區(qū)域控制系統(tǒng)雖然還處于不斷發(fā)展和完善的過程中，但是通過實(shí)踐已經(jīng)取得了比較好的應(yīng)用效果。

Furth[2]等人探討交通訊號的協(xié)調(diào)如何在雙向交通干線上創(chuàng)造或限制超速機(jī)會，提出了兩項(xiàng)措施超速行駛的機(jī)會：無約束的車輛，同時(shí)具有多個交叉點(diǎn)的集群可以產(chǎn)生有效的速度增大調(diào)節(jié)，但該方法在實(shí)際應(yīng)用中對車路協(xié)同的環(huán)境要求較高，還需進(jìn)一步測試。Lu等人[3]通過分析交叉口與交通流參數(shù)之間的交通相關(guān)性，來闡明路網(wǎng)的拓?fù)浣Y(jié)構(gòu)。建立了基于路網(wǎng)拓?fù)浣Y(jié)構(gòu)的交叉口重要性估計(jì)模型。然后通過深度優(yōu)先級搜索，設(shè)計(jì)了區(qū)域交通信號協(xié)調(diào)方法。該方法能較為精準(zhǔn)找出解決方案，占用空間小，但往往時(shí)間上存在耗費(fèi)，效率在飽和流量路口不是很高。

本文提出的模型采用到的量子粒子群信號配時(shí)優(yōu)化方法，是結(jié)合相關(guān)配時(shí)優(yōu)化方法引申而來。當(dāng)前應(yīng)用到交通配時(shí)較為廣泛的智能方法有遺傳算法[4]，粒子群算法[5]，模擬退火[6]等智能算法，如Dong[7]等人提出了一種模擬退火粒子群算法，它有效地顯示了在處理城市交通信號定時(shí)的優(yōu)化。張?zhí)m[8]等人以綠波系統(tǒng)為對象，運(yùn)用PSO算法優(yōu)化所提出的交通信號控制器，減小車輛延誤并提高效率。然而這些方法參數(shù)難以控制，不能保證一次就收斂到最優(yōu)值，一般需要多次嘗試才能獲得。

針對以上問題，為了保證更快速找到全局最優(yōu)，本文引進(jìn)量子計(jì)算更新方式，增大搜索能力，同時(shí)把該算法融合到多交叉口協(xié)調(diào)控制模型中，建立區(qū)域通行效率與所有信號燈配時(shí)的關(guān)系。

2 多交叉口實(shí)時(shí)信號控制模型

通常情況下，多交叉口信號配時(shí)模型可分為干線控制和區(qū)域控制。區(qū)域也可視為多條干線的組成。本文先從單個交叉口進(jìn)行信號分析，再“以點(diǎn)帶面”輻射到區(qū)域信號控制。圖1為單個交叉口的相位分布。交通信號相位指一個交叉口幾個方向上的交通流組合得到的通行時(shí)序。在交叉口設(shè)定好車輛到達(dá)率以及每個相位的駛離率，這樣確定不同的信號配時(shí)策略。

圖1 四相位交叉口

針對以區(qū)域?yàn)閷ο蟮亩嘟徊婵诘那闆r，本文設(shè)計(jì)一種實(shí)時(shí)路口協(xié)調(diào)控制(Real-time Intersection Coordination Control，RIC2)模型。如圖2所示，它可分為兩個組成部分。第一部分是多交叉口信號控制模型，用來模擬在信號控制下交通網(wǎng)上的車輛行駛狀況，以便計(jì)算在一組給定的信號配時(shí)方案作用下實(shí)時(shí)交通路網(wǎng)的運(yùn)行指標(biāo)，其中根據(jù)路網(wǎng)中車輛平均延誤時(shí)間及停車次數(shù)，還可以設(shè)計(jì)出車流總耗能計(jì)算方法。第二部分是優(yōu)化過程，改變信號配時(shí)方案并確定指標(biāo)是否減小，經(jīng)過反復(fù)試算求得最佳配時(shí)方案，達(dá)到一個延誤最小且效率最高的結(jié)果。

圖2 RIC2模型的基本構(gòu)成部分

RIC2模型旨在使得整個城市交通路網(wǎng)取得較好的交通效益，既能保證交通路網(wǎng)的暢通，又能降低車輛的能源耗費(fèi)。因此，本文主要以車輛延誤、停車次數(shù)、排隊(duì)長度、油耗等作為指標(biāo)，來評價(jià)信號控制交叉口的交通效益。

1)延誤時(shí)間

一般指交叉口進(jìn)道口車輛因信號控制或某些車流沖突，帶來的時(shí)間損失。延誤也是一個重要的評價(jià)參數(shù)，來衡量交叉口信號控制性能。為了更好比較模型帶來的優(yōu)化效果，本文不考慮隨機(jī)延誤，而是取平均延誤來進(jìn)行計(jì)算

(1)

其中di表示一個周期內(nèi)第i個相位的平均延誤時(shí)間，λ是有效綠燈時(shí)長與周期之比，也成綠信比。c為交叉路口的周期時(shí)長，pi是交叉口中第i個相位的交通流量與飽和流量的比。那么總延誤D計(jì)算式為

(2)

式中qi第i相位的交通流到達(dá)率。

2)停車次數(shù)

采用經(jīng)典的Akcelic公式[9]，第i個相位的平均停車次數(shù)hi(次)為

(3)

3)排隊(duì)長度

在一個信號周期內(nèi)，平均各個車道排隊(duì)長度，每條車道上最長排隊(duì)長度取該車道綠燈相位起始長度。其中第i個周期平均排隊(duì)長度的指標(biāo)與平均延誤是一樣的，在飽和交通流和非飽和交通流時(shí)之間進(jìn)行計(jì)算時(shí)會有變化。

另外，有關(guān)平均行駛路程、油耗、碳排放等指標(biāo)，本文不作詳細(xì)分析。如圖3所示，本文建立一個多交叉口小區(qū)域作為研究目標(biāo)，每個交叉口都標(biāo)注序號，方便計(jì)算以區(qū)域?yàn)槟繕?biāo)的整體平均延誤。

圖3 多交叉口區(qū)域交通局部網(wǎng)

在路口車隊(duì)獲得通行權(quán)時(shí)，發(fā)生的離散狀態(tài)會對排隊(duì)產(chǎn)生一定影響。本文在RIC2控制模型中嵌入了Roberston車輛離散模型，來快速預(yù)測計(jì)算從上游交叉口獲得通行權(quán)的交通流抵達(dá)下游交叉口的流率。該表達(dá)式如下：

f1(t+βT)=μ×f0(t)+[(1-μ)×f1(t+βT-1)]

(4)

μ=(1+αβT)-1

(5)

該式中，f1(t+βT)是t+βT時(shí)刻所測算的交通流率，f0(t)指t時(shí)刻車輛流率，T是車輛在交叉口間路段的行程時(shí)間，β是經(jīng)驗(yàn)系數(shù)，一般取0.8；μ是平滑因子；α車隊(duì)離散系數(shù)，取0.35。0.35也算是經(jīng)驗(yàn)系數(shù)，在城市交通通常情況下，該取值表達(dá)車輛離散程度較為準(zhǔn)確。為了更便于協(xié)調(diào)控制，各信號交叉口周期取相同值。

另外，隨著無線傳感、圖像識別等技術(shù)的快速發(fā)展和日趨成熟，獲得路段車輛的基礎(chǔ)參數(shù)不再是技術(shù)難點(diǎn)。在本文的控制方案中加入了“溢出截流”的約束控制，即路網(wǎng)交通流數(shù)據(jù)出現(xiàn)過飽和情況時(shí)，當(dāng)下游交叉口的相應(yīng)車道達(dá)到較大容量時(shí)，與之相關(guān)聯(lián)的上游交叉口車道截流，不再放行。

3 控制模型中的優(yōu)化算法

3.1 量子粒子群優(yōu)化算法

首先，粒子群算法是一種經(jīng)典的群智能演算計(jì)算方法，起源于鳥類對捕食的模擬[10]，廣泛應(yīng)用于各個領(lǐng)域，如函數(shù)優(yōu)化、通信信道組合優(yōu)化等。圖像處理以及用于訓(xùn)練神經(jīng)網(wǎng)絡(luò)進(jìn)行交通事件檢測。但在有些工業(yè)方面，運(yùn)用粒子群算法往往會出現(xiàn)局部過早收斂現(xiàn)象，造成求解不穩(wěn)定。為了能完善這一問題，研究人員引進(jìn)量子計(jì)算與粒子群結(jié)合，旨在增大全局搜索能力。

量子粒子群優(yōu)化(Quantum Particle Swarm Optimization，QPSO)算法取消了粒子的移動方向?qū)傩?，相比較于粒子群算法，粒子位置的更新跟該粒子之前的運(yùn)動沒有任何關(guān)系，是量子編碼與量子門計(jì)算進(jìn)行更新，這樣就增加了粒子位置的隨機(jī)性，避免發(fā)生局部過早收斂。

在量子粒子群算法中，設(shè)搜索空間為N維，種群的規(guī)模M，xit為第i個粒子的位置，引入的新名詞mbest表示pbest的平均值，即平均的粒子歷史最好位置。pbest表示歷史最優(yōu)值，Pi(t+1)=(Pi1(t)，Pi2(t)…，Pin(t))，全局最好位置gbest為：Gi(t+1)=(Gi1(t)，Gi2(t)，…Gin(t))，G(t)=pg(t)。

QPSO算法過程具體描述如下：

算法1：QPSO

初始化 i=1to M

If f(Xi(t))

pg(t)=minpi(t)

計(jì)算mbest

進(jìn)行位置更新

For n=1 to N

Pij(t)=φPbesti+(1-φ)gbest

其中α為創(chuàng)新參數(shù)，一般不大于1，φ和u為(0，1)上的均勻分布數(shù)值，取+和-的概率分別為0.5。

3.2 IQPSO對信號配時(shí)的優(yōu)化過程

按照量子粒子群算法的步驟，改進(jìn)后的量子粒子群算法IQPSO不再由全局最好位置和Pi決定，而是結(jié)合Pi和隨機(jī)選取的一個粒子最好位置決定，這也更契合各個交叉口不同情況特點(diǎn)，能選擇更符合實(shí)時(shí)的情況，比如隨機(jī)選取一個粒子c；

Iff(pc)

Iff(pc)>f(pi)，G=pg

3.2.1 適應(yīng)度函數(shù)

(6)

其中T分別取最小周期和最大周期，D是平均延誤時(shí)間，q是交通流量，g是獲得綠燈通行時(shí)間，懲罰因子γ1，γ2一般取10以上。

3.2.2 算法步驟

把該方法結(jié)合實(shí)際信號配時(shí)優(yōu)化過程，以區(qū)域?yàn)閷ο螅蠼獬鲎顑?yōu)的配時(shí)組合。類似選擇操作過程，從粒子群中隨機(jī)選擇一個粒子k；對該粒子進(jìn)行編碼，確定該粒子各項(xiàng)參數(shù)。具體步驟如下：

1)輸入交叉口交通流的模型參數(shù)，包括最大以及最小周期時(shí)長，周期數(shù)L以及交叉口數(shù)量n。

2)各項(xiàng)參數(shù)設(shè)定；種群的規(guī)模M，迭代數(shù)最大Genmax，加入懲罰因子γ1，γ2。

3)在所有配時(shí)問題空間初始化粒子的位置。

4)計(jì)算在群空間中的平均最優(yōu)位置。

5)把粒子的當(dāng)前適應(yīng)值與上一次迭代的適應(yīng)值進(jìn)行比較，如果當(dāng)前適應(yīng)值小于上一次的值，那么粒子位置更新為當(dāng)前位置，也就是取當(dāng)前信號配時(shí)。

6)算出當(dāng)前群體全局最優(yōu)值G，并與前一次迭代的全局最優(yōu)位置進(jìn)行比較，哪個位置好即成為更新值。

7)選擇點(diǎn)G，對每一個粒子每一維算出歷史最優(yōu)更新值。

8)計(jì)算粒子新的位置。

9)重復(fù)4)～8)步驟，直到滿足條件，跳出循環(huán)。

10)調(diào)用可視化仿真工具，動態(tài)演示信號優(yōu)化配時(shí)結(jié)果，包括車輛行駛狀態(tài)、隊(duì)列情況、交通流量、交叉口數(shù)量、信號控制變化等情況。

4 仿真測試

采用仿真軟件Vissim與Matlab工具進(jìn)行分析測試。設(shè)定三種車流情況，交通流密度分別為一般，臨近飽和與過飽和情況。分別運(yùn)用傳統(tǒng)固定配時(shí)算法、PSO算法和本文提到的IPSO算法進(jìn)行重復(fù)次數(shù)實(shí)驗(yàn)，算出平均延誤進(jìn)行比對。如圖4所示，單個交叉口局部仿真情況，其中圖中各種長短的圓角矩形塊代表不同類型的車輛，在仿真中駕駛行為一般只與前車行駛狀態(tài)有關(guān)，這一點(diǎn)可能與實(shí)際情況有點(diǎn)誤差。

圖4 交叉口仿真示意圖

第一種情況，交通流量為一般飽和，平均到達(dá)設(shè)置為λ=15輛/min，符合泊松分布。在傳統(tǒng)固定配時(shí)、PSO以及IQPSO三種交叉口控制方法下的車輛平均延誤如圖5所示。

圖5 一般飽和流量下的車輛平均延誤

第二種情況，當(dāng)交通流達(dá)到飽和流量臨界值時(shí)，交通量服從二項(xiàng)分布n=35，p=0.7(p為到達(dá)成功率)。該情況下車輛的平均延誤如圖6所示。

圖6 飽和流量下的車輛平均延誤

第三種過飽和情況下，設(shè)置n=60，p=0.6，該情況下車輛的平均延誤如圖7所示。

圖7 過飽和流量下的車輛平均延誤

在仿真過程中，分別設(shè)置配時(shí)周期120秒、90秒、60秒，實(shí)際交通網(wǎng)某些路口固定配時(shí)往往超過了120秒。根據(jù)三種不同的交通流情況下的對比圖顯示，IQPSO有明顯的效率優(yōu)化，而PSO因有時(shí)陷入局部早熟的情況，有時(shí)并沒有比固定配時(shí)效率高，這也和通行能力降低有關(guān)系。

5 結(jié)束語

為進(jìn)一步優(yōu)化城市交通信號控制系統(tǒng)，本文提出一種實(shí)時(shí)路口協(xié)調(diào)控制RIC2模型，其中重點(diǎn)介紹了配時(shí)優(yōu)化過程。該環(huán)節(jié)采取一種改進(jìn)的量子粒子群算法IQPSO對信號配時(shí)進(jìn)行優(yōu)化并達(dá)到協(xié)調(diào)控制的效果。在仿真測試后，結(jié)果顯示該算法能對RIC2模型起到很好的性能提升，配時(shí)優(yōu)化結(jié)果顯示車輛平均延誤有顯著的減小。不過，以區(qū)域控制為對象的實(shí)際交通路網(wǎng)中，該模型還需進(jìn)一步測試。