交通信号控制中的延误计算与分析
９６福建电脑２００７年第９期
交通信号控制中的延误计算与分析
关朴芳，陈成春，许
铁
（福建交通职业技术学院汽车系福建福州３５０００７）
摘【
分析了交通信号与延误相关参数之间的关系，并给要】：本文重点在于研究信号交通控制中的车辆延误计算问题。
出了一种延误计算的方法。
关键词】【：交通信号控制延误计算交通流
１．引言
信号交叉口的运行效率是由四个基本参数来衡量的，分别
是通行能力、饱和度、停车次数、车辆受阻延误时间，同时它们也是作为交叉口信号配时设计的基础。信号设计的目标就是寻求最大的通行能力，最低的饱和度，并且使得通过交叉口的全部车辆总延误时间最短或停车次数最少。当然，除了这四个基本的动态特性的参数外还有其它的次级参数，比如车辆在交叉口的燃油消耗量、废气排放量以及运营成本。本篇文章主要讨论的是其中的车辆受阻延误时间问题。
众所周知，车辆到达交叉口的时间间隔和单位时间段内到达停车线的车辆数都是随机变化的。所以，在每个信号周期内，总有一部分车辆在到达停车线之前后受到红灯阻滞。即便有些车辆是在绿灯期间可到达停车线的，但由于前面有上一次红灯阻滞而积存下的车辆阻挡，也不得不减速甚至停车等待，然后再起动车辆加速，逐渐穿过交叉口。实际上，这些车辆的延误也还是红灯阻滞的结果。如图１所示，给出了车辆在到达停车线前由于受到红灯信号的影响时，车辆逐渐减速停车，并等候一段时间后，又加速起动通过交叉口的过程。在图中，车辆在Ａ点开始减速，Ｃ点表示车辆完全停了下来，Ｄ点表示车辆开始起动，Ｆ点表示车辆加速到正常速度；ｔ１表示车辆在减速阶段所用时间，ｔ２表示车辆在加速阶段所用时间。有一点要注意，并不是所有车辆在受到阻挡后都完全停下来，而是呈现以下３种形式：（１）车辆在受到阻挡后，车速由正常速度逐渐下降，但是尚未停止下来，又马上起动加速，恢复到原有车速；（２）车辆在受到阻挡之后，车速由正常速度逐渐降到零，然后停撤等待了一段时间后，又起动加速，恢复到原来车速。（３）车辆在受到阻挡之后，车速由正常速度逐渐降低，并维持一段低速后又开始加速，
图１车辆通过交叉口的情形恢复到原有车速。
第（２）两种情况称为“在上述情况中，第（１）、构成一次完全停
车”，第（３）种情况称为＂构成一次不完全停车＂。可以看出，完全停车和不完全停车的区别在于：在完全停车情况下，车速是降到零后重新加速到正常速度；在不完全停车情况下，车速是还没有降到零就又开始加速。在车辆通过交叉口的延误时间里，都至少包含了一次停车（完全停车或不完全停车）。２．延误计算
一般来讲，车辆通过交叉口的延误时间主要是受车辆到图２车辆在交叉口受阻
延误与到达率的关系
达率和交叉口通过能力的影响。而车辆到达率和通过能力是随
时间变化的，这种变化是随机的，难以用数字模型加以表达。但是，如果某一交叉口的交通流量尚未达到饱和状态，仔细观察该交叉口处的交通情况可以发现，虽然某一较短时间段内交通量变化较大，但在一个较长的时间段内总的交通情况变化不大。正是基于这种现象，可以应用稳态理论分析车辆通过交叉口所受延误。这种理论基于如下假设：
（１）车辆到达率在所取时间段内稳定不变；（２）所考察的交叉口进口道通行能力为常数；
（３）车辆受信号阻挡所造成的行车延误与车辆到达率的相互关系在所研究时间段内保持不变；
（４）虽然有些车辆会受阻挡而形成排队，但是这些排队车辆在经过若干时间段后会消失。
依据上述假设条件，车辆延误时间可以简化成如下过程：（１）首先将车辆到达率视为常数，计算车辆的均衡相位延误；
（２）计算由于各个信号周期车辆到达率不一致产生的附加延误时间，其中包括在个别周期中由于入口车道处于饱和状态所产生的附加延误时间，统称为随机延误时间；
（３）将上述均衡相位延误时间和随机延误时间相加即可得到车辆的平均延误时间。
在均衡相位延误的研究中，一般在车辆到达率和进口车道通过能力均为常数的情况下，车辆的受阻延误与车辆到达率是
在该图中，ｔＥＲ表示有效红灯时间，呈现线性关系的，如图２所示。
ｔＧ表示绿灯时间，横轴表示时间，纵轴表示车流率。车辆Ａ在红灯时间到达时，其前方已经有车辆排队，它要经过一定的延误时间才能通过停车线。从这里不难看出，在三角形ＯＣＤ中，水平线对应为每一辆车的延误时间，而垂直直线为不同瞬时停车线后的车辆排队长度。这样，在到达率为一常数的情况下，一个信号周期内，全部车辆的总延误时间等于三角形的面积，即
（１）
式中：ｔＥＲ――有效红灯时间，等于周期时间减去有效绿灯时间，ｓ；
Ｈ――三角形的高。从图中可以看出：（２）式中：ｔＤＥ――这段时间对应为排队车队消散所需要时间；
ｑｓ――是入口车道的饱和流量。
在入口车道处于不饱和状态时，最大的排队长度简单地等于在有效红灯时间内所到达车辆数，即
ｔＤＥＮｕ＝ｑｔＥＲ（３）
由于在不饱和状态下，在绿灯时间内车队的净驶出率为，这样，在绿灯时间开始后，排队车辆消散所需要时间为：
（４）
（下转第８１页）
２００７年第９期福建电脑
８１
上面每个步骤时间复杂度均为Ｏ（Ｎ）。因为至多有［Ｌｏｇ２（ｎ＋１）］个阶段，所以在最坏情况下，生成ＳＡ的算法的时间复杂度为Ｏ
而算法的空间复杂度为Ｏ（Ｎ），其中Ｎ为ｔ的长度ｌｅｎ（ｔ），ｎ（Ｎｌｏｇｎ）。
为Ｄ中最长字符串的长度。
例１：令∑＝｛ａ，ｂ，ｃ｝，Ｄ＝｛ｂｂａｂａｂ，ａｂａｃａｃ，ｂｂａａａ｝，由Ｄ中各字符串生成的ｔ，广义后缀数组ＳＡ及相应后缀可以用图２表示。
图２：Ｄ的广义后缀数组及后缀列
３．算法分析
假设Ｎ为ｔ的长度ｌｅｎ（ｔ），ｎ为Ｄ中最长字符串的长度，在最坏情况下，生成ＳＡ数组的算法的时间复杂度为Ｏ（Ｎｌｏｇｎ），空间复杂度为Ｏ（Ｎ）。相对于文［５］提出的算法的时间复杂度为Ｏ（ＮｌｏｇＮ），有较大的改进。当对多个字符串进行处理时，由于Ｎ的长度远大于ｎ，故而算法效率较为明显。４．结束语
本文提出了一种高效的广义后缀数组的构造算法，使得算法效率可以达到Ｏ（Ｎｌｏｇｎ）。该算法可以用于二维模式匹配和Ｗｅｂ用户访问模式的挖掘中。由于广义后缀数组在字符串处理中具有较强的功能，笔者将进一步对其在实际工作的应用加以研究。
参考文献：
１．许智磊．后缀数组［Ｃ］．ＩＳＩ２００４国家集训队论文，２００４．
２．张长利，赫枫龄，左万利．一种基于后缀数组的无词典分词方法［Ｊ］．吉林大学学报（理学版），２００４，（１０）：５４８－５５３．
３．ＦｅｉＳｈｉ．ＳｕｆｆｉｘＡｒｒａｙｓｆｏｒＭｕｌｔｉｐｌｅｓｔｒｉｎｇｓ：ＡＭｅｔｈｏｄｆｏｒｏｎ－ｌｉｎｅＭｕｌｔｉｐｌｅＳｔｒｉｎｇＳｅａｒｃｈｅｓ［Ｊ］．Ｉｎ：ＬｅｃｔｕｒｅＮｏｔｅｓＩｎＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，１９９６．Ｖｏｌ．１１７９，１１－２２．
４．ＴｈｏｍａｓＨ．Ｃｏｒｍｅｎ，ＣｈａｒｌｅｓＥ．Ｌｅｉｓｅｒｓｏｎ，ＲｏｎａｌｄＬ．Ｒｉｖｅｓｔ，ＣｌｉｆｆｏｒｄＳｔｅｉｎ．ＩｎｔｒｏｄｕｃｔｉｏｎｔｏＡｌｇｏｒｉｔｈｍｓ．ＵＳＡ：ＴｈｅＭＩＴＰｒｅｓｓ，１９９０．
５．Ｍ．Ｉ．Ａｂｏｕｅｌｈｏｄａ，Ｓ．Ｋｕｒｔｚ，Ｅ．Ｏｈｌｅｂｕｓｃｈ．Ｒｅｐｌａｃｉｎｇｓｕｆｆｉｘｔｒｅｅｓｗｉｔｈｅｎｈａｎｃｅｄｓｕｆｆｉｘａｒｒａｙｓ［Ｊ］．ＤｉｓｃｒｅｔｅＡｌｇｏｒｉｔｈｍ，２：５３－８６，
２００４．
图１广义后缀数组构造２Ｈ阶段算法描述
"""""""""""""""""""""""""""""""""""""""""""""""
（上接第９６页）
由此可得：
真正了解了的延误计算相关参数的影响才能准确的计算出车辆的延误时间。延误计算结果将被用于信号优化配时，更说明了准确计算的必要性。
参考文献：
１．荆便顺．道路交通控制工程［Ｍ］．北京：人民交通出版社，１９９５．１１９￣１３１．２．全永燊．城市交通控制［Ｍ］．北京：人民交通出版社，１９８９．１１￣９５．
３．尹宏宾徐建闽．道路交通控制技术［Ｍ］．广州：华南理工大学出版社，２０００，４．１２￣６４．
４．黄辉先．城市交通信号优化控制方法的研究：［博士学位论文］［Ｄ］．西安：西北工业大学控制理论与控制专业，２０００．２６￣３１．
５．徐吉万．．城市交通的计算机控制和管理［Ｍ］．北京：测绘出版社，，１９８８．６．吴瑞麟，沈建武．城市道路设计［Ｍ］．北京：人民交通出版社，２００３．１１０￣１２７．
７．杨佩昆，吴兵．交通管理与控制［Ｍ］．北京：人民交通出版社，２００３，２．７９￣１４４．
８．杨晓光等．城市道路交通设计指南［Ｍ］．北京：人民交通出版社，２００３，６．１２０￣１５８．
９．徐吉谦．交通工程总论．［Ｍ］．北京：人民交通出版社．１９８９，６．５１￣９２．
（５）
上式求出的是一个信号周期内车辆的总延误时间。由于一个周期内到达车辆数是，因此每辆车的平均延误时间是
（６）
将关系式
，
，
代入上式中有
（７）
上式给出了均衡相位延误时间的表达式。显然信号周期会影响车辆通过交叉口所受到的平均延误。若周期很短，则损失时间所占比例较大，并引起延误过长，交叉口通行效率较低。另一方面，周期过长，待行车辆（红灯期间在停车线后排队等候的车辆）有可能在绿灯开放后不久就可以从停车线后驶完，而在绿灯后期通过停车线的少数车，将是那些以稀疏车距到达的车辆，这不利于绿灯时间的充分利用。图３给出了信号周期和车辆延误时间的关系图。
上式也同样可以说明饱和度也对延误有影响。图４给出了均匀延误和随机延误与饱和度的关系，ｔｕ表示均衡相位的延误时间，ｔｓ表示随机延误时间。从图中可以看出：随机延误随着饱
图３信号周期与延误时间关系和度的增加而上升得很快，均衡延误增加的较为平缓。
３．小结
从上面的分析看延误计算与周期、饱和度等都有关系，只有