楊利紅，王列偉

(中國電子科技集團公司第三十八研究所 合肥公共安全技術(shù)研究院，安徽 合肥 230000)

0 引 言

由路段、交叉口、部署在交叉口的交通信號燈，以及車輛和人的動態(tài)行為組成的城市道路交通網(wǎng)絡(luò)系統(tǒng)可以被看成一類含有大量不確定性的復(fù)雜的離散事件系統(tǒng)。而城市道路交叉口信號系統(tǒng)的設(shè)計與優(yōu)化是提高城市道路利用率、減少擁堵的關(guān)鍵。文中研究了基于Petri網(wǎng)的道路交叉口信號控制系統(tǒng)的建模及優(yōu)化方法。

Petri網(wǎng)是一種常見的離散事件系統(tǒng)模型[1]。Petri網(wǎng)模型對動態(tài)系統(tǒng)中常見的并行(parallelism)、同步(synchronization)、資源共享(resource sharing)等特性具備強大表述能力，廣泛應(yīng)用于工業(yè)制造系統(tǒng)、軟件系統(tǒng)設(shè)計、工作流、并行計算、交通系統(tǒng)等領(lǐng)域。近年來，使用Petri網(wǎng)對道路交叉口系統(tǒng)進行建模的方法受到學(xué)者的廣泛關(guān)注，具有代表性的成果見文獻[2-8]。其中文獻[2-5]建立基于Petri網(wǎng)的微觀交通模型，通過時延Petri網(wǎng)、隨機Petri網(wǎng)、著色Petri網(wǎng)等結(jié)構(gòu)，描述交叉口信號燈色的切換、車輛在道路上的移動速度以及車輛在交叉口內(nèi)可能的轉(zhuǎn)向和路徑選擇等信息。系統(tǒng)仿真證明，通過這類模型可以較準(zhǔn)確地計算出車輛排隊長度以及車輛在交叉口的平均等待時間。文獻[6-8]不以單個車輛作為建模對象，而是類似于連續(xù)時間系統(tǒng)(continuous-time system)，主要以交通流量、車輛速度，以及車輛密度等作為描述對象，建立基于混合網(wǎng)結(jié)構(gòu)的宏觀交通模型。然而，上述這些交叉口建模及優(yōu)化算法都是基于傳統(tǒng)的交通信號固定相序邏輯，沒有充分考慮車流到達的隨機性、突發(fā)性等不規(guī)律的動態(tài)特征，優(yōu)化空間有限。在文獻[9-10]中，作者雖然考慮了基于可變相序的優(yōu)化算法，但是優(yōu)化函數(shù)大都是根據(jù)當(dāng)前或者歷史數(shù)據(jù)構(gòu)造(例如通過當(dāng)前的車輛排隊長度、車輛停留時間、車輛通過時間等)，而沒有考慮系統(tǒng)狀態(tài)的預(yù)測，對車流實時狀態(tài)的適應(yīng)性有待提高。

文中首先建立了基于混合Petri網(wǎng)的可變相序交通信號模型，并創(chuàng)新性地提出了一種基于MPC(model predictive control，模型預(yù)測控制)[11-12]的優(yōu)化控制算法。根據(jù)MPC控制模型，該算法在每一個采樣瞬間通過求解一個有限時域開環(huán)最優(yōu)控制問題，獲得在一個完整交通信號周期內(nèi)的最優(yōu)相序及綠燈通行時間，之后放行該最優(yōu)解中的第一個相位，等到該放行相位結(jié)束后，再更新系統(tǒng)狀態(tài)，并將當(dāng)前狀態(tài)作為最優(yōu)控制問題的初始狀態(tài)，求解下一個最優(yōu)相序。

1 交通信號可變相序的Petri網(wǎng)模型

Petri網(wǎng)有多種定義形式，其中應(yīng)用比較廣泛的是庫所/變遷(place/transition)網(wǎng)。經(jīng)典離散Petri網(wǎng)的形式化定義如下：

