基于改進(jìn)Lagrange乘子法的交通信號配時優(yōu)化研究

牟 亮，趙 紅，崔翔宇，袁煥濤，李 燕，仇俊政

(青島大學(xué)機(jī)電工程學(xué)院，山東 青島 266071)

0 引言

交叉口的信號控制在交叉口通行效率、交通秩序以及污染物排放等方面有著重要的影響。近年來，全國機(jī)動車保有量不斷增加，駕駛汽車已經(jīng)成為人們?nèi)粘５某鲂蟹绞剑覀円裁媾R著交通堵塞和環(huán)境污染等嚴(yán)重問題。合理的交通信號配時方案可以有效地減少這方面的問題。交通排放會對環(huán)境甚至是人們的身體造成危害，人們也越來越關(guān)心出行時間。因此低排放和低延誤成為交通信號控制的主要問題?，F(xiàn)有文獻(xiàn)表明，交通信號配時問題是復(fù)雜的、分布式的、混合的[1-5];交叉口的交通規(guī)律是難以預(yù)測的、復(fù)雜的、無規(guī)律的[6-9]，但VISSIM中可以較真實地反映出現(xiàn)實的交通運行情況?，F(xiàn)實中在制定交通信號配時策略時不能僅考慮一方面，而是需要綜合考慮多個方面，因此為提高交叉口的通行效率及降低環(huán)境污染，本文將采用多目標(biāo)優(yōu)化控制策略。多目標(biāo)優(yōu)化相較于單目標(biāo)優(yōu)化可以提高交叉口的綜合性能，同時可以反映所研究的目標(biāo)之間的關(guān)系，在實際工程問題中具有一定的優(yōu)勢。

目前國內(nèi)外在Lagrange乘子法的研究上已經(jīng)取得了一些成果。張克等[10]針對Lagrange乘子法將約束問題轉(zhuǎn)化為無約束問題，與粒子群優(yōu)化算法結(jié)合提出的一種新型算法；黃燦遠(yuǎn)[10]對Lagrange乘子法的乘子更新進(jìn)行了改進(jìn)，重新定義不等式約束的乘子為原乘子的正定函數(shù)，構(gòu)造出一種直接對不等式約束進(jìn)行處理的改進(jìn)Lagrange乘子法。本文介紹的改進(jìn)方法是對乘子法中另一個重要參數(shù)的更新方式進(jìn)行改變，來研究另一個重要參數(shù)對算法迭代及收斂性的影響。

在交通信號控制方面，Meszaros等[12]基于延誤和排放對交叉口的優(yōu)化控制提出了建議；彭敏等[13]運用博弈論對交叉口的平均延誤和停車延誤進(jìn)行優(yōu)化；衛(wèi)星等[14]推導(dǎo)出平均延誤時間目標(biāo)與綠燈配時之間的關(guān)系，在此模型的基礎(chǔ)上采用自適應(yīng)遺傳算法進(jìn)行優(yōu)化。Lin等[15]利用綜合宏觀交通模型預(yù)測在不同操作條件下的交通流狀態(tài)和排放，并應(yīng)用于城市交通網(wǎng)絡(luò)控制。胡亮等[16]將蜂群抑制算法應(yīng)用到交通信號燈的控制中。

當(dāng)前流行的智能算法，代碼的編寫較為復(fù)雜，例如遺傳算法，需要對問題進(jìn)行編碼，找到最優(yōu)解后有需要進(jìn)行解碼算法的搜索速度比較慢，要得要較精確的解需要較多的訓(xùn)練時間。Lagrange乘子法具有程序簡單、迭代次數(shù)少、搜索范圍大和收斂快等優(yōu)點，并且該方法的耗時很少。根據(jù)動態(tài)車流實時配置信號燈狀態(tài)是現(xiàn)在較為常用的方法，Lagrange乘子法具有較低的延誤，可以對交通信號燈的狀態(tài)進(jìn)行實時配置。本文提出一種改進(jìn)Lagrange乘子法，并應(yīng)用到實際工程中去驗證該種方法真實有效性。

