基于Petri网的交通控制系统建模与评估

第３４卷　Ｖｏ１．３４　・增　刊　计算机工程　２００８年９月　Ｓｅｐｔｅｍｂｅｒ　２００８　Ｓｕｐｐｌｅｍｅｎｔａｒｙ　Ｉｓｓｕｅ　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　软件开发与测评・　文章编号：１ｏ０ｏ—３¨４２８（２０惦）增刊—０ｏｏ８．＿＿ｏ３　文献标识码：Ａ　中蟹分类号；Ｎ９４５　基于Ｐｅｔｒｉ网的交通控制系统建模与评估　刘晓娟　，沮箍华　（１．华东计算技术研究所，上海２００２３３；２．欧特克软件有限公司，上海２００１２２）　摘要：基于Ｐｅｔｒｉ网理论，提出一种对十字路１３交通控制系统建模和性能评估的方法。该方法根据路１３间的交通流量，计算在不同红绿　灯相位差的情况下，各个路１３的平均等待队列长度和平均等待时间，从而得出最优的红绿灯相位差。与通常的Ｐｅｔｒｉ网模型相比，该模型　减少了分析的复杂性，提高了城市路网的通行能力。　关键词：Ｐｅｔｒｉ网；交通控制系统；建模；性能评估　Ｍｏｄｅｌｉｎｇ　ａｎｄ　Ａｎａｌｙｓｉｓ　０ｆ　Ｔｒａｆｉｃ　Ｃｏｎｔｒｏｌｆ　Ｓｙｓｔｅｍ　Ｂａｓｅｄ　０ｎ　Ｐｅｔｒｉ　Ｎｅｔ　ＬＩＵ　Ｘｉａｏ－ｊｕａｎ　．ＷＥＮ　Ｇｕａｎ・ｈｕａ　（１．Ｅａｓｔ　Ｃｈｉｎａ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｔｅｃｈｎｏｌｏｇｙ，Ｓｈａｎｇｈａｉ　２００２３３；２．Ａｕｔｄｅｓｏｋ　Ｉｎｃ．，Ｓｈａｎｇｈａｉ　２００１２２）　｜Ａｂｓｔｒａｃｔ｜Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｐｏｓｅｓ　ａ　ｍｅ￣ｏｄ　ｏｆ　ｍｏｄｅｌｉｎｇ　ａｎｄ　ｐｅｒｆｏｒｍａｎｃｅ　ａｎａｌｙｓｉｓ　ｏｆ　ｔｒａｆｆｉｃ　ｃｏｎｔｒｏｌ　ｓｙｓｔｅｍ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｔｈｅｏｒｙ　ｏｆ　Ｐｅｍ　ｎｅｔ．Ｔｈｉｓ　ｍｅｔｈｏｄ　ｆｉｇｕｒｅｓ　ｏｕｔ　ｔｈｅ　ａｖｅｒａｇｅ　ｌｅｎｇｔｈ　ｏｆ　ｗａｉｔｉｎｇ　ｑｕｅｕｅ　ａｎｄ　ｔｈｅ　ａｖｅｒａｇｅ　ｌａｔｅｎｃｙ　ｔｉｍｅ　ｏｆ　ｅａｃｈ　ｉｎｔｅｒｓｅｃｔｉｏｎ　ｔｏ　ｐｉｃｋ　ＯＵｔ　ｔｈｅ　ｍｏｓｔ　ｓｕｐｅｒｉｏｒ　ｏｆｆｓｅｔ　ａｃｃｏｒｄｉｎｇ　ｔｏ　ｔｈｅ　ｔｒａｆｆｉｃ　ｆｌｏｗ　ａｎｄ　ｄｉｆｆｅｒｅｎｔ　ｏｆｆｓｅｔｓ　ｏｆ　ｔｈｅ　ｔｒａｆｆｉｃ　ｌｉｇｈｔｓ　ａｔ　ｉｎｔｅｒｓｅｃｔｉｏｎｓ．Ｔｈｉｓ　ｍｏｄｅｌ　ｇｒｅａｔｌｙ　ｒｅｄｕｃｅｓ　ｔｈｅ　ｃｏｍｐｌｅｘｉｔｙ　ｏｆ　ａｎａｌｙｓｉｓ，ａｎｄ　ｉｍｐｒｏｖｅｓ　ｔｈｅ　ｔｒａｎｓｐｏｒｔａｔｉｏｎ　ｃａｐａｂｉｌｉｔｙ　ｏｆ　ｕｒｂａｎ　ｔｒａｆｉｃ　ｆｎｅｔｗｏｒｋｓ　ｃｏｍｐａｒｅｄ　ｗｉｈ　ａｃｃｕｓｔｏｍｅｄ　ｔＰｅｔｒｉ　ｎｅｔ　ｍｏｄｅ１．　［Ｋｅｙ　ｗｏｒｄｓＩ　Ｐｅｔｒｉ　ｎｅｔ；ｔｒａｆｉｃ　ｃｏｎｔｆｒｏｌ　ｓｙｓｔｅｍ；ｍｏｄｅｌｉｎｇ；ｐｅｒｆｏｒｍａｎｃｅ　ｎａｌａｙｓｉｓ　１概述　目前，解决交通问题的直接办法是提高路网的通行能力，　但无论在哪个国家的大城市，可供修建的空间是有限的，而　卜Ｐ为输出函数，它是从变迁到库的一个映射。集合Ｐ的基　数为ｎ，集合丁的基数为ｍ。Ｐ的元素记为Ｐ　，ｉ＝１，２，…，ｎ；Ｔ　的一个元素记为ｔｊ，ｊ＝ｌ，２，…，ｍ…。　且资金问题也是一个需要考虑的问题。因此，从系统的观点　出发，把车辆、道路和人等众多因素统筹考虑，运用各种高　新技术和人工智能技术建立具有控制力的、现代化的交通控　当Ｐ　∈，（　ｆ）时，库Ｐｆ称为　ｆ的一个输入库。当Ｐ　∈Ｄ（　ｆ）时，　库Ｐ　称为ｆ，的一个输出库。一个变迁的输入或者输出是一个　库袋，袋是广义的集合，在袋中允许一个元素反复出现。如　制系统来解决日益严重的交通问题已迫在眉睫。本文将Ｐｅｔｒｉ　网的理论知识用于交通控制系统中。Ｐｅｔｒｉ网已经被证明是一　果库Ｐ　是变迁　ｆ的输出库，则　是Ｐｆ的输入变迁，如果库Ｐ　是变迁ｔｊ的输入库，则　是Ｐ　的输出变迁。　个有效的用于离散事件系统的建模工具，Ｐｅｔｒｉ网利用网络图　形描述对象之间的输入／输出关系，能够很好地反映系统的静　态和动态特性。在交通控制系统中，Ｐｅｔｒｉ网模型能够方便地　２．２　Ｐｅｔｒｉ阿的图　Ｐｅｔｒｉ网的图是表示Ｐｅｔｒｉ网结构的双枝有向多重图。Ｐｅｔｒｉ　网结构中包含有库和变迁。与此对应，Ｐｅｔｒｉ网图中有两类节　点。用小圆圈表示库，用短线表示一个变迁，用小圆点表示　ｔｏｋｅｎ，用有向弧（带箭头的曲线）连接库和变迁，一些弧从库　指向变迁，另一些弧从变迁指向库。一条从库　指向变迁０　的弧，表示Ｐ　是ｆ　的一个输入位置。一个Ｐｅｔｒｉ网的图是一个　多重图，因为它允许从一个节点到另外一个节点之间有多重　图。此外，因为图是有向的，所以它是多重有向图，又因为　表示交通和交通控制中活动的协同、竞争和同步，并改变网　络的结构、交通的控制逻辑、时机和协调性，以及假定的输　入流。Ｐｅｔｒｉ网模型可以被数学定义，这样就能考虑到控制逻　辑所有需要考虑到的死锁情况，通过逻辑和时间上的安排使　交通堵塞情况避免发生。　２　Ｐｅｔｒｉ网基本概念　２．１　Ｐｅｔｒｉ两的基本结构　个Ｐｅｔｒｉ网由４个部分组成：库（ｐｌａｃｅ）集合Ｐ，变迁　一它的节点可以分为两个互不相交的集合（库的集合和变迁的　集合），使得每条弧都是从其中一个集合的元素指向另外一个　集合的元素，因此它是双枝有向多重图。　图１是一个包含４个库、２个变迁的简单Ｐｅｔｒｉ网，图ｌ（ａ）　是Ｐｅｔｒｉ网的初始状态，图ｌ（ｂ）是ｔＩ触发后的Ｐｅｔｒｉ网状态，　图１（ｃ）是，２触发后的Ｐｅｔｒｉ网状态。　（ｔｒａｎｓｉｔｉｏｎ）集合７１，输入函数，，输出函数Ｏ。输入函数和输　出函数是位置和变迁之间的映射函数。输入函数，是一个变　迁到一个库问的映射，输出函数Ｏ把一个变迁映射到一组库。　Ｐｅｔｒｉ网的结构由它的位置、变迁、输入函数和输出函数确定。　一个Ｐｅｔｒｉ网的结构Ｃ是一个四元组Ｃ＝｛Ｐ，　，，Ｄ｝。　作者倚介：刘晓娟（１９８３一），女，硕士研究生，主研方向：软件工程；　温冠华，硕士研究生　Ｐ＝｛Ｐｌ，Ｐ２，…，Ｐ　｝（ｎ≥０）是库的有限集合；　｛ｔｌ，ｒ２，…，ｔｍ｝（　≥０）　是变迁的有限集合。库的集合和变迁的集合不相交，即Ｐｎ　丁＝妒。，：丁一Ｊｐ为输入函数，它是从变迁到库的一个映射。Ｏ：　收稿日期：２００８—０８—２８　Ｅ－ｍａｉｌ：ｗｅｎｙａｏｏｏ＠ｈｏｔｍａｉｌ．ｃｏｍ　８一　４系统建模　４．１十字路Ｉ：ｌ的时阔Ｐｅｔｒｉ两模型甩于闭合路罔的控翻　城市中，道路四通八达，每辆车都有可能在任何一个十　字路口拐弯，因此，要提高城市交通整体的性能，就要从路　网的角度来衡量整体的性能。闭合路网如图３所示。对于路　网来说，可以一个路Ｉ：ｌ接一个路口来进行分析，先分析路口　（ａ）初始ＰＮ状态　（１，１）的情况，接着分析路１３（１，２）和（２，１）的情况，再接下来　分析路Ｉ：１（１，３），（２，２），（３，１）的情况，依次往下分析，直到最　后一个路Ｉ：ｌ为止。对每一个路口建模需要考虑两个方向上的　情况　。　４．２　四相位十字路口的时间Ｐｅｔｒｉ舟模型　对于闭合路网的四相位十字路口的时间Ｐｅｔｒｉ网模型要　考虑到两个方向上的车流情况，在具体的建模如下：　图４中的参数说明见表ｌ和表２。在图４中，小的矩形　（ｂ）ｆｌ触发后ＰＮ状态　框代表有时间参数的变迁，短线表示没有时间参数的变迁；　圆圈代表库；黑点表示ｔｏｋｅｎ。　（ｃ）ｔ２触发后ＰＮ状态　圉１一个筲单的Ｐｅｔｒｉ罔　３交通信号控倒　相位是向一股或多股交通流显示的某一种交通信号序　列，十字路口的四相位信号方案见图２　。闭合路网见图３。　＼　啊４四相位十字麝口妁时问Ｐｅｔｒｉ－Ｉ楱星　表１圈４中库的含义　变迁　含义　东西方向红灯信号结束　东西方向绿灯信号结束　东西方向黄灯信号结束　　。／　东西方向车辆到达　东西方向车辆右转（概率）　／／　东西方向车辆左转（概率）　东西方向车辆直行（概率）　东西方向车辆进入十字路口　东西方向车辆离开十字路口　东西方向左拐进入主干道　圈２十字路口莳四相位信号方案　东西方向左拐车辆准备进入十字路口　东西方向右拐车辆准备进入十字路口　，　…　ｍ　—　，”　－１　，　表２圈４中变迁的含义　库　含义　Ｇ　Ａｌ　东西方向上绿灯信号　Ａ　Ａｌ　东西方向上黄灯信号　ＧＡＡｌ　东西方向上绿灯或黄灯信号　ＲＤＹ　Ａ１　东西方向上车辆准备好　ＩＮ　Ａｌ　东西方向上车辆准备进入十字路口　ＲＳＬ　Ａｌ　东西方向上车辆准备直行或者左拐　ｎ一２　Ｒ０ＵＴ　Ａ１　右转离开十字路口　ＩＮＴ　Ａ１　车辆进入路口　ｌ　ＭＦ　ＡＩ　车辆直行　ｎ　ＯＵＴ　Ａ１　车辆离开路口　ＲｌＮ　Ａｌ　车辆右转后进入东西方向　ＬＯＵＴ　ＡＩ　东西方向上车辆左转后离开十字路１７１　ＬＡＲ　Ａ２　图３闭合路阿　车辆左转进入东西方向　ＬＩＮ　Ａ２　车辆准备左转进入东西方向　５　闭合路网控制系统的性能分析　５．１算法　假定在一个闭合路网中共有ｍＸｎ个十字路口，分别记　为，』∥＝１，２，…，ｍＴ＝１，２，…，ｎ，如图３所示。在　，和，ｆ　，之问的　Ａ如果（ＥＴ　—Ｄ　，）ｍｏｄ　ＪｐＤ∈（ＴＧ　，＋　，＋ＴＧ　，ＰＤ），则　Ａ２和ＧＡ—Ａ２包含有１个令牌，ｅａ—Ａ２的持续时间为（ＥＴ　，一　，ＯＳ　）ｒｏｏｄＰＤ一（ＴＧ　，＋　，＋ＴＧ　）。　路段记为Ｓ（ｉ，ｉ＋１），：ｉ＝１，２，…，ｍ－Ｉ　７＝１，２，…，ｎ。同样地，在，　７和，¨＋ｌ　之间的路段记为Ｓ　＋ｌ】：　１，２，…，　；　＝１，２，…，ｎ一１。路段　Ｓ（ｉｉ＋￣ｊ（Ｓｉｕｊ＋１））的长度记为ｄＧｉ＋１）ｊ（ｄｉｑｊ＋ｌ１），车辆通过每个路段的　，５．３性能分析　首先来考虑平均等待队列。令　为十字路１３　ｌｑ的ＳＴＰＮ　模型的可达状态。ＳＴ（Ｍ）为映射Ｍ的时间，Ｍ∈Ｒ　。假定模　拟开始时间为０，结束时间为Ｔｓ。那么ＷＥ和ＮＳ方向上十　字路口的平均队列长度（ＡＱＬｉ））为　ＡＱＬｉｊ－　１　时间是离散的，记为“（　＋１）ｊ（ａｉｑ，ｊ＋１））偏移量为研　＋Ｉ）ｊ（ｏｉ０ｊ＋１））。　｛ｘ　）｝记为ＷＥ方向第ｋ辆车到达十字路口　，的时间，　｛ｘ　１２（ｋ）｝记为ＷＥ方向第ｋ辆车离开十字路１３，　，的时间，　｛Ｘ　（　）｝记为Ｎｓ方向第ｋ辆车到达十字路１３，　，的时问，　∑［（Ｍ（ＲＳＬ＿ＡＩ）＋Ｍ（ＲＳＬ—Ａ２）＋Ｍ（ＬＴＯ—ＡＩ）＋Ｍ（ＬＴＯ—Ａ２）］ＳＴ（Ｍ）（２）　｛Ｘ　２２（女）｝记为Ｎｓ方向第ｋ辆车离开十字路口“的时间　。　模拟算法如下：　Ｓ１：根据指数分布，产生｛ｘ　，　（足）｝和｛Ｘ　２１（　）｝，　ｉ＝１，２，…，ｍ－Ｉ；ｊ＝ｌ，２，…，ｎ。令ｈ＝２。　Ｓ２：对于每一个十字路１３，　ｆ　＝　，，　是四相位的十字路　１３，图４中在｛ｘ　ｋ）｝时刻将模型中库ＩＮ—Ａ１装入令牌，在　｛Ｘｊ　（　）｝时刻将库ＩＮ—Ａ２装入令牌，然后开始模拟。同样地，　当令牌到达ＯＵＴ～Ａ１的时问为｛　（ｋ）｝，当令牌到达ＯＵＴ—Ａ２　的时问为｛Ｘ，２，２（　）｝。　Ｓ３：对于每个十字路１３来说，进入的车辆数量是离散的，　设为ａ（　＋ｌ　误差为研“＋１】ｆ。ｖ（　＋ｌ１肚）表示第ｋ辆车在路段Ｓ　）７　上的行驶速度。所以得到ｘ　（　）：ｘ　１２（　）＋　川１／　ｉｆ，ｉ＋ｌ￣ｊｆ　），那　么Ｘ　（七）就是车辆到达路　＋】ｌ，的时间。用同样的方法可以得　到Ｘ　（　）。令　：　＋１，如果ｈ＜ｍ＋ｎ，转到ｓ２。　ｓ４：计算该系统的性能。　５．２十字路１３　Ｐｅｔｒｉ网模型的初始状态　选择十字路口，ｌ１作为初始的十字路１３。ＰＤ为红绿灯一　个周期的时间，Ｄ　为ＥＢ方向上路口ｌｑ相对于，ｌｌ的偏移量，　Ｄ　为ｓＢ方向上路１３，　相对于，ｌＩ的偏移量。ＴＧ　ｉ和ＴＡ　ｉ　分　别表示ＥＢ方向上绿灯和黄灯的时问，　ｊ和　分别表示　Ｎｓ方向上绿灯和黄灯的时间。￡丁　和Ｅ７１ｊ分别表示ｘ　（　）　和Ｘ　（　）的最早时间。　ＰＤ＝ＴＧ　＋　，，＋　＋　ｊ　（１）　假设Ｅ７１　≤　，如果（ＥＴ　，－Ｄ　，）ｍｏｄ　ＰＤ∈（０，ＴＧ　，】，　则当第一个令牌装入ＩＮ—Ａ１时，所有的状态包括｛Ｇ—Ａ１，　Ａ—Ａ１　ＧＡ—Ａ１，Ｇ—Ａ２，ＡＡ２，ＧＡＡ２，ｅｇ—Ａ１．ｅａＡ１，ｅｇＡ２，　ｅａＡ２｝中，Ｇ—Ａｌ和ＧＡ—Ａ１包含有１个令牌，ｅｇ—Ａ１的持续　时间为（ＥＴ　１　ＯＳ　，）ｏｒｏｄ　ＰＤ。　如果（ＥＴ　，一Ｄ　，）ｍｏｄ　ＰＤ∈（ＴＧ　，，７１Ｇ　，＋　，），则当第一　个令牌装入ＩＮ—Ａｌ时，Ａ—Ａ１和ＧＡ—Ａ１包含有１个令牌，　ｅａＡ１的持续时间为【Ｅ７’：　一０ｓ　，）ｏｒｏｄ　ＰＤ－ＴＧ　，。　如果（ＥＴ　，一ＯＳ　Ｉ）ｏｒｏｄ　ＰＤ∈（ＴＧ　，＋７　，，ＴＧ　，＋ＴＡ　，＋　ＴＧ　），则Ｇ—Ａ２和ＧＡ—Ａ２包含有１个令牌，ｅｇ—Ａ２的持续　时问为（ＥＴ　一ＯＳ　，）ｏｒｏｄ　ＰＤ一（ＴＧ　＋　，）。　Ｍｅ　其中，Ｍ（ＲＳＬ—Ａ１）和Ｍ（ＲＳＬ～Ａ２）分别代表ＥＢ和ＳＢ方向上　直行的车辆数量；Ｍ（ＬＴＯ—Ａ１）和Ｍ（ＬＴＯ—Ａ２）分别代表ＥＢ和　ＳＢ方向上左拐的车辆数量。所以总的平均等待队列为　ＡＱＬ＝　１∑ＥＭＱＬ　（３）　ｉ＝１　ｊ＝ｌ　接下来考虑平均等待时间。令Ⅳ（，）为模型中变迁的触发　时间。则十字路１３的平均等待时Ｉｈ］（ＡＴＤ　，）为　ＡＴＤｉｊ＝　１［而　∑Ｍ（ＲＳＬ＿ＡＩ）ＳＴ（Ｍ）＋　Ｍ∈Ｒ　¨￣　Ｍ（ＲＳＬ＿Ａ２）ＳＴ（Ｍ）　Ｍ∈Ｒ　丽　Ｍ（ＲＳＬＡ１）ＳＴ（Ｍ）＋　Ｍ∈Ｒ　∑Ｍ（ＲＳＬ＿Ａ２）ＳＴ（Ｍ）ｌ　（４）　∈Ｒ　所以，总的平均等待时间为　ＡＴＤ＝∑ＭＴＤ　（５）　６结束语　本文介绍了一种新的交通控制系统的建模和性能评估技　术。用随机时间Ｐｅｔｒｉ网来描述十字路１３的交通控制和车辆运　行情况，并且使用分布式的模型来描述一个路段中相邻两个　十字路１３间的车辆运行情况。这种技术是基于单个十字路１３　的随机时间Ｐｅｔｒｉ网的原理来实现的，这样做比起其他对每个　方向同时建模的Ｐｅｔｒｉ网建模方法可以大大减少计算的复杂　性。将来的研究应该集中于以下两点：　（１）对更为复杂的十字路口建模，比如３相位的十字路口、　５相位的十字路１３以及无规律相位的十字路口。　（２）考虑更为复杂的交通网，比如说单行道和３叉路１３。　参考文献　【１］蒋昌俊．Ｐｅｔｒｉ网的行为理论及其应用　］．北京：高等教育出版　社，２００３　［２】马荣国，杨立波．交通工程设计理论与方法［Ｍ１．北京：人民交　通出版社，２００２．　［３］ＤｉＣｅｓａｒｅ　Ｋｕｌｐ　Ｇｉｌｅ　Ｋ，ｅｔ　ａ１．Ｔｈｅ　Ａｐｐｌｉｃａｔｉｏｎ　ｏｆ　Ｐｅｔｒｉ　Ｎｅｔｓ　ｔｏ　ｔｈｅ　Ｍｏｄｅｌｉｎｇ　Ａｎａｌｙｓｉｓ　ａｎｄ　Ｃｏｎｔｒｏｌ　ｏｆ　Ｉｎｔｅｌｌｉｇｅｎｔ　Ｕｒｂａｎ　Ｔｒａｆｉｆｃ　Ｎｅｔｗｏｒｋｓ［Ｍ］．ｉｓ．１．］：Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，１９９４：２—１５　［４１　Ｌｅｄｏｕｘ　Ｃ．Ａｎ　Ｕｒｂａｎ　Ｔｒａｆｆｉｃ　Ｆｌｏｗ　Ｍｏｄｅｌ　Ｉｎｔｅｇｒａｔｉｎｇ　Ｎｅｕｒａｌ　Ｎｅｔｗｏｒｋｓ［Ｊ］．Ｔｒａｎｓｐｏｒｔａｔｉｏｎ　Ｒｅｓｅａｒｃｈ，１９９７，５ｔ５）：２８７—３００．