城市道路交叉口信號配時多目標優(yōu)化方法研究

摘 要： 針對目前交叉口信號配時優(yōu)化目標單一、綜合運行效率不高的問題，提出一種交叉口信號配時多目標優(yōu)化方法。考慮綠燈時間、周期長度和飽和度等約束條件，通過加權(quán)系數(shù)法定義代價函數(shù)，使交叉口的延誤時間、停車次數(shù)和通行能力在某種程度上達到最優(yōu)?；诿庖呖寺∷惴ㄔ谔幚矶嗄繕藛栴}中具有最優(yōu)解分布寬廣性、均勻性好等特點，引入環(huán)境變異算子，提出環(huán)境變異免疫克隆算法對模型求解，增強了算法的全局搜索能力，提高了解的質(zhì)量。仿真結(jié)果表明，與傳統(tǒng)配時方法和改進粒子群算法相比，該文方法能有效減少信號交叉口的延誤時間和停車次數(shù)，提高交叉口的運行效率。

關(guān)鍵詞： 交叉口； 信號配時； 多目標優(yōu)化； 環(huán)境變異免疫克隆算法

中圖分類號： TN911?34； U491 文獻標識碼： A 文章編號： 1004?373X（2016）16?0019?04

Abstract： To solve the problems of single optimization objective and low efficiency in signal timing， a novel multi?objective optimization method for signal timing of intersections is proposed. In consideration of constraint conditions of green?light duration， cycle length and saturability， the cost function is defined by weighted coefficient method to make delay time， parking times and traffic capacity of intersections optimum to some extent. Based on the characteristics of uniformity and wide?distribution of optimal solution while immune clone algorithm （ICA） is used to solve multi?objective problems， a new environment mutation operator was introduced， and the environment mutation ICA was proposed for model solution， which enhanced the global searching ability of the algorithm and improved the solution quality. The simulation results reveal that， compared with the traditional timing method and inertia weight particle swarm algorithm， the presented method can efficiently reduce average delay， parking times of intersections， and improve the efficiency of traffic signal control.

Keywords： intersection； signal timing； multi?objective optimization； environment mutation immune clone algorithm

信號交叉口常用的性能評價指標有停車次數(shù)、通行能力、延誤、排隊長度、飽和度等[1]。然而，目前國內(nèi)文獻中多以一個性能指標（通常是總延誤）對交叉口進行配時優(yōu)化，既無法滿足現(xiàn)實情況中需要滿足多項性能指標兼顧的要求，也沒有考慮不同交通狀態(tài)下對多個性能指標有所側(cè)重要求，具有一定的局限性[2]。因此，信號交叉口的配時優(yōu)化問題實質(zhì)上是一個多目標優(yōu)化的問題。

多目標優(yōu)化問題（Multi?objective Optimization Problems，MOP）是指具有兩個及以上的目標函數(shù)的最優(yōu)化問題[3]。這些優(yōu)化目標往往彼此間難以直接比較，甚至相互對立，一個目標的改善甚至有可能引起另一個目標性能的降低，因而難以同時達到最優(yōu)。

針對這些問題，本文選取延誤時間、停車次數(shù)和最大通行能力作為信號控制目標，建立了相應(yīng)的單交叉口多目標優(yōu)化信號配時優(yōu)化模型，并提出了基于環(huán)境變異免疫控制算法（Environment Mutation Immune Clone Algorithm，EMICA） 的多目標控制方法。通過該算法協(xié)調(diào)好這三個控制目標的平衡，從而得到實時的多目標最優(yōu)解，進而得到最佳的控制策略。

1 交叉口多目標信號配時優(yōu)化模型

本文在研究單點道路交叉口的信號配時時，假設(shè)交通流數(shù)據(jù)（如每個車道的機動車交通量）已經(jīng)獲得，非機動車及行人已轉(zhuǎn)換成當(dāng)前交通量。

1.1 多目標信號配時模型

交叉口信號控制的優(yōu)化目標包括延誤時間、停車次數(shù)、最大通行能力、飽和度、油耗、尾氣排放等。其中尤以前4項最為重要，一般來說其他項均可以由這幾項導(dǎo)出[4?5]。因此，本文把交叉口的總延誤、總停車次數(shù)、最大通行能力三個指標作為優(yōu)化對象，以飽和度為約束，利用加權(quán)的方法合并成目標函數(shù)并求解。假設(shè)交叉口信號有n個相位，下面是信號配時中需要優(yōu)化三個指標的函數(shù)表達式，將各相位的有效綠燈時間作為自變量：