定義：一個Petri網(wǎng)系統(tǒng)是一個二元組，其中N=是一個網(wǎng)狀結(jié)構(gòu)。(1)P和T是不相交的，分別表示庫所和變遷的有限集合；(2)Pre,Post∈N|P|×|T|是關(guān)聯(lián)矩陣，N表示非負(fù)整數(shù)集合；(3)M0∈N|P|是系統(tǒng)的初始狀態(tài)。

假設(shè)pi,i=1,2,…,|P|和tj,j=1,2,…,|T|分別表示庫所和變遷，在Petri網(wǎng)模型圖中通常用圓圈和矩形框表示。在關(guān)聯(lián)矩陣中，如果Pre[i,j]>0，則在網(wǎng)系統(tǒng)中有一條從pi指向tj的弧，弧上的權(quán)重為Pre[i,j]；在關(guān)聯(lián)矩陣Post中，如果Post[i,j]>0，則在網(wǎng)系統(tǒng)中有一條從tj指向pi的弧，弧上的權(quán)重為Post[i,j]。如果模型中的一條弧上不標(biāo)明數(shù)字，則默認(rèn)該條弧上的權(quán)重為1。Petri網(wǎng)的標(biāo)識狀態(tài)(又稱為marking)由分布在各個庫所中的托肯(token)表示。系統(tǒng)的全局標(biāo)識狀態(tài)向量用M表示，非負(fù)整數(shù)M[pi]表示庫所pi中包含的托肯個數(shù)，也稱為庫所的標(biāo)識。在系統(tǒng)狀態(tài)M下，一個變遷被稱為使能(enabled)，當(dāng)且僅當(dāng)該變遷的輸入庫所中都包含有足夠多的托肯，并使得式1成立。

?pi∈*tj,M[pi]≥Pre[i,j]

(1)

其中，*tj表示變遷tj的所有輸入庫所的集合。

當(dāng)一個變遷使能時，該變遷具備觸發(fā)(fire)條件，即系統(tǒng)中有足夠的資源在其輸入庫所中。一個變遷觸發(fā)后會將其輸入庫所中的資源(托肯)轉(zhuǎn)移到其輸出庫所中。當(dāng)一個或者多個變遷觸發(fā)后，系統(tǒng)進入新的狀態(tài)M'，并滿足基本狀態(tài)等式2。

M'=M0+(Post-Pre)·σ,M'∈N|P|,σ∈N|T|

(2)

其中，σ為觸發(fā)向量，σ[j]為系統(tǒng)從初始狀態(tài)M0進入狀態(tài)M'的過程中，變遷tj觸發(fā)的次數(shù)。

道路交通系統(tǒng)模型可以大致劃分為車流模型、交叉口模型，以及信號燈及其控制模型等部分。文中重點考慮交叉口及信號燈控制模型，對于非交叉口內(nèi)的部分，只考慮進出交叉口的禁止車輛隨意變道區(qū)域的車流模型。如圖1(a)所示的交叉口模型，4個方向均為雙向六車道，且每個方向進入交叉口車流分為直行、左轉(zhuǎn)和右轉(zhuǎn)。

(a)交叉口車流示意圖 (b)4相位信號控制方案

(c)交叉口車流的Petri網(wǎng)概括模型

根據(jù)車流模型的定義并假設(shè)交通信號系統(tǒng)采用固定相序，文中使用比較通用的4相位信號控制方案，如圖1(b)所示。相位1和2分別為允許南北方向的直行加右轉(zhuǎn)和左轉(zhuǎn)車流通行；相位3和4分別為允許東西方向的直行加右轉(zhuǎn)和左轉(zhuǎn)方向車流通行。

