基于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.

（责任编辑：杜能钢）