（1） 延誤時間計算。延誤時間是指在交叉口處由于交通流沖突或信號燈控制引起的行駛時間損失。韋伯斯特（Webster）提出了延誤時間的計算公式[6?7]如下：

[Di=C1-λi221-yi+yi22qiλiλi-yi] （1）

式中：[Di]表示第[i]相位的車輛平均延誤時間，單位為s；[C]為周期，單位為s；[λi]為綠信比表示第[i]相位有效綠燈時間與信號周期的比值；[yi]為第[i]相位的相位流量比；[qi]為第[i]相位的相位車流到達率，單位為pcu/h。

（2） 停車率計算。采用穩(wěn)態(tài)模型[8?9]計算進入交叉口每輛車輛的平均停車次數(shù)，如式（2）所示：

[Hi=0.91-λi1-yi+NiqiC] （2）

式中：[Hi]表示第[i]相位的車輛平均起停次數(shù)；[Ni]表示在未飽和交叉口，某相位的平均滯留車輛數(shù)。

（3） 通行能力計算。采用HCM2000理論[5，10]，先將交叉口各進口道劃分為若干車道組，然后計算各車道組的通行能力：

[Qi=Siλi] （3）

式中：[Qi]表示第[i]相位的通行能力；[Si]為車道組[i]的飽和流率。

1.2 目標函數(shù)

將以上三個函數(shù)通過加權(quán)的方法轉(zhuǎn)化為目標函數(shù)進行求解：

[f=ξ1Di+ξ2Hi+ξ3Qi] （4）

式中，[ξi]表示第[i]個目標函數(shù)的權(quán)重系數(shù)。

為了使建立的優(yōu)化模型更好地符合實際狀況，模型應(yīng)能夠根據(jù)不同交通狀態(tài)對各指標有所側(cè)重：如交通狀態(tài)趨向擁擠時要確保發(fā)揮路口的最大通行能力，而非擁擠狀態(tài)時應(yīng)盡可能減少路口信號控制的延誤和停車次數(shù)。首先評判這幾個指標的相對重要性，根據(jù)式（5）、式（6）建立相應(yīng)的模糊矩陣[R=ri，j]，其中[ri，j]表示[i]相對于[j]的重要性，并根據(jù)式（7）、式（8）求解。

[R=rD，DrD，HrD，QrH，DrH，HrH，QrQ，DrQ，HrQ，Q] （5）

[ri，j=0， ij ri，j=2， i?j ] （6）

令：

[Ii=j=1nri，j] （7）

進行歸一化后可得：

[ξi=IiIi] （8）

這種利用模糊矩陣的加權(quán)系數(shù)法對三個性能指標進行平衡，大大降低了交警設(shè)置指標權(quán)重的復(fù)雜程度和主觀性，從而通過調(diào)整[ξi]的值使得交叉口在不同交通狀態(tài)下均能在某種程度上達到最優(yōu)。

1.3 約束條件

為了保證行人和行車安全，需要在配時前添加一定的約束條件，由式（9）～式（11）給出。

（1） 綠燈時間約束[1]。一般情況下，有效綠燈時間最小不小于12 s，最大不大于100 s。

[gimin≤gi≤gimax ， 1≤i≤n] （9）

（2） 周期約束[1]。信號周期過短會對行人車輛安全通過交叉口造成威脅，過大也不會增加通行能力，所以一般最短信號周期時長可取30～40 s，最大不大于180 s。

[Cmin≤C=i=1ngi+li≤Cmax] （10）

（3） 飽和度約束[1]。因在過飽和情況下，采用優(yōu)化算法往往也難以起到良好的優(yōu)化效果，而飽和度在0.7和0.9之間時，交叉口可以獲得較好的運行條件，故飽和度取0.7～0.9。

[0.7≤X≤0.9] （11）

2 信號配時優(yōu)化算法

本文所要解決的多目標約束優(yōu)化問題可以定義如下[11]：

[min fAs.t. A∈G， G=ai∈Rm gix≤0 i∈1，m ， j∈1，0] （12）

