信號交叉口相位間談判博弈協調控制

夏新海，許倫輝，楊景山，彭智敏

(1.廣州航海學院 港口與航運管理學院，廣東 廣州 510725；2.華南理工大學 土木與交通學院，廣東 廣州 510640；3.廣州航海學院 土木與工程管理學院，廣東 廣州 510725；4.廣州大學 機械與電子工程學院 廣東 廣州 510006)

0 引言

交叉口是城市路網中各向交通流匯聚交錯的地點，對它的交通信號控制是城市交通控制系統的核心,并且是實現干道和區域交通信號協調控制系統的基礎。要實現未來城市交通信號控制的智慧化，交叉口交通信號控制顯得極為重要[1]。交叉口交通信號控制用到的Webster方法、沖突點法等方法難以適應交通條件發生的變化。常規感應控制沒有考慮到相位之間的矛盾，增加綠燈時間可能會造成其他相位平均車輛排隊長度增大。雖然SCOOT,SCATS,OPAC等自適應交通信號控制系統比固定交通信號控制和感應式交通信號控制方案的性能要好，但其往往在可擴展性和魯棒性等方面受到限制。近10年來神經模糊網絡、tabu搜索、自組織協調圖、情感算法、遺傳算法等方法用來改進交叉口交通信號控制方案，但存在指數復雜性和需要大量數據來校準參數等局限性。

博弈論是研究理性決策者之間策略交互的數學模型，其被認為是解決城市交通信號控制問題的合適方法，有利于提高協調控制效率，能較好地適應交通需求水平的動態變化[2-4]。早期，一些學者(如Villalobos 等[5]，楊曉芳等[6]，朱銘琳等[7]，李建明等[8]，Clempner 等[9])使用非合作博弈來進行交叉口相位交通信號協調控制，并取得了一定的效果。但非合作博弈各參與者沒有交互動作等信息，其納什均衡缺乏對效率的考慮，并容易陷入局部最優解，協調效率有限。Elhenawy等[10]采用斗雞博弈來進行單交叉口交通控制，但未考慮交通信號設置。于是，一些學者結合合作和非合作博弈進行信號控制交叉口相位協調控制研究。彭敏等[11]采用二人合作博弈確定交叉口放行方向以及二人非合作博弈來確定該方向上各信號燈放行時間來建立交叉口交通信號博弈模型。Zhao等[12]提出了基于協調博弈和Pareto效率的交叉口交通信號控制，利用非合作博弈框架對交叉口進行建模，利用合作博弈模型中的Pareto效率概念進行求解。也有學者利用聯盟博弈研究單交叉口交通信號控制。如盧維科等[13]建立了以執行綠燈的相位和下一相位為聯盟的單信號交叉口合作博弈控制模型。但是上述研究對相位合作時交叉口交通信號控制系統的漸近穩定性缺乏深入的研究。

也有學者將車聯網和博弈論相結合研究交叉口交通信號控制。Xu等[14]提出了一種V2I技術環境下延誤車輛選擇路徑與交通信號調整之間的博弈模型，但參與人不是相位。談判博弈作為一種合作博弈，將其應用于交叉口各相位協調控制的研究較少。Tan等[15]，Abdelghaffar等[16]利用納什談判解來優化交叉口交通信號控制，但缺乏算法的穩定性分析。Valencia等[17]、夏新海等[18]嘗試利用談判博弈進行多個交叉口交通信號協調控制，但缺乏信號控制交叉口效用空間的凸性分析，因此在交通需求處于過飽和狀態時不一定能保證算法的最優性。

談判博弈模型允許各參與者之間通過交互信息進行協商，適合離散動態交互問題建模。鑒于此，本研究主要目的是利用談判模型建立信號控制交叉口相位間博弈協調框架，將其轉化為局部數學規劃問題，并對其相位效用空間進行了凸性分析。在此基礎上，設計有效的求解算法，并對算法的穩定性進行理論分析。最后設計不同的交通需求情景，驗證所提出算法的有效性和穩定性。

因此，本研究就理論貢獻而言，對相位效用空間的凸性和相位合作時交叉口交通信號控制系統的穩定性進行了理論分析。從方法論的角度來看，相位利用感知的效用選擇合作，保持相位局部控制決策的有效性，并盡可能實現整個交叉口信號控制的效率，以計算效率高的方式找到相位信號控制問題的合作解決方案。