本文綜合考慮交叉口的機(jī)動車通行效率和環(huán)境效益兩方面的優(yōu)化，建立數(shù)學(xué)模型，通過權(quán)重系數(shù)的方式將這兩個優(yōu)化目標(biāo)整合成單目標(biāo)優(yōu)化模型，權(quán)重系數(shù)設(shè)置為變量一同進(jìn)行優(yōu)化，從而可以達(dá)到交叉口性能的綜合最優(yōu)的目的。

1 改進(jìn)Lagrange乘子法

Lagrange乘子法[17]是一種求解非線性約束問題的常用方法，該方法是通過構(gòu)造拉格朗日函數(shù)和添加懲罰項來將有約束的問題轉(zhuǎn)化為無約束問題進(jìn)行求解，求解無約束問題的最小值。然而傳統(tǒng)的Lagrange乘子法的罰參數(shù)的更新是固定的，更新方式為罰參數(shù)與一固定系數(shù)相乘?，F(xiàn)將罰參數(shù)的固定系數(shù)改為與求得值偏離約束條件的大小有關(guān)的函數(shù)。新的算法有以下優(yōu)點，懲罰參數(shù)的更新為一種自適應(yīng)更新，當(dāng)求得值偏離可行域越大時，增加罰參數(shù)的增加速度，該方法的全局搜索能力優(yōu)與傳統(tǒng)算法，罰參數(shù)的更新范圍變大擴(kuò)大了最小值的搜索范圍，以及趨向最優(yōu)值的速度。

1.1 一般約束問題

在交叉口的優(yōu)化模型中，必然會存在各種等式及不等式約束，這樣就構(gòu)成了一般約束問題，一般約束問題的數(shù)學(xué)模型為

(1)

其中，hi(x)為等式約束，gi(x)為不等式約束。接下來需要運用改進(jìn)的乘子法對一般問題的數(shù)學(xué)模型進(jìn)行研究。

1.2 一般約束問題的乘子法

在構(gòu)造增廣拉格朗日函數(shù)時，添加輔助變量將不等式約束轉(zhuǎn)化為等式約束，等式約束則通過與罰參數(shù)相乘來構(gòu)造懲罰項，經(jīng)過上述操作構(gòu)造的增廣拉格朗日函數(shù)為

(2)

更新乘子向量的迭代公式為

(μk+1)i=(μk)i-σhi(xk)
(λk+1)i=max{0,(λk)i-gi(xk)}

(3)

Lagrange乘子法中罰參數(shù)的更新方式為若βk/βk-1≥?，更新罰參數(shù)，σk+1=ησk；否則，不更新罰參數(shù)，σk+1=σk。

1.3 Lagrange乘子法的改進(jìn)

傳統(tǒng)的方法罰參數(shù)的更新方式較為固定，并不能根據(jù)當(dāng)前解偏離可行域的大小進(jìn)行糾偏，可以加速算法的收斂速度，改進(jìn)方法如下。

將罰參數(shù)更新公式改為

(4)

1.4 改進(jìn)Lagrange乘子法的算法流程

Lagrange乘子法是Rockfellar在Powell和Hestenes提出的PH算法的基礎(chǔ)上得到的，所以可以簡稱為PHR算法。將改進(jìn)的罰參數(shù)修改后得到算法的流程如下：

步驟1 選取初值：

x0∈Rn,μ1∈Rl,λ1∈Rm,σ1>0,0<ε?1,

?∈(0,1),η>1,k=1。

步驟2 求解無約束子問題：

minψ(x,μk,λk,σk)

(5)

設(shè)初始點為xk-1,即可求得點xk。

步驟3 檢驗終止條件：

(6)

圖1 改進(jìn)罰參數(shù)的Lagrange乘子法算法流程

若βk≤ε，則停止迭代，輸出xk為原問題的解；否則，轉(zhuǎn)到下一步。

步驟4 更新罰參數(shù)σ：

(7)

步驟5 更新乘子向量：

(μk+1)i=(μk)i-σhi(xk)

(λk+1)i=max{0,(λk)i-gi(xk)}

