基于Petri网的顾及转向延误的最优路径算法

杨 琰，廖伟志，李文敬，杨 文，李 杰

（广西师范学院 计算机与信息工程学院，广西 南宁530023）

0 引 言

城市道路交叉口转向引起的时间延误不能忽略。有调查表明，城市交通网络中车辆在交叉口的延误可以达到全部行驶时间的17%－35%。考虑转向延误的最短路径算法［1］具有重要的现实意义。针对这一问题国内外有些代表性的研究成果：唐小勇［2］和杜牧青［3］从数据存储结构和算法两方面着手求解最优路径；高明霞［4］为网络中的各个弧设置了一个距离标号和紧前弧标号，通过不断迭代、更新弧的标号来寻找最短路径；郑年波［5］把交通路网表达为动态对偶网络，推导了满足先进先出特性的动态行程计算方法，设计了时间依赖的标号设定最短路径算法。

现有的这些研究均针对有向网络，然而现实交通网络是无向的。当网络规模增大时，无向图向有向图的转化以及转换后网络结构的规模会导致问题求解的复杂度急剧增加。再者，目前常用的扩展网络法和对偶网络法均需对初始网络进行变换，处理过程复杂且其处理结果将原本直观的网络结构变的不再一目了然。基于Petri网的最短路算法［6］是通过求解网图中 “托肯”从指定起点到达终点的最短运行时间来寻求最短路径，较传统直接计算路长而言，更为直观和方便。据此，本文针对双向通行的交通网络，提出基于无向Petri网［7］的顾及转向延误的最优路径智能搜索算法。

1 基于无向Petri网的交通网络模型

1.1 Petri网概述

Petri网 （PN）［8］是一种进行系统分析和模拟的图形化建模工具，它既能刻画系统的结构，又能模拟系统的运行，适合描述离散事件的动态过程。Petri网由基网 （net）和标识组成，网的部分描述系统的结构，标识部分表示系统的状态。一个Petri网是一个四元组Σ＝ （S，T；F，M），其中：

（1）S＝ ｛s1，s2，…，sm｝是非空有限库所集；

（2）T＝ ｛t1，t2，…，tn｝是非空有限变迁集，且S和T不相交；

（3）F （S×T）∪ （T×S）是流关系，且dom （F）∪cod（F）＝S∪T；（S，T；F）构成一个有向图；

（4）W：F→N 是权函数。W （s，t）＝i（i＞0）当且仅当存在一条从库所s到变迁t的权值为i的弧；W （s，t）＝0当且仅当不存在从库所s到变迁t的弧。用t＝ ｛s｜ （s，t）∈F｝表示变迁t的输入库所的集合，s＝ ｛t｜ （s，t）∈F｝表示库所s的输出变迁的集合。

（5）标识M用一个m维 （m为网中库所的个数）的非负整数向量表示。

对于变迁t∈T，如果s∈S：s∈t→m （s）≥1，则称变迁t在标识M 有发生权 （enabled），记为M ［t＞。

1.2 扩充的Petri网 （Extended Petri Net）

由于顾及到道路交叉口的转向延误，用基本Petri网难以描述和计算，因此有必要对托肯 （token）和变迁 （transition）的使能规则进行扩展。

1.2.1 托肯的附加描述

Petri网图中的托肯只有一种状态，用库所中的小实心圆点 “·”表示。在交通运输网络中，通常表示 “车辆或者人处于此位置”。现赋予托肯另外两种状态：一种表示“托肯处于转向耗时中”，用内部加一小黑点的小圆 “⊙”表示；另外一种表示 “托肯处于路途耗时中”，用大的实心圆点 “●”表示。库所中托肯的状态变化如图1所示。

图1 托肯的状态变化

说明：状态①：表示车辆或者人处于此位置；状态②：表示托肯在进行 “转向耗时”，或 “转向耗时”刚完成；状态③：表示托肯在进行 “路途耗时”，或 “路途耗时”刚完成；状态③→状态①：表示托肯 “路途耗时完成”，进入输出库所。