1 信號控制交叉口相位間談判博弈模型

本談判博弈模型針對信號控制十字交叉口。以其信號控制交叉口兩相鄰相位為例，相位1和2(其中相位1為某一時刻末將要執行綠燈相位，相位2為相位1的下一相位)總是存在一種矛盾。隨著綠燈時間的增大，執行綠燈相位1的平均車輛排隊長度變小，而執行紅燈相位2的平均車輛排隊長度在增加。這種交互可以描述成兩個相位對綠燈資源的博弈。

因此，城市交叉口交通信號控制中每個相位在進行局部交通信號控制時均受到其他相位局部交通信號控制的影響，并且每一相位需要在交叉口交通信號控制性能和相位局部交通信號控制性能之間進行權衡，使得各相位間交通信號控制能夠共創雙贏，因此各相位間為了相互的利益需要進行合作，進行控制動作等信息的交互。此交互環境屬于離散動態交互。車聯網技術的發展使得各相位之間以及各相位和交叉口交通信號控制器之間能交換性能指標和控制方案等信息，因此交叉口交通信號控制問題可用時間離散動態談判博弈框架來描述。

假設交通信號控制交叉口由M個信號控制相位組成，其信號周期為C(s)，最大和最小周期分別為Cmax,Cmin,相位的綠燈間隔時間為Ii(s),每個相位的綠燈持續時間為Gi(s)，相位最小綠燈時間為Gmin(s)。

