基于Petri網的無信號交叉口車輛誘導及優化系統研究

李佳澎

摘要：為充分利用現有城市道路交通空間，在車路協同環境下對無信號交叉口控制優化方法進行了研究。根據交通流沖突點理論，交叉口分為不同的空間區域，車輛進入不同的區域需要申請該區域路權資源；利用賦時Petri網建立無信號交叉口控制模型。根據優化算法，得到較優的車輛通行序列，從而實時引導車輛通過交叉口；分析了不同數量車輛對交叉口的延誤時間、車輛平均延遲時間的影響，并將其與傳統的信號控制方法進行對比。研究結果表明：基于Petri網的無信號交叉口控制方案改善了交叉口通行狀況，控制效果優于傳統的信號控制方法。

關鍵詞：車路協同系統；無信號交叉路口；Petri網

DOIDOI：10.11907/rjdk.181026

中圖分類號：TP303

文獻標識碼：A 文章編號文章編號：1672-7800（2018）008-0021-07

英文摘要Abstract：In order to make full use of the existing space of city road，under the collaborative vehicle-infrastructure systems environment，the unsignalized intersection optimization control method is investigated.According to the conflict theory of traffic flow，the intersection is divided into different regions，and vehicles need to apply for road right resources while entering different regions.The unsignalized intersection control model is designed by using timed Petri net.Therefore，the optimal vehicle traffic sequence is obtained by the optimization algorithm，which can guide vehicles cross the intersection in real time.The influence of different quantity of vehicles on the delay time of the intersection and the average delay time of vehicles is analyzed and the method is compared with the traditional signal control method.The result indicates that the timed Petri net model method can improve the intersection traffic，and its effect is superior to that of the traditional signal control method.

英文關鍵詞Key Words：intelligent vehicle-infrastructure cooperation systems； unsignalized intersection； Petri net

0 引言

近5年我國機動車保有量每年增加1 400萬輛左右，到2017年第一季度，機動車保有量已突破3億輛。隨著機動車保有量的不斷增加，城市交通擁堵愈發嚴重，進而引發車輛延誤、交通事故等一系列問題。面對這些難題，通過擴充或新建交通設施無法完全解決。道路交叉口作為交通網的樞紐點，對車輛的疏導能力直接影響道路的通行效率。在現有交通設施環境下，針對交叉路口的管理創新成為解決城市擁堵問題的研究熱點。信號控制是我國城市交叉路口的主導模式，信號控制的優劣是影響城市道路交通系統運行效率的重要因素。全球廣泛應用的交通信號控制系統SCOOT[1]（Split Cycle Offset Optimization Technique，綠信比、周期長、相位差優化技術），是一種對交通信號網絡實時協調控制的自適應系統，可用來制定信號配時方案，但其相位不能自動增減，相序不能自動改變，導致通行車輛不必要的停車，影響交叉口通行效率。

隨著交通管理和服務需求的提高，基于協同管控和服務的交通系統建設引起各國政府和企業界的重視，產生了如美國的智能駕駛、日本的ITS安全示范和歐盟的ITS行動計劃，而我國的智能車路協同系統（Intelligent Vehicle-Infrastructure Cooperation Systems，i-VICS）正是順應未來交通系統發展的產物。智能車路協同系統基于無線通信、傳感探測等技術，通過車與車（Vehicle-to-Vehicle，V2V）、車與路（Vehicle-to-infrastructure，V2I）的信息交互和共享，實現車輛與基礎設施之間的智能協同與配合，達到優化利用系統資源、提高道路交通安全、緩解交通擁堵的目標。