1.2.2 变迁的使能规则

规则1：若状态①的托肯位于库所p中，则所有以p为输入库所的变迁t的实施都是可能的。

规则2：从第0时刻开始计时，当托肯第一次到达库所q时，将q（t）（t为托肯进入q的时刻）存入集合A。此托肯途经的库所序列就是从起点出发到q的最优路径序列，其时间消耗为t。此后所有以A中任一元素为输出库所的变迁均不能使能。

作用有二：因网络无向，可以防止查找方向逆回去；若q属于A，则表明从起点S到q的最优路径已经产生，其余尚未到达q而准备朝q方向的查找将没有意义 （满足整体最优，则局部也最优）。

规则3：若托肯在向库所q移动的 “耗时 （转向耗时或路途耗时）”过程中，有其余托肯率先进入了q，则该托肯所代表路径上相应变迁的使能终止，托肯移出网络；当两个或两个以上来自不同库所中的托肯准备在同一时刻移入到同一输出库所时，只保留其中一个，其余的移出网络。

假设有3个来自不同库所的托肯要同时进入输出库所q，这表明从起点S到达节点q的最优路径有3条。

1.3 限制搜索区域的思想

经典Dijkstra算法按节点距起始点距离递增的顺序产生最短路径，搜索的区域理论上是一个以起点S为圆心，M （人们所能接受的从S到终点D的极限距离）为半径的圆。这种方法忽略实际交通网络本身特有的空间分布特性，盲目的搜索导致大量与结果无关的节点引入计算，严重影响算法的效率。实际城市路网结构比较规则，特别是经过规划的现代化都市。在城市路网路径规划研究中，合理的限制搜索区域［9］理论上可以提高路径搜索的效率。

根据几何知识：到两定点的距离之和不超过某一确定值 （大于两定点间的欧氏距离）的点的集合，构成了以这两个定点为焦点、确定值为长轴长的椭圆。椭圆外的节点与结果无关，因此智能算法将搜索范围锁定在此椭圆区域内。设网络中一点N到S和D的欧氏距离分别为｜SN｜、｜DN｜，则限制椭圆搜索区域的数学表示为：｜SN｜＋｜DN｜≤M 。

图2所示为经典Dijkstra算法和限制椭圆的搜索区域对比图。很明显，限制区域后算法所需扫过的范围要小很多，并且这种差别会随着交通网络规模及起终点间距离的增大而变得更加明显。

图2 圆和限制椭圆搜索区域对比

1.4 无向交通运输网络的Petri网表示

Petri网图是由 （S，T；F）决定的有向二元图。图中库所节点s用圆表示，变迁t用带箭头的短线表示。将交通运输网络中相异路径上相交的站点抽象为Petri网结构中的库所s，不同站点间相连通的路径抽象为变迁t。变迁的激发表示车辆离开当前站点，沿着变迁所代表的路径向与其连接的另一站点前进。变迁上的权值表示相邻站点间的距离、路途消耗时间等。将交通网络中所有站点和路径信息都体现在Petri网结构中就形成了交通运输网络的Petri网模型［10］。

本文针对双向通行的交通网络，故模型中连接库所和变迁的弧是无向的。现实中的交通网络是实时动态的，若某时段某路段限行，则只需随时对数据库中相应的弧段权值进行更新或增加限制即可。

图3是由23个站点及36条双向通行路径构成的交通网络的Petri网表示。站点抽象为库所集P＝ ｛a，b，c，…，v，w｝，路径抽象为变迁集T＝ ｛tab，tba，tad，tda，…，tgw，twg｝。变迁上的权值表示车辆通过相邻站点所需的时间（单位：min）。假设起点为a，目标点为i，车辆在道路交叉口右转、直行和左转的平均延误时间分别为0、2和3。设M值为50，用｜SN｜ ＋ ｜DN｜≤M计算得到的限制椭圆搜索区域如图3中阴影部分所示。

