基于粒子群算法下的交叉口信号配时优化

徐明杰，韩 印 （上海理工大学 管理学院，上海 200093）

0 引 言

当下我国的机动车保有量日益增加，城市交通问题已经成为一大难题。在城市道路网中，交叉口的畅行程度直接影响路网的服务与通行能力水平，而交叉口却是发生拥堵的主要地段，因此对交叉口采取合理的优化设计及控制是提高道路通行能力的重要手段[1]。优化交叉口的方法有很多，其中优化交叉口信号配时是最直接有效的方法，合理的信号配时可以有效降低交叉口的延误，因此交叉口的信号配时优化显得尤为重要。

关于交叉口信号配时优化，国内外学者专家进行了大量研究。总体而言可以分为2类方向，第一类是单纯的针对单点交叉口进行信号配时优化，如：Mohajerpoor[2]等提出了一种基于冲击波理论的计算交叉口延误的方法，给出了一种新的最佳信号配时公式；Ceylan[3]通过周期和相位绿信灯时间和周期作为约束，总延误和总停车次数最小为目标，使用遗传算法进行求解，获得最优解；黄敏[4]通过分析传统的交叉口信号配时方法，使用改进的蚁群算法来进行求解优化；Yu[5]等将行人和车辆的总延误作为目标函数，且将目标函数构建成为凸函数获得了全局最优解；付珊[6]通过分析交叉口左转待行区的设置条件，建立了交叉口左转车道的延误模型，并使用了遗传算法进行求解；王秋平[7]等通过分析单点交叉口的车流特性，建立以平均延误、平均停车次数最少的多目标函数，并分别使用遗传算法、遗传模拟退火算法进行求解，上述研究侧重于静态交通流下的信号配时研究。第二类是考虑交通流的随机性，针对单点交叉口的动态控制进行研究，如：邹娟[8]等通过改进元胞传输模型，建立了适用于多个相位控制的交叉口信号配时优化模型，采用了蜜蜂算法对其进行动态配时优化；王逸[9]等通过建立交叉口平均延误为优化目标，以各个相位绿灯时间作为约束条件并采用了自适应下的遗传算法进行求解；曹阳[10]则是建立了以交叉口车辆的平均延误最小的模型，在进行神经网络预测各进口道短时间交通流到达情况前提下，基于模拟退火算法提出交通信号控制的动态配时方法；Yang[11]等为了降低车辆延误，提出了一种基于改进遗传算法的交叉口协调控制信号的方法；此外，也有学者结合了VISSIM和SYCHRO的优点，针对交叉口进行信号优化，如：陈东芳[12]通过把VISSIM和SYCHRO软件结合起来进行对交叉口信号优化。在上述文献中，大部分学者都是构建目标函数，使用当下发展迅猛的智能算法进行求解或者通过软件仿真得出结论。然而，这些算法本身具有一定的复杂性，理解和操作起来也较为困难。相比而言粒子群算法具有程序简单、收敛速度快、容易操作等特点；并且通过提高算法系统的稳定性，不仅可以提高粒子群算法的稳定性避免获得随机解，而且可以提高算法的全局搜索能力，防止早熟。因此本文将构建以平均停车次数和平均延误最小、交叉口通行能力最大的函数，并使用动态的加权系数使其成为单一目标函数，然后使用改进后的粒子群算法进行交叉口信号配时优化。

1 模型建立

交叉口信号配时的目标就是要求获得最大的通行能力、最小延误、最小的停车次数、最短的排队长度、车辆的油耗最低等，其中，最小延误、停车次数、通行能力是评价交叉口运行状况的重要指标。韦伯斯特给出的最佳周期计算公式，是建立在以交叉口最小延误为目标的基础上通过求导和近似计算得出的，并没有综合考虑到上述指标，因此选取延误、停车次数、通行能力作为模型的构建部分。

1.1 韦伯斯特延误模型