(8)

步驟6 令k=k+1,轉(zhuǎn)到步驟2。

流程圖如圖1所示。

2 信號控制優(yōu)化模型

2.1 選取交通信號控制目標(biāo)

評價交叉口的好壞有3個方面，即機(jī)動車效益、環(huán)境效益和行人效益。機(jī)動車效益包含了車輛通行能力、停車率、延誤、排隊長度等，環(huán)境效益包括了車輛通行時的燃油消耗及尾氣排放，行人效益一般為行人等待時間。在此，我們綜合考慮機(jī)動車效益和環(huán)境效益，既提高交叉口車輛通行效率又降低汽車尾氣排放，從中選取最能代表每種效益的關(guān)鍵性能指標(biāo)，本文選取了機(jī)動車延誤和尾氣排放來建立目標(biāo)函數(shù)。

2.2 車輛延誤與尾氣排放模型

車輛延誤是指機(jī)動車在信號控制的交叉口運行與在無信號控制及無其他車輛干擾下的行程時間的差值?？梢赃x用Webster延誤模型和美國道路通行能力手冊(Highway Capacity Manual，HCM)延誤模型，由于Webster延誤模型經(jīng)人們廣泛地使用和驗證，該模型適用于進(jìn)口道飽和度較小時，飽和度范圍一般在0～0.67內(nèi)。而HCM延誤模型適用于適應(yīng)度較高的干道協(xié)調(diào)控制的延誤計算。本文是在這兩種模型的基礎(chǔ)上來建立模型進(jìn)行計算的，如式(9)[18]：

(9)

其中，dij為第i相位第j車道的車輛平均延誤;c為交叉口周期長度;λi為第i相位綠信比;qij為第i相位第j車道的車流量;si為第i相位的飽和流量;yij為qij與si之比。

交叉口總延誤為

(10)

車輛駛過交叉口時存在勻速、減速、怠速和加速行駛4種工況，每種工況的排放量不同，所以我們在分析交叉口的尾氣排放量時將要分情況考慮。在計算交叉路口的排放量時，可分解為交叉口和路段的行車排放和因車輛延誤造成的怠速排放，通過該種方法得到的排放模型[19]為

(11)

其中，eij為第i相位第j車道的排放量;e1為標(biāo)準(zhǔn)小汽車單位排放因子;Lij為第i相位第j車道路段長度;e2為標(biāo)準(zhǔn)小汽車單位怠速排放因子;dij為第i相位第j車道的車均延誤。

交叉口一小時內(nèi)車輛的總排放量為

(12)

2.3 建立優(yōu)化目標(biāo)模型

在建立優(yōu)化模型時綜合考慮交叉口的機(jī)動車效益和環(huán)境效益，其中車輛延誤和尾氣排放量是最能代表兩個效益的指標(biāo)，故選取車輛延誤和尾氣排放量作為優(yōu)化目標(biāo)。為達(dá)到一個綜合的最優(yōu)值，利用加權(quán)的形式放入到一個目標(biāo)函數(shù)中，并考慮變量的范圍，最終構(gòu)建交叉口的優(yōu)化模型為

(13)

其中，D、E分別為優(yōu)化后的交叉口信號配時方案下的延誤及排放量;D0、E0分別為原始配時方案下的交叉口延誤及排放量;α與β為權(quán)重系數(shù);cmin、cmax分別為交叉口最小、最大周期長度;gimin、gimax分別為交叉口第i相位最小、最大有效綠燈時間;L為一周期的總損失時間；n為交叉口內(nèi)的相位數(shù)。

3 實例仿真

為驗證該種方法的真實有效性，利用MATLAB R2015b將乘子法進(jìn)行編程，并在CPU型號為Core i7-8565U，內(nèi)存為8G的電腦上運行。選取青島市黑龍江中路與九水東路交叉路口，該交叉口為雙向三車道，道路狀況良好無障礙物，根據(jù)道路實況以及Webster方法計算車道飽和度為1 500 pcu/h，對該路口在16:00-17:00的高峰期進(jìn)行采集可知該路口處于非飽和狀態(tài)，利用案例對本文提出的方法進(jìn)行分析。