图3 交通网络的Petri网表示

2 智能算法

2.1 算法原理

首先通过合理限定椭圆区域把对网络节点的搜索范围缩小，然后根据1.2小节中变迁的使能规则1和2，在所有可能实施的变迁中选择符合条件的那些变迁激发。同一时刻不同托肯的状态代表着各自所探索路径的耗时 （转向或者路途耗时）状况。搜索过程中根据规则3，及时地终止一些无意义的查找。程序按照使能规则有序发生，直到目标库所中拥有托肯。算法通过计算机仿真托肯在网图中从起点到达目标点的最短运行时间来寻求最优路径，到达目标点的托肯所途经的库所序列即为最优解。以图3为例，求解从a到i的最优路径问题就转换成了求解起始库所a中的托肯经过一系列变迁到达目标库所i的最短时间消耗问题。

2.2 数据的准备工作

数据的准备工作包括5方面内容：网络中各节点的坐标信息，各节点的可行方向集，转向耗时信息，路途耗时信息，道路实时信息 （如某时段某路段限行）。实际操作时将节点的可行方向集和道路实时信息相结合起来考虑。

定义节点s的可行方向集s’为从节点库所s出发可以到达的库所的集合。因本文针对双向通行交通网络，所以s’可理解为与s相连通的所有节点的集合。规定托肯在起始库所的 “转向耗时”时长为0，即不进行转向耗时，根据可执行的变迁直接进入路途耗时。后面简称 “路途耗时”为 “路耗”、“转向耗时”为 “转耗”。

2.3 算法步骤

输入：起始节点S，目标节点D，极限距离M

输出：S到D的最优路径序列

步骤1 根据1.3小节限定椭圆区域的思想，计算｜SN｜＋ ｜DN｜≤M ，得到落在椭圆区域内的库所集合R。

步骤2 ①状态的托肯进入起始库所S，S存入集合A。

步骤3 在有①状态托肯的库所处，根据1.3小节中规则1和规则2确定可能实施的变迁集T。若-t∈T，且tR，则t不使能，T中其余变迁均使能。

步骤4 托肯根据使能的变迁数目进行衍生，新生成托肯的数目等于使能的变迁数目。查看数据库信息，各新托肯代表各自不同的路径进行相应的 “转耗”和 “路耗”。

步骤5 托肯 “路耗”结束，并且此刻其相应的输出库所oA，则托肯进入输出库所o。

步骤6 判断o是否为目标节点D，若是，表示最优路径搜索成功，输出到达D的托肯所途经的库所序列，程序运行结束；若非，则先判断o是否为其余托肯的待输出库所，若是，则其耗时终止并移出网络，返回步骤3。

如图4所示为智能算法中托肯的状态变化流程图。

2.4 算例

以图3所示的交通网络为例，经过27个单位时间可以求得从a到i的最优路径。篇幅所限，本文只详述搜索过程中的以下6个代表时刻，具体如下：

（1）第0时刻，初始托肯进入a，a存入集合A。a’＝｛b，d，s，u｝，根据规则，这些变迁均使能。查看数据库确定各路耗时长，托肯准备进行各路耗。A＝ ｛a （0）｝。

（2）第6时刻，路径ab（后面简称ab）的托肯在 “a→b的路耗中”；ad的托肯 “a→d的路耗完成”，d存入A，d’＝ ｛a，e，g，v｝R，因a∈A，所以实施变迁d→e、d→g、d→v；au的托肯在 “a→u的路耗中”；as的 “路耗”在时刻5完成，s’＝ ｛a，r，t｝，因 ｛r，t｝R，a∈A，所以as方向的搜索自动终止。A＝ ｛a （0），s（5），d （6）｝，如图5 （a）所示。

图4 算法托肯状态变化的流程