延误是指车辆在受阻的情况下通过交叉口所需时间与正常行驶所需要的时间之差。计算交叉口延误的模型有很多，常见的有HCM2000模型、韦氏延误模型等。其中韦氏模型及其相应的改进模型被使用的频率较高，其主要由2部分组成，一部分称为均衡相位延误，使用符号表示，它是根据稳态理论得到的。另外一部分是随机延误，使用符号表示。计算公式分别为：

dij表示第i相位j个车道组的平均延误，qij表示第i相位j个车道组的当量车流量，那么整个交叉口的平均延误d表示为：

1.2 平均停车次数

第i相位j个车道组的平均停车次数使用符号hij表示，计算公式为：

那么整个交叉口的平均停车次数h可表示为：

1.3 交叉口通行能力

第i相位j个车道组的通行能力使用符号Qij表示，计算公式为：

那么整个交叉口的通行Q能力计算为：

1.4 动态权重系数

分析上述模型的架构过程不难看出，最后的模型是在共同的约束条件下的多目标优化问题，解决多目标优化问题一般有二种做法，一是分层序列法，二是把多目标转化为单一目标的函数问题，本文采用第二种方法。把多目标转换为单目标方法一般采取线性加权组合法，即根据各个目标函数的重要程度，乘上权重系数，构成一个目标函数。关于权重系数的选取，大部分的学者都是人为的设置加权系数，这样设置虽然易于求解但是不能反应出交通流的动态性，廖诗琪[13]曾引入了随着某一相位关键车道变化的动态权重系数，取得了良好的效果，但是不能够反映出每个车道的变化情况，因此本文为改进上述不足对权重公式进行推广。分别选取动态延误权重系数、停车权重系数和通行能力权重系数。由这3个动态权重系数分别对i相位j个车道组的延误、通行能力和停车次数进行修正，并将多目标优化问题转化为单一目标问题。计算公式分别为：

其中：Y是各个相位的关键流量比之和，c是周期（s），是第i相位j个车道组的饱和流量。

1.5 配时模型

构建如下的目标函数：

即：

在模型中k为大于0的常数，为了求得通行能力的最大值，将其取倒数并乘上系数k，这样就使得求通行能力目标函数最大值变成为求最小值，L表示交叉口总损失时间。

2 粒子群算法

从上面的模型可以看出，信号配时模型是一个非线性的最优化问题，解决这个问题有很多有效的办法，不少学者使用了遗传算法、蚁群算法等，这些算法虽然可以求解问题，但方法本身有一定的复杂性，而粒子群算法具有简单、收敛速度快等特点，因此可以用于求解此模型。

粒子群算法是一种群体优化算法，源自于鸟类捕食的启发。粒子群算法首先在约束条件所围成的可行区域范围内初始化一群粒子，每个粒子都代表优化过程中的潜在解，每一个粒子使用位置、速度、适应度值三项指标表示该粒子特性，适应度值由事先编好的适应度函数计算获得。适应度值的大小用于评价粒子的好坏与否和确定粒子下一次更新位置与速度。粒子在解集域内活动，通过追踪个体极值Pbest和群体极值Gbest更新位置，粒子每更新一次位置，就计算适应度值，然后通过比较新粒子适应度值、个体极值、群体极值来更新个体极值和群体极值位置。

2.1 算法系统稳定性改进

和大部分群体智能算法一样，粒子群算法虽然具有不少优点但也存在不少缺点，其中最主要的问题是算法的不稳定性。关于解决算法稳定性的相关研究不是很多，解决办法可以概括为2种，一种是在主程序中设置实验次数，即将一个程序多次计算，取最后的平均值作为计算结果，另外一种就是对初始化种群的适应度值进行扰动，即对适应度较大进行恰当缩小，适应度较小进行放大以均匀化初代群体，这样不仅可以提高算法的稳定性，还可以在一定程度上避免算法陷入早熟的情况，提高了算法的全局搜索能力。将上述方法结合起来使用，适应度值更新公式为：

（k）表示第k代群体的平均适应度值，（k）表示经过缩放后j个个体的适应度值，fj（k）表示k代群体第j个个体适应度值，ε表示缩放度，取值范围在［0.5,1］。