3.1 交叉口數(shù)據(jù)信息

該交叉口為四相位信號控制，信號相序以及原始配時的情況如圖2所示，各路口車流量如表1所示。

模型中權(quán)重函數(shù)α、β也是兩個變量，我們需要將交叉口通行能力和尾氣排放量綜合考慮。結(jié)果中，權(quán)重函數(shù)大的一方，優(yōu)化的相對比例也大，實驗證明交叉口通行能力和尾氣排放量以如此的比值進(jìn)行優(yōu)化，就是最優(yōu)結(jié)果。

一個周期交叉口的損失時間設(shè)置為10 s，選取CO(一氧化碳)作為尾氣排放的目標(biāo)，標(biāo)準(zhǔn)小汽車CO的排放因子為45 g/(pcu*km)，標(biāo)準(zhǔn)小汽車怠速排放因子為5 g/(pcu*h),最大、最小信號周期，最大最小有效綠燈時間的設(shè)置如表2所示。

圖2 信號相序及原始配時方案

表1 該交叉口16：00-17：00的小時車流量(pcu/h)

3.2 優(yōu)化結(jié)果對比

為驗證本文提出的改進(jìn)Lagrange乘子法的優(yōu)點，將本案例分別放到改進(jìn)前后的Lagrange乘子法中分別進(jìn)行優(yōu)化，并記錄每一代尋找到的最小值，運行得到兩個方法的對比結(jié)果，如圖3所示。

表2 交叉口信號配時參數(shù)

圖3 改進(jìn)前后乘子法求解配時問題的迭代過程

由圖3可以看出，傳統(tǒng)的Lagrange乘子法由于劣質(zhì)的罰參數(shù)，導(dǎo)致數(shù)值的震蕩劇烈無法迅速收斂，求得的解也無法快速趨向于可行域。而通過罰參數(shù)自適應(yīng)更新的Lagrange乘子法，可以根據(jù)當(dāng)前解偏離可行域的距離來適當(dāng)加大罰參數(shù)，在7代左右就達(dá)到穩(wěn)定值(傳統(tǒng)乘子法14代以后才漸漸達(dá)到穩(wěn)定)，并且求得的最小值也更優(yōu)?？梢娫摲椒ǖ氖諗啃院涂焖傩詢?yōu)于傳統(tǒng)的Lagrange乘子法。這里具體只研究改進(jìn)Lagrange乘子法的優(yōu)化配時等問題。

為更加直觀地看出本文方法與智能算法在交通信號控制應(yīng)用中的區(qū)別，將上述案例分別利用標(biāo)準(zhǔn)遺傳算法和差分進(jìn)化算法進(jìn)行優(yōu)化，得到的進(jìn)化曲線如圖4所示。

圖4 兩種智能算法的進(jìn)化曲線

表3 算法耗時對比

Lagrange乘子法首先是找到最優(yōu)值的大致范圍，隨后對當(dāng)前解進(jìn)行調(diào)整，使其位于可行域范圍內(nèi)；而智能算法是一個逐漸尋優(yōu)的過程，算法迭代過程相對復(fù)雜。

從圖3中可以看出，Lagrange乘子法在迭代10代左右就可以準(zhǔn)確地找到最優(yōu)值，而本文介紹的遺傳算法和差分進(jìn)化算法需要200～300次左右才能逐漸找到最優(yōu)值。

在編寫代碼時記錄算法的耗時，將幾種算法的耗時進(jìn)行對比，如表3所示。

由圖3和表3可知，經(jīng)本文方法改進(jìn)后Lagrange乘子法的耗時更少，收斂更快，精度更高；由于智能算法的計算量巨大，迭代復(fù)雜，算法耗時相對較高。遺傳算法和差分進(jìn)化的最優(yōu)值分別為0.910 8和0.899 6，差分進(jìn)化算法的優(yōu)化結(jié)果優(yōu)于遺傳算法。接下來將改進(jìn)Lagrange乘子法與差分進(jìn)化算法進(jìn)行對比分析，結(jié)果如表4所示。