（3）第11时刻，ab在8时刻已路耗完成。b’＝ ｛a，c，e，r｝，因rR，a∈A，于是只执行b→c、b→e。abc的托肯 “路耗中”，abe的托肯 “转耗完成，准备路耗”；ade的托肯 “路耗完成”，e存入A，此时abe搜索终止。e’＝｛b，d，f，h｝，｛b，d｝A，执行e→f和e→h；adg及adv的托肯 “路耗中”；u在9时刻进入A，auv的托肯 “路耗中”。A＝ ｛a （0），s （5），d （6），b （8），u （9），e （11）｝，如图5 （b）所示。

（4）第14时刻，adeh的托肯 “转耗完成，开始路耗”；adef、adg、adv、auv及abc的托肯均 “路耗中”。此时A＝ ｛a （0），s （5），d （6），b （8），u （9），e （11）｝，如图5（c）所示。

（5）第20时刻，adg的g和adv的v均在时刻15拥有了托肯。考虑路径adg，g’＝ ｛d，h，j，w｝，jR，wR，d∈A，只执行g→h；v’＝ ｛d，u，w｝，wR，｛d，u｝A，adv方向的搜索终止；adeh的托肯 “路耗完成”，此时adgh方向的搜索终止，h’＝ ｛e，g，i，k｝，｛e，g｝A，实施h→i，h→k；adef的托肯在 “路耗中”；路径abc，c’＝ ｛b，f，p，q｝，pR，qR，b∈A，只实施c→f。此时A＝ ｛a （0），s （5），d （6），b （8），u（9），e （11），g （15），v （15），c （16），h （20）｝，如图5（d）所示。

图5 智能算法的搜索过程

（6）第27时刻，adehi的托肯率先进入目标库所i，路径搜索成功，输出序列adehi，程序运行结束，如图5（e）所示。

关于图5中不同箭头的说明：

本算例的结果与用改进的Dijkstra算法求得的结果一致。从以上搜索过程我们可以发现，在搜索范围本就已经缩小很多 （限定区域）的情况下，1.2小节中托肯运行规则的定义也及时避免了很多无意义的查找，使得双向通行网络上复杂的路径选择问题变的简单很多，极大的降低了搜索的复杂度，提高了搜索的效率。经多次反复试验证明本智能算法是准确可用的。

3 实验与分析

本文随机选取北京市内4对起终点，采用P41.4GHz CPU、1GB内存的计算机进行仿真。随着起终点间直线距离的增大，涉及路段和节点数目增多，网络规模也越来越大，具体数据见表1。

表1 用于实验的4对起终点

对4个随机起终点对分别用改进的Dijkstra算法，A＊算法以及本文智能算法进行路径规划，实验结果见表2和图6。

表2 3种算法路径规划结果

图6 3种算法搜索节点数的比较

从试验结果可以看出，前3个点对的起终点间直线距离相对较小 （小于40km），利用智能算法找到了最优路径，而且搜索节点数目都明显小于对比算法。随着网络规模的增大，智能算法搜索节点数变化上升的趋势要小于对比算法。这得益于算法搜索范围的合理限定以及路径选择变迁规则的定义。进一步观察可发现，对于点对4（直线距离大于40km），智能算法求得的结果50.1稍大于对比算法的48.8，意即得到的路径结果并非最优。这是由于在第一步设定M值时，只考虑了欧氏距离，而没有将转向延误信息考虑进去，致使一些可用节点一开始就被排除到了搜索区域之外。对于欧氏距离较大的点对集来说，Dijkstra和A＊算法虽然结果更优，没有精度损失，但是搜索范围向四周急剧扩散，运行效率很低，而本智能算法的搜索具有一定方向性。如果为了追求结果最优而过分的增大M值会导致搜索规模的增大，从而直接影响到算法运行的效率，因此本算法实际上是一种用牺牲精度来换取效率的方法。

4 结束语

