基于MPC的可變相序交通信號(hào)優(yōu)化控制方法

楊利紅，王列偉

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

0 引 言

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

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

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

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

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

定義：一個(gè)Petri網(wǎng)系統(tǒng)是一個(gè)二元組，其中N=是一個(gè)網(wǎng)狀結(jié)構(gòu)。(1)P和T是不相交的，分別表示庫(kù)所和變遷的有限集合；(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|分別表示庫(kù)所和變遷，在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)識(shí)狀態(tài)(又稱為marking)由分布在各個(gè)庫(kù)所中的托肯(token)表示。系統(tǒng)的全局標(biāo)識(shí)狀態(tài)向量用M表示，非負(fù)整數(shù)M[pi]表示庫(kù)所pi中包含的托肯個(gè)數(shù)，也稱為庫(kù)所的標(biāo)識(shí)。在系統(tǒng)狀態(tài)M下，一個(gè)變遷被稱為使能(enabled)，當(dāng)且僅當(dāng)該變遷的輸入庫(kù)所中都包含有足夠多的托肯，并使得式1成立。

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

(1)

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

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

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

(2)

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

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

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

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

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

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

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

(3)

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

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

(4)

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

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

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

圖2 交叉口4相位可變相序交通信號(hào)控制模型

變遷t1、t2、t3、t4為瞬時(shí)變遷(immediate transition)，也就是假設(shè)其變遷觸發(fā)時(shí)間為零。當(dāng)瞬時(shí)變遷被使能時(shí)，立即完成觸發(fā)并更新系統(tǒng)狀態(tài)。變遷ta、tb、tc、td為固定時(shí)延變遷(determined delay transition)，每個(gè)變遷具有一個(gè)延遲時(shí)間，分別表示為δa、δb、δc、δd。當(dāng)一個(gè)固定時(shí)延變遷在時(shí)間點(diǎn)τ被使能，則經(jīng)過(guò)其對(duì)應(yīng)的時(shí)延δi，在時(shí)間點(diǎn)τ+δ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)模型中形成了一個(gè)典型的沖突關(guān)系；在對(duì)應(yīng)的交通信號(hào)模型中，這意味著所有的相位都有機(jī)會(huì)在下一時(shí)刻獲得綠燈通行權(quán)。因此，Petri網(wǎng)模型中的沖突解決策略決定了信號(hào)系統(tǒng)的相序選擇。例如，假設(shè)此時(shí)的沖突解決策略是變遷t1、t2、t3、t4的優(yōu)先級(jí)依次降低。在初始狀態(tài)，變遷t1將優(yōu)先獲得觸發(fā)，庫(kù)所p0和pe1中的托肯被轉(zhuǎn)移到p1中，因此相位1對(duì)應(yīng)的車(chē)流獲得綠燈通行權(quán)，此時(shí)ta被使能；經(jīng)過(guò)時(shí)延δa(相位1的綠燈通行時(shí)間)后，變遷ta觸發(fā)，庫(kù)所p1中的托肯重新轉(zhuǎn)移到p0中，同時(shí)庫(kù)所ps也獲得一個(gè)托肯；注意，此時(shí)庫(kù)所pe1中的托肯被清空，因此變遷t1不再使能，即在該周期內(nèi)相位1不再獲得通行權(quán)；根據(jù)優(yōu)先級(jí)，下一時(shí)刻變遷t2觸發(fā)(相位2的車(chē)流獲得通行權(quán))；當(dāng)變遷t1、t2、t3、t4全部獲得觸發(fā)后，庫(kù)所pe1,pe2,pe3,pe4中的托肯全部被清空，而ps獲得4個(gè)托肯，因此變遷ts被使能，ts觸發(fā)后系統(tǒng)信號(hào)控制系統(tǒng)回到初始狀態(tài)，意味著一個(gè)新的信號(hào)周期開(kāi)始。

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

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

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

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

(5)

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

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

(6)

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

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

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

(7)

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

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

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

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

(8)

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

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

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

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

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

4 結(jié)束語(yǔ)

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