表4 信號配時優(yōu)化結(jié)果對比

經(jīng)過結(jié)果的對比可知，乘子法優(yōu)化的配時使延誤降低了19.89%，排放降低了2.379%；差分進(jìn)化算法優(yōu)化的配時使延誤降低了18.9%，排放降低了1.723%。上述優(yōu)化結(jié)果使延誤大幅度降低，但排放卻優(yōu)化很少，主要原因是在權(quán)重系數(shù)的分配過程中，將優(yōu)化的比例大部分分給了延誤，該種配時適用于擁堵嚴(yán)重的路口以及繼續(xù)降低延誤的情況。而當(dāng)排放污染嚴(yán)重，此時就需要大比例優(yōu)化排放。為解決這種問題，不再將權(quán)重系數(shù)看作變量，而是根據(jù)需要將β值設(shè)置得更高。權(quán)重系數(shù)的方法可以適用于各種不同的情況，適用范圍廣泛，不再局限于單個交叉口性能優(yōu)化。

3.3 VISSIM仿真

根據(jù)青島市黑龍江中路與九水東路交叉路口的實際情況搭建VISSIM仿真模型，如圖5所示。

為驗證本文方法的真實有效性，將優(yōu)化前后的配時利用微觀交通仿真軟件VISSIM進(jìn)行進(jìn)一步的驗證，在仿真軟件中選擇輸出交叉口的車輛延誤及CO的尾氣排放量。仿真周期設(shè)置為1 h，每60 s對該交叉口的數(shù)據(jù)進(jìn)行采集，將輸出結(jié)果繪制成折線圖，如圖6所示。

圖5 青島市黑龍江中路與九水東路VISSIM仿真模型

圖6 優(yōu)化前后配時于VISSIM仿真結(jié)果

表5 在VISSIM中各種配時的仿真結(jié)果

將各種配時分別輸入到VISSIM中進(jìn)行仿真對比，得到的車輛延誤及CO尾氣排放量的對比如表5所示。

綜合VISSIM仿真的延誤與排放的優(yōu)化結(jié)果，本文的方法對于優(yōu)化交叉口延誤以及排放是十分有效的，具有較強(qiáng)的全局搜索能力，相對于智能算法也具有一定的優(yōu)勢。整體來看，本文提出的信號優(yōu)化配時的方法以及建立的多目標(biāo)優(yōu)化模型都是有效的。

4 結(jié)論

為提高城市交叉口的通行效率，減少機(jī)動車尾氣排放，本文從綜合考慮機(jī)動車通行效率與環(huán)境效益的角度出發(fā)，建立以交叉口處的機(jī)動車延誤及尾氣排放量為綜合優(yōu)化指標(biāo)的目標(biāo)優(yōu)化模型，改進(jìn)傳統(tǒng)Lagrange乘子法收斂慢、精度不高等問題，并將該方法應(yīng)用到交通信號控制中。從VISSIM仿真結(jié)果得出，改進(jìn)Lagrange乘子法優(yōu)化配時令車輛延誤降低20.42%，一氧化碳尾氣排放量降低7.046%。與差分進(jìn)化算法得到的配時，在延誤方面降低了15.52%，排放方面降低了4.65%，本文方法在延誤方面比差分進(jìn)化算法減少了6.16%，排放方面降低了2.58%。本文方法尋找的最優(yōu)值略優(yōu)于智能算法的最優(yōu)值。

在面臨多種情況時，可對優(yōu)化目標(biāo)添加不同的權(quán)重，將優(yōu)化的重點放到我們需要優(yōu)化的目標(biāo)中。本文的方法針對于單交叉路口，將兩個目標(biāo)函數(shù)合并成一個，從而達(dá)到了整體上的優(yōu)化，克服了單目標(biāo)優(yōu)化不能綜合考慮交叉口性能的弊端。本文僅研究單交叉路口，后續(xù)可以應(yīng)用到路口存在相關(guān)聯(lián)的區(qū)域交通信號優(yōu)化控制中。