式中：[fA]為優(yōu)化目標函數(shù)；[A=a1，a2，…，am]為[Rm]空間內(nèi)變量集；[G]為所有可行解集合；[g·]為約束函數(shù)。本文采用十進制編碼，所有變量歸一化在[0，1）區(qū)間。

2.1 代價函數(shù)設(shè)計

由于配時優(yōu)化模型中約束條件的存在，需要進行約束處理。而罰函數(shù)法是處理約束條件最常用的方法之一，故采用罰函數(shù)的方式來處理，代價函數(shù)可寫為：

[fCA=fA+rg?A] （13）

式中：[rg]為懲罰系數(shù)；[?A]為罰函數(shù)。

雖然罰函數(shù)法有著簡單易行的優(yōu)點，但實際上選取合適的懲罰系數(shù)相當(dāng)困難。懲罰系數(shù)[rg]太小可能導(dǎo)致懲罰力度過小，影響優(yōu)化函數(shù)的尋優(yōu)方向[11?12]；懲罰系數(shù)[rg]過大則會引發(fā)計算的困難容易引起早熟收斂[13]；因此，如何選擇合適的懲罰系數(shù)[rg]或懲罰函數(shù)的形式是解決有約束優(yōu)化問題的關(guān)鍵。罰函數(shù)可以調(diào)節(jié)個體的適應(yīng)度值，對群體的排序產(chǎn)生影響。文獻[14]中采用概率排序的形式，使得群體在目標函數(shù)和約束條件中得到動態(tài)的平衡。本文在參考文獻[14]核心思想的同時，也制定了以下三條規(guī)則，以能夠保證目標函數(shù)值小、約束條件值也不大個體的基因也有機會在群體中傳播[11?12]：

（1） 當(dāng)兩個個體都符合約束條件時，目標函數(shù)值小的排序靠前；

（2） 當(dāng)兩個個體有一個不符合約束條件時，目標函數(shù)值小而且約束條件值小的排序靠前；

（3） 當(dāng)兩個個體有一個不符合約束條件且目標函數(shù)值小與約束條件值小條件不同時成立時，則以約束條件的比值為概率，隨機排序。

2.2 環(huán)境變異免疫克隆算法算子描述

免疫克隆算法是近年來新興的進化算法之一。人們受生物免疫系統(tǒng)的啟發(fā)，通過對免疫應(yīng)答過程及免疫細胞克隆的模擬而提出的一種啟發(fā)式搜索算法。它提供噪聲忍耐、自組織、記憶等學(xué)習(xí)機理，具有保持群分布多樣性的特點[15]。免疫克隆算法較成功地解決了多目標優(yōu)化中最優(yōu)解分布的寬廣性、均勻性及向著最優(yōu)Pareto?前端逼近等問題。本文借鑒了免疫克隆算法在解決多目標優(yōu)化問題中的優(yōu)勢，并基于以前的工作，利用EMICA算法來解決有交叉口信號控制的優(yōu)化問題。本文信號配時優(yōu)化算法的核心就是EMICA算法?；贓MICA算法的多目標尋優(yōu)步驟如下，詳細步驟[12]如下：

（1） 初始化。初始化抗體群，設(shè)定算法參數(shù)，抗體號i=1，進化代數(shù)t=0；

（2） 疫苗選擇[TCs]。在人類免疫系統(tǒng)中，抗原一般指問題及其約束，抗體一般是指問題的候選解[16?17]，疫苗則是由先驗知識而得到的對最佳個體基因的估計。在EMICA算法中將每代親和度最高的抗體認為是疫苗：

[TCsAPt=maxi∈1，NfCAt] （14）

式中：[APt]為第[t]代的抗體集；[N]為種群規(guī)模。

（3） 克隆增殖[TCc]?？寺≡鲋持饕菍贵w群進行復(fù)制，因此克隆后種群[AP]包括兩部分：一部分是克隆子群記為[APC]；另一部分是原抗體群：

[TCcAP=TCcA1 TCcA2 … TCcAPtTTCcAi=Ik×Ai] （15）

式中，[Ik]為[k]維單位行矩陣；[k]為克隆規(guī)模。

（4） 環(huán)境變異[TCe]。環(huán)境變異主要是對克隆子群[APC]進行環(huán)境影響因素的變異操作。這樣做有兩個好處：一是在群體中較優(yōu)個體周圍探索前進方向，從而提高免疫算法效率；二是通過環(huán)境變量獲取進化過程中的歷史經(jīng)驗，使算法在一定程度上具有學(xué)習(xí)能力：

[TCeACt=ACt+r1Et ， ACt?APCtEt=r2Et-1+r3TCsAPt-ACt] （16）

式中：[E]為環(huán)境變量；[r1]為學(xué)習(xí)系數(shù)；[r2]為遺忘系數(shù)；[r3]為修改系數(shù)。

（5） 克隆變異[TCm]。通過式（13）對克隆子群[APC]進行變異操作：

[TCmgCj1j2=gmj1j2 ， flippm=1gCj1j2 ， 其他 gCj1j2∈ACit] （17）

式中：[flip?]為伯努利試驗；[gCij]為克隆個體的基因位；[gmij]為變異基因位；[pm]為變異概率。

（6） 克隆選擇[TCr]。克隆選擇是從克隆進化后的群體中選擇優(yōu)秀個體，進而形成新的種群的過程。若克隆子群個體的親和度大于克隆母體的親和度，則將該個體替代母體，從而使高親和力抗體中的優(yōu)秀基因得到更好地保存和發(fā)展。

[TCrAit，APCt=ACt+1，max， fACt+1，max>fAit且 fACt+1，max≥∨j=1kfACjAit， 其他 ] （18）

式中，[ACt+1，max]為最大親和度個體。

（7） 判斷。判斷是否滿足終止條件，不滿足終止條件則返回步驟（3），并將前一個時刻的最終抗體群作為下一個時刻的初始種群，若滿足終止條件則算法結(jié)束。

3 仿真結(jié)果及分析

為了驗證本文方法的有效性，以典型的四相位信號交叉口為例（即假設(shè)右轉(zhuǎn)車流不受信號控制），計算各相位的有效綠燈時間，信號控制方案如圖1所示，交叉口各進口各向交通量如表1所示[8]，其中非機動車交通量已經(jīng)換算為標準小轎車交通量。

程序采用VC++ 6.0語言編寫。參數(shù)設(shè)置：群體規(guī)模N=200，克隆規(guī)模k=5，變異概率pm=0.01，環(huán)境變量學(xué)習(xí)參數(shù)r1=random（0.0，1.2），環(huán)境變量遺忘參數(shù)r2=random（0.6，0.7），環(huán)境變量修改參數(shù)r3=random（0.0，1.4）。采用連續(xù)100 代不能提高群體的最優(yōu)解時停止為算法終止條件。其中，最小周期和最大周期分別為40 s和180 s，總損失時間為16 s，飽和度限制在0.7～0.9之間。原配時方案得到的結(jié)果，利用文獻[8]提出的改進粒子群算法優(yōu)化得到的結(jié)果，及采用本文提出的算法優(yōu)化后的結(jié)果如表2所示。

由表2可以看出，與原有配時方案相比，經(jīng)過兩種算法優(yōu)化后總延誤和總停車次數(shù)兩個指標均得到一定程度的改善。原方案的總延誤為16 648 s，經(jīng)改進粒子群算法優(yōu)化后最小延誤為10 683 s，比原方案減少了35.8%，而經(jīng)本文算法優(yōu)化后的最小延誤為9 883 s，較原方案降低了40.6%。原方案總停車次數(shù)為212次，經(jīng)改進粒子群算法優(yōu)化后最小停車次數(shù)為170次，比之前降低了19.8%，而經(jīng)本文算法優(yōu)化后的最小停車次數(shù)為163次，較原方案降低了23.1%?？梢钥闯鲈诳傃诱`和總停車次數(shù)兩個指標上，本文算法的優(yōu)化結(jié)果均好于改進粒子算法得到的結(jié)果。但由于交叉口周期時長的減小，從而使交叉口最大通行能力有所下降，可由于本文不探討交叉口過飽和度的通行狀態(tài)，一般達不到交叉口的最大通行能力，可以說交叉口最大通行能力的略微下降對整個交叉口的運行效率幾乎無影響。綜上所述，兩種算法在優(yōu)化結(jié)果上均取得了較好的結(jié)果，但本文算法在處理交叉口信號控制多目標優(yōu)化的綜合性能要強于改進粒子群算法優(yōu)化。

4 結(jié) 論

進行信號配時優(yōu)化時，綜合考慮了交叉口的總延誤時間、總停車次數(shù)和最大通行能力三個常用評價指標，并應(yīng)用加權(quán)的方法定義了目標函數(shù)，克服了以往優(yōu)化方法目標過于單一的缺點，更加符合實際環(huán)境中多項性能指標的控制需求。使用模糊矩陣的方法來確定三個性能指標的權(quán)重系數(shù)，簡化了人們對指標權(quán)重判斷的復(fù)雜性和主觀性，解決了在不同交通狀態(tài)下確定權(quán)重的方法一致性問題。算法性能上，引入了多目標問題求解上有諸多優(yōu)勢的免疫克隆算法，并在其中融合了環(huán)境變異算子，將環(huán)境對個體進化的影響積累到克隆變異操作中，提高了免疫克隆算法的搜索效率和穩(wěn)定性。對典型的四相位信號交叉口信號配時的仿真結(jié)果表明，與現(xiàn)有算法相比，本文算法更能夠得到高質(zhì)量的解，有助于緩解交通擁堵的狀況。下一步的研究工作是將提出的基于環(huán)境變異免疫克隆算法的交叉口信號控制多目標優(yōu)化方法在實際交叉口中加以應(yīng)用，利用前期開發(fā)的視頻車檢器獲取交通流量等信息，從而使交叉口通行更為順暢，同時也更加節(jié)能和環(huán)保。

參考文獻

[1] 王錦錦.改進交叉口性能評價及多目標優(yōu)化配時研究[D].重慶：重慶大學(xué)，2012.

[2] 曹成濤，徐建閩.單交叉口交通多目標控制方法[J].計算機工程與應(yīng)用，2010，46 （16）：20?22.

[3] 王光遠.城市交通信號多目標自適應(yīng)控制[D].大連：大連理工大學(xué)，2010.

[4] 蘇長慧，夏桂梅.基于改進微粒群算法的單點信控交叉口配時優(yōu)化[J].太原科技大學(xué)學(xué)報，2014，35（3）：198?201.

[5] 曹娟娟，卲維.基于改進粒子群算法的多目標單交叉口信號優(yōu)化控制[J].長沙大學(xué)學(xué)報，2012，26（2）：69?71.

[6] 伍尚昆，陳翠宜，祝勝林.基于多種群蟻群算法的交叉路口信號配時優(yōu)化[J].計算機應(yīng)用與軟件，2014，31（5）：83?88.

[7] 崔明月，劉紅釗，劉偉，等.改進的非劣遺傳算法在多目標優(yōu)化中的應(yīng)用[J].南陽師范學(xué)院學(xué)報，2014，13（12）：8?12.

[8] 劉金明.基于多目標規(guī)劃的城市道路交叉口信號配時研究[D].北京：北京交通大學(xué)，2011.

[9] 肖婧，王科俊，畢曉君.交叉口混合交通流高維多目標信號優(yōu)化控制[J].公路交通科技，2014，31（11）：108?115.

[10] 陳小紅.混合交通環(huán)境下城市道路交通信號控制優(yōu)化模型研究[D].北京：北京交通大學(xué)，2012.

[11] 徐海黎，解祥榮，莊健，等.工業(yè)機器人的最優(yōu)時間與最優(yōu)能量軌跡規(guī)劃[J].機械工程學(xué)報，2010，46（9）：19?25.

[12] 徐海黎，朱志松，王恒，等.環(huán)境變異免疫克隆算法解決有約束優(yōu)化問題[J].系統(tǒng)仿真學(xué)報，2011，23（11）：2412?2416.

[13] 焦李成，尚榮華，馬文萍，等.多目標優(yōu)化免疫算法、理論和應(yīng)用[M].北京：科學(xué)出版社，2010：114.

[14] RUNARSSON Thomas Philip，YAO Xin. Stochastic ranking for constrained evolutionary optimization [J]. IEEE transactions on evolutionary computation （S1089?778X），2000，4（3）： 284?294.

[15] 尚榮華，焦李成，公茂果，等.免疫克隆算法求解動態(tài)多目標優(yōu)化問題[J].軟件學(xué)報，2007，18（11）：2700?2711.

[16] 秦亮，張文廣，史賢俊，等.基于免疫克隆算法的多目標聚類方法[J].信息與控制，2013，42（1）：8?12.

[17] 林滸，彭勇.面向多目標優(yōu)化的適應(yīng)度共享免疫克隆算法[J].控制理論與應(yīng)用，2011，28（2）：206?214.