智能車路協同成為現代智能交通系統的基礎性內容，智能交通原有和新增的所有功能及服務均可在車路協同環境下展開。近幾年，許多學者在車路協同環境下，對智能交通系統，尤其是無信號交叉口的車輛通行控制方法進行了創新，如Dresner等[2]提出了一種自治交叉路口管理（Autonomous Intersection Management，AIM）的多智能體方案。在該方案中，駕駛員和交叉路口均被看作是自治的智能體。在通信協議環境下，交叉路口采用一種基于預約的方法管理車輛通行；Vasirani等[3]基于AIM系統，分析了在單個無信號交叉口條件下，基于組合拍賣的預留分配方法對交叉口吞吐量的影響，和競爭激烈的情況下交通分配策略對駕駛員路線選擇的影響，提出一種基于拍賣的交通控制策略與競爭性交通分配策略相結合的自適應管理機制；Lee等[4]基于車路協同環境，提出一種無信號交叉口控制算法，該算法用于消減車輛之間的軌跡沖突，使車輛安全通過交叉口；Lee等[5＼]在單交叉路口車輛協同控制算法基礎上，提出了適用于多個交叉口的協同控制以及評價模型，衡量安全和環境的影響；Raravi等[6]提出了一種車車協同環境下的車輛自動合并控制系統，通過構造一個有約束的優化問題，確保道路交叉路口車輛安全行駛，提高了智能交通系統安全性；Ahmane等[7]在車車協同環境下，基于一種帶乘法器的賦時Petri網模型（Timed Petri Nets with Multipliers，TPNM），通過對模型的結構分析得到車輛通行順序控制策略，車輛按照車載單元提示通過交叉路口；Fadi[8]等在車路協同環境下，根據無信號交叉口中央控制站控制模式，設計了交叉口防碰撞系統。交叉口傳感器將檢測到的信息傳遞給智能路側單元，路側單元根據得到的信息判斷交叉口整體通行情況，預測車輛行駛軌跡進而判斷車輛是否會發生碰撞。

很多學者在車車協同控制模式下對車輛控制策略進行創新。本文在車路協同環境下針對無信號交叉口，采用中央控制站控制模式，提出一種新的車輛調度通行策略，將交叉口的空間區域劃分為路權資源，車輛要通過交叉路口需要占用不同的路權資源，通過構建的Petri網模型和遺傳算法進行優化，得到較優的車輛通行順序，并按照指引信息有序地通過交叉路口，在保證行車安全前提下使路口延誤時間最小。

1 無信號交叉口Petri網模型

1.1 無信號交叉路口結構

車路協同系統是各種功能、技術和信息的綜合體，包括自治車輛、智能路側系統以及協同信息交互系統。因此，本文構建的模型主要由以下3部分組成：

（1）自治車輛：具有智能車載系統的車輛。當自治車輛進入路口感應區間時能將自身狀態信息實時發送給智能路側系統，并能實時接收智能路側系統的指令信息。

（2）智能路側單元：與交叉路口區間內的自治車輛進行信息交互，獲取車輛的實時狀態信息，通過信息交互系統給車輛發送指令信息。

（3）協同信息交互系統：自治車輛和智能路側系統信息傳輸載體。

目前，智能化無交通信號的交叉路口控制模式分為中央控制站控制模式和車車協同控制模式，分別如圖1和圖2所示。

本文采用中央控制站控制模式。在車路協同環境下，當車輛進入交叉口的進口區域，依據智能車載技術中的車輛運動狀態感知技術、定位技術等，采集交叉口范圍內所有車輛的運動狀態信息，通過車路通信技術發送給智能路側設備，等待路權分配。智能路側設備根據交叉口優化控制方法將車輛的決策控制信息反饋給智能車載設備，引導自治車輛安全有效地通過交叉口，使交叉口延誤時間最小。

系統總體結構如圖3所示。

本文的研究對象是單個雙向四車道交叉路口，如圖4所示。交叉口共有16條車道（C1，C2，C3，…，C16），C3、C7、C11、C15是專用左轉車道；C4、C8、C12、C16是直行右轉車道。

根據車道數量，將交叉口的物理空間劃分為16個路權資源，如圖4中1，2，3，…，16所示。在車輛通行過程中，車輛不可避免地要使用某些路權資源，例如，從車道C4直行駛向C9的車輛要依次使用資源13-14-15-16，從車道C3左轉進入C14的車輛要依次使用資源9-10-7-3，從車道C4右轉進入C5的車輛需要使用資源13。

根據交叉口沖突點理論可知，不同方向的車輛在通過交叉路口時可能會占用相同的路權資源。例如，從車道C4直行進入C9的車輛與從C16直行進入C5的車輛都需要占用資源13。為保證車輛安全，需要限制路權資源容量，即同一時間能夠使用該路權資源的最大車輛數。通常每個路權資源的容量為1，但是從C3左轉進入C14的車輛和從C11左轉進入C6的車輛，資源7和10是可以共享的。實際情況是相向行駛車輛左轉路線一般不會相交，本文將資源6、7、10、11的容量設置為2，與此同時將資源6、7、10、11的中心點設置為4個方向左轉路線的相交區域。假設該區域為路權資源0，該資源同一時刻只能被一輛車占用。

1.2 賦時變遷Petri網基礎理論

本文采用賦時變遷Petri 網（Timed Transition Petri Net，TTPN）對交叉路口進行建模。TTPN 是由6個元素組成的有向圖：