圖1(c)為該交叉口的Petri網(wǎng)概括模型(利用庫所和變遷的局部特性(locality)，可通過逐步細化得到滿足仿真要求的加細模型[13])。模型中的庫所用于對交叉口內(nèi)的或者準(zhǔn)備進入交叉的車流建模，而變遷用于對車流駛?cè)牖蛘唏偝鰧?yīng)車流隊列的事件建模。為了便于說明，對模型中的所有節(jié)點采用了統(tǒng)一的命名方式。對于變遷，其命名規(guī)則為tx(y)z，其中x=n,s,w,e分別表示北、南、西、東四個方向，y=l,c,r分別表示左轉(zhuǎn)、直行和右轉(zhuǎn)，z=i,o分別表示駛?cè)牒婉偝觥＠?，變遷twli的含義為從交叉口的西面駛?cè)胱筠D(zhuǎn)車道，變遷two的含義為從交叉口的西面駛出交叉口。對于庫所，采用了類似的命名規(guī)則px(y)(z)，例如庫所pwc表示從交叉口西面進入直行車道的車流隊列，庫所peo表示從交叉口東面駛出的車流隊列。庫所在狀態(tài)M下的托肯數(shù)M[px(y)(z)]代表了對應(yīng)車流隊列中車輛的個數(shù)。以從交叉口西面進入左轉(zhuǎn)車道，并由從交叉口北面駛出交叉口為例。車輛到達左轉(zhuǎn)車道時變遷twli被觸發(fā)，相應(yīng)車流隊列的排隊數(shù)加1，即M[pwl]加1；隨后變遷twlo被觸發(fā)，車輛駛出左轉(zhuǎn)車道，進入交口北面駛出車流隊列(由庫所pno表示)；最終變遷tno被觸發(fā)，車輛駛出交叉口。

根據(jù)交通信號控制系統(tǒng)的特性，采用基于有限語義服務(wù)器語義(finite server semantics)的固定時延(constant delay)離散時間Petri網(wǎng)進行建模。對于車流部分，采用基于無限服務(wù)器語義(infinite server semantics)的隨機時間Petri網(wǎng)建模，也就是說，每個變遷的觸發(fā)延遲時間為符合指數(shù)分布的隨機數(shù)[10]。基于無限服務(wù)器語義的離散時間Petri網(wǎng)，又稱為馬爾可夫Petri網(wǎng)(Markovian Petri net)。對于在一個指定標(biāo)識M下的變遷tj，其觸發(fā)時間符合參數(shù)為λj·enab(tj)的指數(shù)分布，其中λj為變遷的觸發(fā)速率，enab(λj)為變遷的使能度。

(3)

馬爾可夫Petri網(wǎng)及其在交叉建模中的應(yīng)用具體可參見文獻[8]。基于無線服務(wù)器語義的連續(xù)時間Petri網(wǎng)得到了廣泛的應(yīng)用[14-16]。在任意時間點τ，變遷tj的輸出流(flow)被f(tj,τ)定義為:

f(tj,τ)=λj·enab(tj,τ)=

(4)

可以看出，在連續(xù)Petri網(wǎng)中，變遷的使能度不再限制為整數(shù)。

道路交叉口模型中的另一個重要部分是信號控制模型。為方便討論，文中將綠燈和黃燈歸為一類允許通行信號，因此信號周期由各個相序的通行時間之和組成。傳統(tǒng)的固定相序信號控制方法中，各個相位的車流根據(jù)預(yù)先設(shè)定好的固定順序依次獲得通行權(quán)。該方法雖然簡單，但是卻沒有充分考慮各個方向到達車流量的動態(tài)特征，無法對車流的變化做出及時有效的響應(yīng)，優(yōu)化空間較小。因此，文中提出了一種基于Petri網(wǎng)的可變相序控制模型，系統(tǒng)根據(jù)優(yōu)化目標(biāo)函數(shù)，動態(tài)選擇相序及每個相位的綠燈通行時間。圖1(b)中4相位交通信號系統(tǒng)的可變相序控制模型如圖2所示。

模型中庫所p1,p2,p3,p4用于對相位1到相位4的通行綠燈狀態(tài)建模，當(dāng)庫所中含有托肯時，表示其對應(yīng)相位中的車流具有通行權(quán)。例如，如果庫所p1中含有托肯，則相位1中的車流2、3、8、9具備了通行權(quán)(見圖1)。庫所pe1,pe2,pe3,pe4用于確保在一個完整的信號周期內(nèi)，任何一個相位都只能獲得一次通行權(quán)，從而避免某個相位的車流長時間處于等待狀態(tài)；在狀態(tài)M下，如果M[pei]=1，表示在當(dāng)前的信號周期內(nèi)，相位i尚未獲得過綠燈通行權(quán)，其中i=1,2,3,4；只有當(dāng)庫所p0和pei同時含有托肯時(M[pei]=M[p0]=1)，相位i才有機會獲得綠燈通行權(quán)。庫所ps的作用是標(biāo)識一個新的信號周期的開始。在文中的4相位交通信號控制模型中，M[ps]=4表示所有的相位都獲得了一次通行權(quán)，信號控制系統(tǒng)將進入下一個信號周期。

