基于改進Lagrange乘子法的交通信號配時優化研究

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

(青島大學機電工程學院，山東 青島 266071)

0 引言

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

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

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

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

本文綜合考慮交叉口的機動車通行效率和環境效益兩方面的優化，建立數學模型，通過權重系數的方式將這兩個優化目標整合成單目標優化模型，權重系數設置為變量一同進行優化，從而可以達到交叉口性能的綜合最優的目的。

1 改進Lagrange乘子法

Lagrange乘子法[17]是一種求解非線性約束問題的常用方法，該方法是通過構造拉格朗日函數和添加懲罰項來將有約束的問題轉化為無約束問題進行求解，求解無約束問題的最小值。然而傳統的Lagrange乘子法的罰參數的更新是固定的，更新方式為罰參數與一固定系數相乘。現將罰參數的固定系數改為與求得值偏離約束條件的大小有關的函數。新的算法有以下優點，懲罰參數的更新為一種自適應更新，當求得值偏離可行域越大時，增加罰參數的增加速度，該方法的全局搜索能力優與傳統算法，罰參數的更新范圍變大擴大了最小值的搜索范圍，以及趨向最優值的速度。

1.1 一般約束問題

在交叉口的優化模型中，必然會存在各種等式及不等式約束，這樣就構成了一般約束問題，一般約束問題的數學模型為

(1)

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

1.2 一般約束問題的乘子法

在構造增廣拉格朗日函數時，添加輔助變量將不等式約束轉化為等式約束，等式約束則通過與罰參數相乘來構造懲罰項，經過上述操作構造的增廣拉格朗日函數為

(2)

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

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

(3)

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

1.3 Lagrange乘子法的改進

傳統的方法罰參數的更新方式較為固定，并不能根據當前解偏離可行域的大小進行糾偏，可以加速算法的收斂速度，改進方法如下。

將罰參數更新公式改為

(4)

1.4 改進Lagrange乘子法的算法流程

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

步驟1 選取初值：

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

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

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

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

(5)

設初始點為xk-1,即可求得點xk。

步驟3 檢驗終止條件：

(6)

圖1 改進罰參數的Lagrange乘子法算法流程

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

步驟4 更新罰參數σ：

(7)

步驟5 更新乘子向量：

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

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

(8)

步驟6 令k=k+1,轉到步驟2。

流程圖如圖1所示。

2 信號控制優化模型

2.1 選取交通信號控制目標

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

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

車輛延誤是指機動車在信號控制的交叉口運行與在無信號控制及無其他車輛干擾下的行程時間的差值。可以選用Webster延誤模型和美國道路通行能力手冊(Highway Capacity Manual，HCM)延誤模型，由于Webster延誤模型經人們廣泛地使用和驗證，該模型適用于進口道飽和度較小時，飽和度范圍一般在0～0.67內。而HCM延誤模型適用于適應度較高的干道協調控制的延誤計算。本文是在這兩種模型的基礎上來建立模型進行計算的，如式(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為標準小汽車單位排放因子;Lij為第i相位第j車道路段長度;e2為標準小汽車單位怠速排放因子;dij為第i相位第j車道的車均延誤。

交叉口一小時內車輛的總排放量為

(12)

2.3 建立優化目標模型

在建立優化模型時綜合考慮交叉口的機動車效益和環境效益，其中車輛延誤和尾氣排放量是最能代表兩個效益的指標，故選取車輛延誤和尾氣排放量作為優化目標。為達到一個綜合的最優值，利用加權的形式放入到一個目標函數中，并考慮變量的范圍，最終構建交叉口的優化模型為

(13)

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

3 實例仿真

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

3.1 交叉口數據信息

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

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

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

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

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

3.2 優化結果對比

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

表2 交叉口信號配時參數

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

由圖3可以看出，傳統的Lagrange乘子法由于劣質的罰參數，導致數值的震蕩劇烈無法迅速收斂，求得的解也無法快速趨向于可行域。而通過罰參數自適應更新的Lagrange乘子法，可以根據當前解偏離可行域的距離來適當加大罰參數，在7代左右就達到穩定值(傳統乘子法14代以后才漸漸達到穩定)，并且求得的最小值也更優。可見該方法的收斂性和快速性優于傳統的Lagrange乘子法。這里具體只研究改進Lagrange乘子法的優化配時等問題。

為更加直觀地看出本文方法與智能算法在交通信號控制應用中的區別，將上述案例分別利用標準遺傳算法和差分進化算法進行優化，得到的進化曲線如圖4所示。

圖4 兩種智能算法的進化曲線

表3 算法耗時對比

Lagrange乘子法首先是找到最優值的大致范圍，隨后對當前解進行調整，使其位于可行域范圍內；而智能算法是一個逐漸尋優的過程，算法迭代過程相對復雜。

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

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

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

表4 信號配時優化結果對比

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

3.3 VISSIM仿真

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

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

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

圖6 優化前后配時于VISSIM仿真結果

表5 在VISSIM中各種配時的仿真結果

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

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

4 結論

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

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