N=（P，T，I，O，m0，d）

其中，

P={P1，P2，…，Pn}是庫所的有限集合，n>0；

T={T1，T2，…，Tm}是變遷的有限集合，m>0，P∩T=；

I：（P×T）→N是輸入函數，它定義了從P到T的有向弧的權的集合，N={0，1，…}為非負整數集；

O：（T×P）→N是輸出函數，它定義了從T到P的有向弧的權的集合；

m0：系統的初始狀態標識，即初始時令牌在各庫所的分布；

d：P→R+∪{0}為分配變遷延遲時間的函數，R+為實數集，其中變遷的延遲時間服從：①固定時間延遲；②隨機時間延遲。

為模擬系統的動態變化，Petri網中的標識根據以下的激發規則進行變化：①當且僅當p∈P，m（p）≥I（p，t），變遷t使能；②當系統處于標識m時，使能變遷t激活后，p∈P，m′（p）=m（p）+O（p，t）-I（p，t），得到新的標識m'。

1.3 無信號交叉口Petri網模型

在車路協同環境下，根據賦時Petri網特點，結合中央控制站控制模式，將無信號交叉口的模型分為兩部分：①對交叉口的通行過程建模；②對路權資源分配控制建模。

圖4中交叉路口的Petri網模型如圖5所示。圖中16個陰影區域對應該交叉路口的16個路權資源，庫所（R1，R2，…，R16）的令牌數量表示各個路權資源的容量。庫所R6、R7、R10、R11的令牌數量為2，其余資源庫所的令牌數量為1。長方形（t1，t2，t3，…，t83）表示即時變遷，長方形（T6，T7，T8，…，T84）表示延時變遷。

到達交叉口的每輛車看作一個獨立的被控對象，即一個令牌代表一輛車。從圖5可以看到，在陰影區域之外的即時變遷t1、t2、t18、t35、t46、t63、t75等模擬了車輛進入交叉口過程。若這些變遷滿足使能條件，表示有車輛要進入交叉口；同樣，t3、t4、t5、t10等即時變遷模擬了車輛離開交叉口狀況。

令牌轉移過程模擬了車輛通過交叉口的過程。當有車輛從C4直行前往C9時，車輛需要依據路側系統所提示的t63、t65、t67、t69激活時間，依次占用路權資源13、14、15、16， 最終到達C9。當路側系統發出激活t63指令時，令牌從庫所R13轉移到庫所P53。由于此時R13的令牌數量為0，根據變遷使能條件，其它車輛不可能進入該資源所對應區域。與此同時，由于P53 的令牌數為1，延時變遷T64自動激活，系統開始記錄車輛占用該資源所需要的剩余時間，直至T64的延遲時間完結，令牌從P53轉移到P54。此時，當路側系統發出激活t65指令時，令牌從R14和P54轉移到R13和P55中， 13資源得到釋放，14資源被占用。按照上述過程的演進方法，通過優化瞬時變遷激活時間，車輛即可安全高效地通過交叉路口，見表1。

2 優化控制方法

在車路協同環境下將無信號交叉口車輛通行問題轉化為資源調度問題，這類問題不僅僅是NP完全問題，同時也是最困難的組合優化問題。本文采用遺傳算法得到最優或次優的車輛通行次序，達到優化交叉口延遲時間的目的。

2.1 問題描述

前面將交叉口劃分為16個不同的路權資源，當車輛通過不同區域時，車輛需要占用該區域所對應的路權資源，每次占用同一路權資源的車輛數不能超過該資源的容量。因此，無信號交叉口的車輛通行問題可歸結為資源調度問題。

（1）16個共享資源。

（2）12條車輛通行路線J1，J2，…，J12，其中Ji=（Ji1，Ji2，…，Jik），Jik（k∈{1，2，…，5}）表示第i條路線的第k個通行階段所占用的路權資源。

（3）12條車輛通行路線的時間T1，T2，…，T12，Ti=（Ti1，Ti2，…，Tim），Tim（m∈{1，2，…，5}）表示第i條路線的第m個通行階段所消耗的時間。

無信號交叉口的通行優化問題要求在滿足路權資源約束的條件下，確定車輛通過交叉口的次序以提高交叉口的通行效率。

2.2 優化方法