圖2 交叉口4相位可變相序交通信號控制模型

變遷t1、t2、t3、t4為瞬時變遷(immediate transition)，也就是假設(shè)其變遷觸發(fā)時間為零。當(dāng)瞬時變遷被使能時，立即完成觸發(fā)并更新系統(tǒng)狀態(tài)。變遷ta、tb、tc、td為固定時延變遷(determined delay transition)，每個變遷具有一個延遲時間，分別表示為δa、δb、δc、δd。當(dāng)一個固定時延變遷在時間點τ被使能，則經(jīng)過其對應(yīng)的時延δi，在時間點τ+δi變遷ti完成觸發(fā)并更新系統(tǒng)狀態(tài)。

在初始狀態(tài)下，M[pe1]=M[pe2]=M[pe3]=M[pe4]=M[p0]=1，因此變遷t1、t2、t3、t4都被使能，這在Petri網(wǎng)模型中形成了一個典型的沖突關(guān)系；在對應(yīng)的交通信號模型中，這意味著所有的相位都有機會在下一時刻獲得綠燈通行權(quán)。因此，Petri網(wǎng)模型中的沖突解決策略決定了信號系統(tǒng)的相序選擇。例如，假設(shè)此時的沖突解決策略是變遷t1、t2、t3、t4的優(yōu)先級依次降低。在初始狀態(tài)，變遷t1將優(yōu)先獲得觸發(fā)，庫所p0和pe1中的托肯被轉(zhuǎn)移到p1中，因此相位1對應(yīng)的車流獲得綠燈通行權(quán)，此時ta被使能；經(jīng)過時延δa(相位1的綠燈通行時間)后，變遷ta觸發(fā)，庫所p1中的托肯重新轉(zhuǎn)移到p0中，同時庫所ps也獲得一個托肯；注意，此時庫所pe1中的托肯被清空，因此變遷t1不再使能，即在該周期內(nèi)相位1不再獲得通行權(quán)；根據(jù)優(yōu)先級，下一時刻變遷t2觸發(fā)(相位2的車流獲得通行權(quán))；當(dāng)變遷t1、t2、t3、t4全部獲得觸發(fā)后，庫所pe1,pe2,pe3,pe4中的托肯全部被清空，而ps獲得4個托肯，因此變遷ts被使能，ts觸發(fā)后系統(tǒng)信號控制系統(tǒng)回到初始狀態(tài)，意味著一個新的信號周期開始。

2 基于MPC的可變相序優(yōu)化算法

預(yù)測模型的建立和滾動優(yōu)化過程是MPC控制算法的核心。文中創(chuàng)新性地將MPC算法框架應(yīng)用到交通信號可變相序的優(yōu)化問題中。

在任一個信號周期的起始時刻，以信號周期的總時長作為MPC模型的優(yōu)化時間域，通過建立優(yōu)化函數(shù)，求解在該信號周期內(nèi)的最優(yōu)相序策略；在獲得當(dāng)前時間點的相序及綠燈通行時間后，應(yīng)用當(dāng)前第一個相位的通行策略，直到該相位綠燈時長結(jié)束；之后在下一相位通行開始前，再滾動式地優(yōu)化有限時域內(nèi)的控制策略，獲取下一個最優(yōu)相位及其綠燈通行時間。需要注意的一點是，雖然與傳統(tǒng)MPC算法類似，為了使得模型能夠盡量細致地描述系統(tǒng)在整個時間域內(nèi)的動態(tài)特征，從而取得較好的優(yōu)化效果，在優(yōu)化模型中采用了較小的步長(1s)。但是由于每個相位的通行時間必須是連續(xù)的，因此在計算出當(dāng)前采樣時刻的最優(yōu)控制策略后，采取的控制動作不以優(yōu)化步長為單位，而以單個相位的通行綠燈時長為單位。