2.2 算法步骤

（1）首先生成满足约束条件的粒子群和初始化粒子的速度。

（2）根据定义好的目标函数计算初始化粒子的适应度值。

（3）对适应度值进行扰动，计算方法参考2.1。

（4）找到并记录初始化粒子中个体极值Pbest和群体极值Gbest，粒子位置。

（5）粒子通过个体极值和群体极值更新自身的速度和位置，计算更新后粒子的适应度值。速度和位置更新公式分别为：

其中：w是惯性权重参数，其取值影响算法的收敛速度和全局寻优能力；表示第k代粒子速度；表示迭代后粒子的速度；c1、c2是加速度因子（常数）；r1、r2是随机数其取值范围在［0,1 ］之间；表示迭代k次后粒子的个体最优值；表示迭代k次后粒子的群体最优值；表示迭代k次后粒子的位置。

（6）更新个体极值和群体极值。

（7）判断算法是否满足终止条件，如果满足终止条件则输出结果，否则重复执行5、6、7步骤，直到满足终止条件。

3 算例分析

本文选取了德州市临邑县的某十字形交叉口作为算例，并调查了其当前的信号配时方案，晚高峰小时流量和路面渠化状况，现状的渠化图如图1所示，现状流量如表1所示：

图1 交叉口现状渠化图

表1 交叉口流量调查表

当前的信号相位控制方案简述如下：第一相位东西方向放行，第二相位南北方向直行，第三相位南北方向左转。

在Matlab中编写程序语言，相关约束参数、算法参数分别设置如下：其中第一、二相位最小绿灯时间为20s，第一、二相位最大绿灯时间均设置为60s，第三相位最小绿灯时间设置为10s，最大设置为40s，最小周期时长设置为36s，最大周期时长设置为120s，交叉口信号总损失时间L为12s，各个车道组的饱和流率取1 250pcu/h；算法中的参数做如下设置：最大的迭代次数为300代，粒子规模为200个，每个粒子有3个位置分量，分别表示周期，第一相位有效绿灯时长，第二相位有效绿灯时长，第三相位有效绿灯时长，加速度因子c1、c2均取值为1.49445，惯性权重w参数则不是固定值，它随着迭代次数的改变而改变，其计算方法如下：

ws取值0.9，wend取值0.5，k表示第k次试验，maxgen表最大的迭代次数。其中每个实验设置运行100次，并将这100次的平均值作为最后的结果，这样可消除群体算法的不稳定性得出可靠的结果，最后的运行结果如表2所示，粒子群算法的收敛图像分析如图2所示，作为对比没有进行稳定性改进的算法收敛图像分析如图3所示。

从图2可以看出在300次的迭代过程中改进的粒子群算法于第216代开始收敛，运算结果如表2所示，从表2中结果可以发现，在使用粒子群算法进行配时后交叉口平均延误变为23，较之现状下降28%；平均停车次数变为0.76，较之现状下降了9%；理论通行能力变为3 280，较之现状提升了9%。同时可以看到粒子群在各方面的优化结果均优于Webster算法，体现了算法的优越性。从表2中结果和图2和图3的算法收敛曲线图对比中也可以看出，在进行算法的稳定性改进后算法进行了216次迭代计算趋于收敛，这验证了改进方法的可靠性，所得出的结果也基本避免了因为种群的随机性而导致结果的不合理性。

表2 算法结果对比表

4 结束语

本文研究分析了交叉口的评价因素，构建多目标的数学模型，且引入各个目标的权重系数使其转化为单一目标函数，最后使用了粒子群算法进行求解，在求解过程考虑了算法系统的稳定性，提高了结果的科学性，并获得了良好的信号配时方案，证明了算法和构建模型的可靠性。但是回顾研究发现，本文模型没有考虑到排队长度的约束，也没有考虑到行人安全等因素，另外在求解多目标的优化问题的方法上还可以做出改进，下一步将会对上述研究存在的不足进行修正，并继续结合智能算法进行交叉口优化，以期获得良好的效益。