有限資源調度問題具有普遍性、復雜性、動態模糊性、多約束性。很多研究人員對資源調度問題進行了深入研究[9]，提出了很多啟發式方法，如分支邊界法[10]、模擬退火算法[11-12]、禁忌搜索算法[13-14]等。其中，遺傳算法被廣泛認為是解決調度問題適當并有效的啟發式方法，使用該方法可找到有限資源調度問題的最優解或近似最優解。本文采用遺傳算法對到達交叉口的車輛進行周期性調度，以提高交叉口吞吐量，減少交叉口延遲時間。

采用遺傳算法的交叉口調度控制優化算法流程如圖6所示。其中，種群初始化模塊初始化種群構成問題的初始解集，適應度值計算模塊計算染色體的適應度值，選擇操作采用輪盤賭法選擇優秀個體，交叉操作采用整數交叉法得到優秀個體，變異操作采用整數變異法得到優秀個體。

2.3 算法實現

2.3.1 個體編碼

本文染色體編碼方式采用整數編碼，每個染色體表示該周期內所有被調度車輛的通行順序，如待通行車輛總數為n，第i輛車要通過交叉口需要依次占用的資源數為ri，則每個染色體表示長度為2∑ni=1ri的整數串。其中，染色體的前半部分表示該周期內所有車輛的通行順序，后半部分表示每輛車在通行某區域占用其對應的路權資源。如個體[3，2，4，4，3，1，4，3，2，3，3，4，4，1，2，2，2，1，1，1，8，15，2，6，7，9，21，21，11，10，14，11，12，10，21，6，5，21，3，7]編碼了4輛車的通行序列，其中前20位表示車輛的通行順序：車輛3→車輛2→車輛4→車輛4→車輛3→車輛1→車輛4→車輛3→車輛2→車輛3→車輛3→車輛4→車輛4→車輛1→車輛2→車輛2→車輛2→車輛1→車輛1→車輛1；21到40位表示車輛通過某區域所對應的路權資源：資源8→資源15→資源2→資源6→資源7→資源9→資源21→資源21→資源11→資源10→資源14→資源11→資源12→資源10→資源21→資源6→資源5→資源21→資源3→資源7。

2.3.2 適應度值

2.4 解碼

圖7演示了當交叉口的4個方向共有44輛車駛向交叉口時，中央控制站通過優化算法分配路權資源得到最優或次優車輛通行的次序。

根據圖3的系統總體結構，優化算法需要為Petri網模型變遷激活次序，表2為變遷隨時間的激活次序情況。

根據變遷激活時刻，中央控制站實時向車輛發送信息，引導車輛安全通過交叉口，優化交叉口延遲時間。

3 仿真及結果分析

為驗證本文提出的模型及優化算法的有效性，本文使用Platform Independent Petri Net Editor4.3（PIPE4.3）和MATLAB2014a進行仿真。首先，在PIPE4.3中建立交叉口的Petri網模型，生成模型的XML文件。然后，MATLAB讀取生成的XML文件，得到交叉口的Petri網模型，并采用上文給出的算法對其進行優化。仿真過程如圖8所示，其中本文的仿真時鐘推進機制采用固定步長時間推進制。

本文采用對比實驗對無交通信號交叉路口車輛調度進行仿真：①對比無交通信號交叉口在平衡交通流量情況下和不平衡交通流量情況下的車輛吞吐能力；②在相同交通流量情況下，對比交叉口在本文優化策略下和在傳統有交通信號控制策略下的車輛吞吐能力。

假設Sr是一個變量，表示車輛數量。在平衡交通流量環境下，從車道C3、C4進入交叉口的車輛數均為Sr，車道C4的轉向率為0.3，該條件適用其余方向的車道；在不平衡交通流量條件下，從車道C3、C4和C11、C12進入交叉口的車輛數均是Sr，但從C7、C8和C15、C16進入交叉口的車輛數減少為Sr/2，其它條件和平衡交通流量環境下相同。

針對信號控制策略，本文根據圖9的四相位信號控制方案，構建信號控制的Petri網模型[15]如圖10所示，其中變遷T93，T95，T97，T99是固定時間延遲變遷，代表每個相位的有效綠燈時間，本文每個相位的有效綠燈時間均為25s；T94，T96，T98，T100是隨機時間延遲變遷，代表每個相位的損失時間，包含黃燈時間、紅燈清空時間、駕駛員啟動反應時間。每個相位的損失時間服從正態分布N（5，025），交通信號周期的期望為120s。

在信號控制模式下，為更好地模擬實際情況，車輛通過每個路權資源對應區域的時間減小為中央控制站模式下所消耗時間的1/3～2/3。例如，在通過路權資源1時，在中央控制站控制模式下，車輛的通過時間為4s，而在信號控制模式下，從車道C16到C1的車輛左轉時間優化為3s，從C12到C1直行通過的時間為1s。