根據(jù)圖1、圖2中的交通流及信號控制模型，求解最優(yōu)相序的問題可以轉(zhuǎn)換為求解變遷t1、t2、t3、t4的最優(yōu)沖突解決策略問題。定義對角線矩陣W為沖突解決矩陣，其對角線元素的定義如下：

(5)

其中，Λ={t1,t2,t3,t4}。

相序優(yōu)化考慮的優(yōu)化指標(biāo)可以有很多種，比較常用的包括排隊長度、車流通過率、車流停留時間等。在該算法中，假設(shè)當(dāng)前的采樣時刻為τ，在一個完整信號周期T中，交叉口內(nèi)各方向車流平均排隊長度構(gòu)造相序優(yōu)化的目標(biāo)函數(shù)J為：

(6)

其中，pi∈ψ={pno,pwo,peo,pso}；Mτ+δ[pi]表示在時刻τ+δ庫所pi對應(yīng)隊列的排隊長度。

本文標(biāo)題，取意于宋代無名氏的《一剪梅·漠漠春陰酒半酣》最后一句：“篝燈強把錦書看。人在江南，心在江南”。此時的作者，在“江南”耶、不在耶？——所謂“錦書”指夫妻間書信，傳情遞意，且要“篝燈強看”，那般地眷戀、向往、思念，是全詞情意落位的重心點。

在每一個采樣周期，通過解決優(yōu)化問題(見式7)，求解在信號周期內(nèi)的T個最優(yōu)的沖突解決矩陣Wτ,Wτ+1,…,Wτ+T：

(7)

3 算法仿真及比較結(jié)果

針對圖1中的4相位道路交通交叉口信號控制系統(tǒng)，本節(jié)基于混合結(jié)構(gòu)的Petri模型(交通流使用了連續(xù)時間Petri網(wǎng)，其他采用離散時間Petri網(wǎng))，分別使用固定相序模型以及圖2所示的可變相序模型進行定量的仿真及比較分析。

對于車流模型，假設(shè)變遷ti對應(yīng)的車流到達和離開時間的間隔都符合參數(shù)為θi=1/λi的指數(shù)分布，在連續(xù)模型中采用無限服務(wù)語義模型，則變遷的觸發(fā)速率為λi。假設(shè)在交叉口外，每個車流方向不允許變道區(qū)域的最大排隊長度限制為20；駛出交叉口的車流最大排隊長度限制為30(通過在模型中加入自環(huán)庫所實現(xiàn)，可參考文獻[12,16])。

文中定量地比較了交叉口內(nèi)各個車流隊列的平均排隊長度L，也就是模型中庫所pno,pwo,pso,peo的平均托肯數(shù)量。實驗中采用基于Matlab的Petri網(wǎng)仿真工具，經(jīng)過100次仿真后取平均值。L定義如下：

(8)

其中，K=100為仿真次數(shù);ψ={pno,pwo,peo,pso}。

表1 車流Petri網(wǎng)模型參數(shù)配置

采用傳統(tǒng)的固定相序信號控制策略，以及文中提出的可變相序模型和優(yōu)化算法(兩種方案采用的總信號周期相同)，分別在Matlab下進行仿真，得到的仿真結(jié)果如表2所示。

表2 仿真結(jié)果比較

從仿真結(jié)果中可以看出，使用可變相序模型以及基于MPC的相序優(yōu)化算法，交叉口的平均排隊長度優(yōu)化了12%(從17.5降到15.4)。

4 結(jié)束語

道路交叉口交通信號的優(yōu)化能夠進一步提高車輛的通行效率以及道路資源的利用率，因此一直是交通系統(tǒng)控制與優(yōu)化的熱點問題，在智能交通迅速發(fā)展的今天尤其受到重視。針對傳統(tǒng)固定相序交通信號控制機制的不足，提出了基于Petri網(wǎng)的可變相序控制模型，并結(jié)合MPC算法框架實現(xiàn)了相序與通行時間的優(yōu)化。仿真結(jié)果表明，與傳統(tǒng)固定相序算法相比，該算法能有效減少交叉口內(nèi)各方向的平均排隊長度，從而減少了擁堵。