定義此談判博弈模型為元組G=(N，{Ai}i∈N,{φi(a(k)}i∈N,{ηi}i∈N)。其中N={1，…,M}為信號控制交叉口中各相位的集合。

Ai為信號控制交叉口中第i個相位的可行動作集合。對于每個相位，其動作ai∈Ai，Ai={1，0}。其中，動作1表示保持綠燈指示，意味著沒有信號變化(即綠燈指示將保持綠色；紅燈指示將保持紅色)。動作0表示改變綠燈指示，意味著交通信號指示將在仿真時間間隔內改變(即綠燈指示將變為黃色，然后變為紅色；紅燈指示將變為綠色)。當某一個相位保持綠燈指示，而所有其他相位保持紅燈指示。

φi(a(k))：A1×…×AM→R：為在時間步k時，當信號控制交叉口各相位采用聯合動作a(k)時第i個相位的效用函數，其決定了信號控制交叉口中第i個相位的喜好和策略，并給出了一定程度的理性。其中a(k)為聯合動作向量，a(k)=(a1,a2，…,aM)。

博弈中每個相位的效用函數φi可定義為應用特定動作后每個相位相應車道車輛排隊長度總和的估計值，根據如下思路計算。

在仿真中，使用Vissim軟件監控車速，假設車輛與交叉口交通信號控制器有某種形式的通信(即，車輛與基礎設施[V2I]通信)，或使用閉路電視攝像機的視頻圖像處理器的檢測能力，包括車輛排隊檢測、車輛方向的檢測、車速檢測，并且計算出進入交叉口的車流。所有進入車道的這些參數都會不斷更新。

(1)

(2)

每個相位的效用為：

(3)

式中，Δt為更新時間間隔；Qi(t+Δt)為相位i在Δt之后的估計排隊長度；Qinl為車流到達率(veh/h/車道)；Qoutl為車流駛出率(veh/h/車道)。Qoutl通常在連接的下游端測量，而Qinl則在距離連接的下游端相當于阻塞密度上的談判初始點值(定義見下文)處測量。

使用運動學公式(4)來估計Qinl,其中sgn(x)是符號函數。

(4)

對于Qoutl，計算可分為3種情況。對處于綠燈相位并希望保持當前相位(條件c1)的相位，可以簡單地使用飽和流率進行估算；對處于紅燈相位并希望切換到綠燈相位(條件c2)的相位，不能使用飽和流率(綠燈相位將剛剛開始)，因此使用運動學公式來估計；對于其他條件，駛離車輛的數量為零。因此Qoutl的公式如(5)所示：

(5)

式中，μl為車道l的飽和流率;ΔL可用如下公式估算：

(6)

ηi為信號控制交叉口中第i個相位的談判初始點，為期望性能的最大損失，其反映信號控制交叉口中第i個相位是否參與合作的意愿。

交叉口交通信號控制的目標是使不同相位的排隊長度最小化并相等。根據文獻Nash[19]的雙人博弈談判模型，此博弈問題可轉化為如下局部線性數學規劃問題(其中log(_)函數來自于Nash乘積的轉換)來求解最優動作：

(7)

s.t.:

ηi(k)≥φi(a(k))；Cmin≤C≤Cmax；

式中wi=1/M。

2 信號相位效用空間凸性分析

根據文獻Nash[19]，若效用空間{φi(a(k)}i∈N為有界的閉凸集，則式(7)存在唯一的最優解，即能保證收斂到最優解。因此，為了設計有效算法求解談判博弈模型，需要對信號控制相位效用空間凸性進行分析。

設一信號周期長為C的交通信號，其有效紅燈時間為R；有效綠燈時間為G；有效綠燈時間內的飽和流率為μ；車輛平均到達率為λ；通行能力為c(c=μG/C)；一個周期內的服務車輛數為n′(n′=λC)；延誤車輛數為n。

(1)非飽和交通需求下(λ

非飽和交通條件下一個信號周期內全部車輛的總延誤時間，用ω(veh·s)表示，可以得到一個周期內每輛車的平均延誤時間為[20]：

(8)

設G1,G2為兩個相位(南北車流和東西車流各一個相位)的有效綠燈時間；L為損失時間；μ為進口車道飽和流率；λ為進口車道到達率，則有R1=L+G2,R2=L+G1,并且L=C-G1-G2。

4個入口車道的總車均延誤為：

(9)

式中i為入口車道編號。根據式(8)、(9)有：

(10)

將R1,R2,C用L，G1,G2替換，4個進口道上的平均車輛排隊長度之和為：

(11)

因此，需要證明車輛排隊長度函數(y)是一個凸函數。令

式中，a，b，c，d是正常數，于是有：

(12)

設η為特定車道上可存儲的最大車輛排隊長度，根據前述，博弈效用定義為車輛排隊長度，即φ=y。因為完成了這一步的y是一個凸函數，所以不等式(y(G1，G2)≤常數)定義了一個凸集，即φ≤η為凸集。式(12)可以推廣到任意數量有多個流向車流的相位。

因此對于非飽和交通需求，效用空間是凸的，局部優化問題(7)能保證收斂到唯一的最優解。

(2)過飽和交通需求(λ>c)，效用空間不是凸的

對于過飽和的交通條件，綠燈間隔(即λiC>μiG)結束時，排隊車輛沒有被清除，剩余的排隊車輛在整個分析時間段T內持續增加。

為了計算在綠燈期間無法提供放行服務的排隊車輛數，必須在式(12)中添加4個進口道與過飽和延誤有關的附加項(y2)。過飽和平均排隊長度(y2)為：

(13)

式中，Zi為正增凸函數;Z-1為正減凸函數;μi為正常數。因此，μi(Zi-L)Z-1為一個凸函數，-μi(Zi-L)Z-1為一個凹函數。于是，對于過飽和交通需求，總排隊長度函數不是凸函數。

因此，對于過飽和交通需求，效用空間不是凸的，當車輛排隊溢出超過初始參考點時，局部優化問題(6)不能保證收斂到最優解。

3 談判博弈模型求解算法設計

3.1 基本思想

(1)保證算法的最優性

根據本研究第2部分研究結論，對于非飽和交通需求下，局部優化問題(6)是可行的，算法能保證收斂到唯一的最優解。而對于過飽和交通需求，局部優化問題(6)不可行。因此，為了保證算法收斂到最優解，算法在當時間步k=0時，將相位談判初始點設置為基于車道長度可容納的最大可測排隊長度。

(2)避免繁瑣的迭代過程

算法由一系列步驟組成，其結果是以合作或非合作的方式解決局部優化問題(6)[19]。信號控制交叉口相位i與其他相位j交換動作、談判初始值，可以避免繁瑣的迭代過程，信號控制交叉口各相位根據從合作行為中感知的效用來決定是否合作。

(3)合理構建初始點

給定談判初始點的更新條件，其值降低(這意味著相位i決定合作)為增加合作行為的需求提供了強有力的激勵；但是，使其值等于效用函數的當前值(意味著相位i決定不合作)為改變不合作的決策而提供了激勵。鑒于此，ηi值構建如下：

(14)

式中α為系數，0≤α≤1。

3.2 算法流程

(1)時間步k=0,每一相位的ηi設置為相位所屬的基于車道長度可容納的最大可測車輛排隊長度。

(2)在每一時間步k，每一相位i將ai，ηi值發送給其他相位。

(3)對于每一相位i=1，…,M，根據接收到的其他相位的信息，求解局部優化問題(7)。

(5)每一相位更新其談判初始點。如果局部優化問題(7)可行(非飽和交通需求下)，相位i根據ηi(k+1)=ηi(k)-α(ηi(k)-φia(k))來更新談判初始點。如果局部優化問題(7)不可行(過飽和交通需求下)，相位i根據ηi(k+1)=φia(k))更新談判初始點。

(6)所有相位將更新的控制動作和談判初始點發送給其他相位。

(7)轉到步驟(2)。

從算法流程中看出，該算法只需求解一個優化問題，其減少了有關相位之間的通信，減輕了在每個時間步處理多個優化問題的有關分布式交通信號控制的計算負擔。

4 算法穩定性理論分析

談判博弈模型求解算法的穩定性取決于每個相位是否決定合作。因此，為了證明此方法的穩定性，考慮了兩種情況：

(1)所有相位總是相互合作。

(2)一些相位不合作，僅在少量的時間步內開始合作。這里不考慮所有相位決定不合作的情況，因為根據第3.1節中提出的談判初始點的構建，這種情況只有當k→∞，φi(a(k))→∞發生。根據前述，對于不合作的相位有ηi(k+1)=φi(a(k))。

(15)

(16)

(17)

(18)

(19)

在時間步k+1, 全局效用函數的初始值由式(20)給出：

(20)

根據式(16)有：

(21)

并且根據式(19)有：

(22)

其中有

a-i(k)]，

(23)

(24)

式中M(k)≤0，定義如下：

(25)

(1)?(a(k))≠0，L(a(k))≠0，

(2)對于a(k)=0，L(a(k))=0，

(3) ?k,L(a(k+1))-L(a(k))≤M(k)。

其中M(k)為k的一個非遞增函數時，控制系統的狀態收斂到原點附近。因此，系統是穩定的。由于不能證明M(k)收斂到原點，因此在一般情況下不能保證漸近穩定性。

一種特例是所有相位總是決定合作，即?k，C(k)=N。在這種情況下：

(26)

(27)

(28)

因此：

(29)

那么有

(30)

根據前述，L(a(k))為二次正凸函數，滿足：

(1)?(a(k))≠0，L(a(k))≠0。

(2)對于a(k)=0，L(a(k))=0。

所以有：

(1)?k，Mc(k)>0。

(2)L(a(k+1))-L(a(k))是k的遞減函數，其下限為0。

因此，L(a(k))滿足Lyapunov函數的條件，并證明了當相位總是決定合作時交叉口交通信號控制系統的漸近穩定性。

5 仿真試驗分析

5.1 測試交叉口

仿真試驗將在具有4個方向(東、南、西、北)進口道的十字交叉口進行測試，每個進口道由3條車道組成。劃分4個相位，分別為：東西進口車流直行及右轉，東西進口車流左轉，南北進口車流直行及右轉，南北進口車流左轉。各相位原始交通需求(O-D)矩陣見表1，其在VISSIM仿真平臺中設置。

表1 原始交通需求O-D矩陣(單位:veh/h)Tab.1 Original traffic demand O-D matrix(unit:veh/h)

5.2 仿真參數和測試指標

采用韋伯斯特方法對固定配時方案進行優化，黃燈時間ty為3 s,全紅時間為2 s。感應控制的最大綠燈時間和固定交通信號控制方案相同。感應控制的最小綠燈時間為6 s,最大綠燈時間為31 s,綠燈延長時間為2 s。因當Δt很小時，即接近黃燈時間時，對應切換函數的下一相位的效用函數在太短的有效綠燈時間內緩慢增加。當Δt較大時，由于使用的所有變量都是在一個時刻檢測到的，因此使用的運動學公式見式(4)的估計將有較大的偏差，故取Δt=17 s。其他仿真參數值設置如下。

臨界速度：sTh=3.6(km/h)；飽和流率：μ=1 655(veh/h/ln)；自由流速度:80(km/h)；阻塞密度：150(veh/h/ln)。時間步k=0,各相位的談判初始點設置為ηi=12。采用平均車輛排隊長度、平均車輛行駛時間、總車均延誤對本研究方法、韋伯斯特固定信號控制和感應控制方法的性能進行評價。

5.3 結果和討論

以韋伯斯特的固定信號控制和感應控制方法為基準來評估本研究方法的性能。使用3個仿真場景：1個是表1所示的原始O-D交通需求矩陣；第2個是較低的交通需求，即原始O-D交通需求矩陣的80%；第3個是較高的需求，即原始O-D交通需求矩陣的120%。第1和第2個交通需求屬于非飽和交通需求，第3個交通需求屬于過飽和交通需求。

(1)算法有效性分析

表2給出了在原始交通需求下，Δt=17 s時，通過使用韋伯斯特的固定信號控制、感應控制方法和本研究方法得到的每條車道的平均車輛排隊長度的均值和標準差。很明顯，雖然本方法并不是對幾乎所有車道都是最好的，但最后的結果表明本研究方法是最好的。另一方面，韋伯斯特方法在交通流量較大的相位效果較好，感應控制方法在交通流量較小的相位效果較好，這使得同一算法下不同相位的差異較大。然而，對于本研究算法，無論交通流水平如何，幾乎所有車道的平均車輛排隊長度都在同一水平上。由表2可知，采用本研究算法進行交通信號控制時，各個相位相關車道平均車輛排隊長度波動趨勢保持一致，即1個信號周期結束時，不同相位之間平均車輛排隊相差不大，較好地實現了車輛排隊長度均衡，表明了博弈中各個相位之間不是對立而是追求共同收益的關系。因此，可以將本研究算法具有更好的協調均衡性，以確保交通信號系統更有效。

表2 在原始交通需求下，不同方法下該測試交叉口各車道的平均車輛排隊長度均值和標準差Tab.2 Standard deviations and mean values of average vehicle queue length for every lane of tested intersection by different methods under original traffic demand

不同方法和不同交通需求下本研究方法與韋伯斯特方法和感應控制方法相比性能改進情況見表3。可以看出，除了在較低的交通需求下感應控制方法運行較優外，本研究方法的3個有效性測試指標的平均值相比之下都取得更好的值。特別是過飽和交通需求(高交通需求)時，通過在時間步k=0時將相位談判初始點設置為基于車道長度可容納的最大可測排隊長度，本算法仍然保證收斂到最優值，并且相對于非飽和交通需求，改進效果更好。

表3 不同交通需求和不同方法的性能指標值Tab.3 Performance indictors obtained by different methods under different traffic demands

(2)算法穩定性分析

表4顯示了不同交通需求下不同性能指標的標準差，可以看出本研究方法除了在較低及原始的交通需求下部分指標的標準差略低于感應控制方法的部分指標的標準差外，其他情況標準差明顯低于另外兩種方法，即各相位車流到達率類似的情況下，平均車輛排隊長度等指標不會出現較大波動。這是因為相位在決定合作過程中進行動作和談判初始點的交互，交叉口交通信號控制系統具有一定的漸近穩定性。因此本研究方法更穩定。

表4 不同交通需求下不同方法的性能指標值的標準差Tab.4 Standard deviations of performance indictors obtained by different methods under different traffic demands

6 結論

本研究提出了一種基于實時談判博弈優化模型的信號控制交叉口相位協調控制方法。在進行相位效用空間凸性分析的基礎上設計有效的求解算法。此算法可以避免繁瑣的迭代過程，并能保證算法在過飽和交通需求下收斂到最優解。對算法的穩定性進行了理論分析。當相位總是決定合作時交叉口交通信號控制系統具有漸近穩定性。通過仿真試驗分析對該算法與韋伯斯特方法和感應控制方法在平均車輛排隊長度、車均行駛時間和平均總延誤方面進行了比較。結果表明，在不同交通需求下，該方法具有更好的有效性和穩定性。

未來進一步將本研究的算法擴展到多交叉口，并引入智能網聯技術[22]，以利于城市交通信號協調控制。另外，本研究采用可變相序，雖然可以通過提取道路數據選取最有價值通行相位，但是改變交叉口的相序時沒有考慮駕駛員停車按相位順序等待綠燈的習慣，以及由于相位切換造成的處理沖突的時間變長問題，這些將是以后的研究方向。