如圖11所示，在平衡車流和不平衡車流條件下，隨著待通行車輛數量的增加，采用遺傳算法調度方法的平均延遲時間隨著調度車輛數量的增加而增加，但是優于信號控制的平均延遲時間。

如圖12所示，采用調度算法能夠顯著改善交叉路口的吞吐量。對比遺傳算法調度和信號控制，給定數量的車輛通過交叉路口的時間能大幅減少，顯著提高交叉口吞吐量，改善道路交通狀況。

4 結語

本文采用中央控制站控制模式，首次提出基于資源調度思想，將交叉路口的空間區域劃分為路權資源，通過優化算法得到車輛最優或次優的通行序列，然后通過Petri網模型的仿真模擬，實時引導車輛按次序通過交叉口。經實驗驗證，本文提出的方法使交叉口延遲時間有了較大幅度降低，車輛平均延遲時間有一定改善。本文提出的方法為無信號交叉口車輛通行控制模式創新提供了一種新的思路。通過構建的Petri網模型，為今后引入離散事件系統故障診斷方法，解決車輛通過無信號交叉口時出現故障等意外情況提供了理論基礎。

參考文獻：

[1] HUNT P B，ROBERTSON D L，BRETHERTON R D.The SCOOT on-line traffic signal optimization technique[J].Traffic Engineering and Control，1982，23（4）：190-192.

[2] DRESNER K，STONE P.Amultiagent approach to autonomous intersection management[J].Journal of Artificial Intelligence Research，2008，31（1）：591-656

[3] VASIRANI M，OSSOWSKI S.A market-inspired approach for intersection management in urban road traffic networks[J].Journal of Artificial Intelligence Research，2012，43（1）：621-659.

[4] LEE J，PARK B.Development and evaluation of a cooperative vehicle intersection control algorithm under the connected vehicles environment[J].IEEE Transaction on Intelligent Transportation Systems，2012，13（1）：81-90.

[5] LEE J，PARK B，MALAKORN K，et al.Sustainability assessments of cooperative vehicle intersection control at an urban corridor[J].Transportation Research Part C，2013（32）：193-206.

[6] RARAVI G，SHINGDE V，RAMAMRITHAM K，et al.Merge algorithms for intelligent vehicles[C].Next Generation Design and Verification Methodologies for Distributed Embedded Control Systems.2007：51-65.

[7] AHMANE M，ABBAS-TURKI A，PERRONNET F，et al.Modeling and controlling an isolated urban intersection based on cooperative vehicles[J].Transportation Research Part C，2013（28）：44-62.

[8] BASMA F，TACHWAII Y，HREFAI H.Intersection collision avoidance system using infrastructure communication[C].14th International IEEE Conference on Intelligent Transportation Systems，2011：422-427.

[9] SRISKANDARAJAH C，SETHI S P.Scheduling algorithms for flexible flowshop：worst and average case performance[J].European Journal of Operational Research.1989，43（2）：143-160.

[10] SHANKER K，MODI，B K.A branch and bound based heuristic for multiproduct resource constrained scheduling problem in FMS environment[J].European Journal of Operational Research.1999，113（1）：80-91.

[11] BALAJI A，PORSELVI S.Artificial immune system algorithm and simulated annealing algorithm for scheduling batches of parts based on job availability model in a multi-cell flexible manufacturing system[J].Procedia Engineering，2014（97）：1524-1533.

[12] ELMI A，SOLIMANPUR M，TOPALOGLU S，et al.A simulated annealing algorithm for the job shop cell scheduling problem with Intercellular moves and reentrant parts[J].Computers and Industrial Engineering，2011，61（1）：171-178.

[13] SHAHVARI O，SALMASI N，LOGENDRAN R，et al.An efficient tabu search algorithm for flexible flow shop sequence-dependent group scheduling problems[J].International Journal of Production Research，2012，50（15）：4237-4254.

[14] SOLIMANPRR M，ELMI A.Atabu search approach for cell scheduling problem with makespan criterion[J].International Journal of Production Economics，2013（141）：639-645.

[15] FEBBRARO D A，GIGLIO D，SACCO N.A deterministic and stochastic petri net model for traffic-responsive signaling control in urban areas[J].IEEE Transaction Intelligent Transportation Systems，2016，17（2）：510-524.

（責任編輯：杜能鋼）