与传统顾及转向延误的最优路径算法相比，本文提出的基于Petri网的智能算法更简便、易于实现，且运行效率较高。它面向的是最复杂的实时双向通行网络，并且无需对原始网络结构做任何调整。在根据用户需求对搜索区域进行合理的限定后，使能规则的拓展定义更有效的降低了双向通行路网上路径选择的复杂度，更大程度的缩小了搜索范围，提高了查找效率。故该算法可以为日益复杂的智能交通系统的动态交通诱导提供思路。但该算法有一个缺点是M值人为设定，这使得一些情况下的搜索结果带有随意性和强制性。如何更加合理的设定M值或者采用更好办法来对搜索方向进行限定，并将其完美融合在算法中将是我们下一步要研究和探讨的问题。

［1］Gutierrez E，Medaglia A L.Labeling algorithm for the shortest path problem with turn prohibitions with application to largescale road networks［J］.Annals of Operations Research，2008，157 （1）：169－182.

［2］TANG Xiaoyong，CHENG Lin，XU Shang.A least time algorithm considering delays fo intersection movements and its implementation［C］／／3rd China Annual Conference on ITS Proceedings，2007 （in Chinese）.［唐小勇，程琳，徐上.考虑转向延误最短路径算法及实现 ［C］／／第三届中国智能交通年会论文集，2007.］

［3］DU Muqing，CHENG Lin.Auction algorithm for shortest paths in road networks considering delays for intersection movements［J］.Journal of Southwest Jiaotong University，2010，45 （2）：249－254 （in Chinese）.［杜牧青，程琳.考虑交叉口转向延误的最短路径拍卖算法 ［J］.西南交通大学学报，2010，45（2）：249－254.］

［4］GAO Mingxia，HE Guoguang.An arclabeling algorithm for shortest path problem considering turn penalties and prohibitions at intersections ［J］.Journal of Lanzhou Jiaotong University，2011，30 （6）：111－114 （in Chinese）.［高明霞，贺国光.考虑交叉口延误和转向限制的弧标号最短路径算法 ［J］.兰州交通大学学报，2011，30 （6）：111－114.］

［5］ZHENG Nianbo，LU Feng，DUAN Yingying.Dynamic dual graph model for turn delays on road networks ［J］.Journal of Image and Graphics，2010，15 （6）：915－920 （in Chinese）.［郑年波，陆锋，段滢滢.道路转向延迟的动态对偶图模型［J］.中国图象图形学报，2010，15 （6）：915－920.］

［6］HUANG Shengguo，SUN Tongjiang，LV Bing.Petri net simulation arithmetic of the shortest directional path in transportation net ［J］.Journal of Nanjing University of Aeronautics ＆Astronautics，2002，34 （2）：121－125 （in Chinese）.［黄圣国，孙同江，吕兵.运输网络的最短有向路Petri网仿真算法 ［J］.南京航空航天大学学报，2002，34 （2）：121－125.］

［7］REN Xiaolong，WEN Haoyu，LI Hua.Routing algorithm for multiple AGVs with the undirected Petri Net ［J］.Journal of Xidian University，2008，35 （3）：517－522 （in Chinese）.［任小龙，温浩宇，李华.无向Petri网的多AGV最优路径方法研究 ［J］.西安电子科技大学学报，2008，35 （3）：517－522.］

［8］WU Zhehui.Petri net introduction ［M］.Beijing：Machine Press，2006 （in Chinese）.［吴哲辉.Petri网导论 ［M］.北京：机械工业出版社，2006.］

［9］WANG Haimei，ZHOU Xianzhong.Improved shortest path algorithm for restricted searching area ［J］.Journal of Nanjing University of Science and Technology（Natural Science），2009，33 （5）：638－641 （in Chinese）.［王海梅，周献中.一种限制搜索区域的最短路径改进算法 ［J］.南京理工大学学报，2009，33 （5）：638－641.］

［10］LI Shuju.The modeling of variable transportation network and the shortest path algorithm based on petri net ［D］.Guangxi：Guangxi Teachers Education University，2012 （in Chinese）.［李书举.基于Petri网的变数交通网络建模及其最短路径算法研究 ［D］.广西：广西师范学院，2012.］