2008研究生数学建模获一等奖论文

全国第五届研究生数学建模竞赛

题 目 城市道路交通信号实时控制问题

摘 要：

目前，城市交通问题已成为民生问题的一个焦点。解决该问题的关键是能够优化配置城市交通资源，而其中一种重要手段就是设计有效的路口信号灯控制方案。本论文就此提出路口信号灯的一种实时控制策略。

为使所有路口的车辆延误时间缩减至最短，文中首先建立了单个十字路口模型所需的优化函数，通过粒子群算法求解该优化函数得到模型所需的优化配置方案。其次利用单路口优化配置方案，我们给出线状双十字路口以及网状五十字路口的优化方案。同时我们给出根据泊松分布生成交通流序列的方法，并利用生成的交通流序列模拟实际的交通运行。最后我们根据生成的交通流对优化方案进行数值试验，将实验结果与固定周期的信号灯控制方案进行对比，分析我们的优化方案的优缺点以及算法的复杂度，并给出本方案的使用建议。

【关键字】

交通信号 粒子群算法 单路口 多路口

参赛密码 （由组委会填写） 参赛队号 1038402

1 问题重述

随着社会经济的发展，交通拥挤、交通事故、环境污染、能源短缺等交通相关问题成为世界各国共同面临的一大问题。其中，如何对交通情况进行合理调控成为人们普遍关注的话题之一。而对于一个城市而言，对于交通的调控的一个重要手段就是对于十字路口的信号灯系统进行优化配置，以起到对于交通资源进行最优配置的作用。下面，我们以“十字路口车辆的延误时间最短”作为信号灯系统的优化指标，在已知车流量信息的前提下，考虑头车启动以及色灯响应时间等损失，对于非饱和路口的信号灯系统进行建模并优化配置。

我们需要考虑的问题如下：

（1） 对于非饱和的单个十字路口，线状双十字路口区域，网状五十字路口区域建

立信号灯决策方案。

（2） 建立实现决策方案的算法

（3） 建立虚拟的交通流序列以进行模型的数值试验。

（4） 分析模型以及算法的优缺点，提出决策方案的适用范围，以及模型的改进意

见。

2 模型假设

基本假设1：在一个周期内车流量保持不变。 基本假设2：路口非饱和且通行能力非常大。

基本假设3：需决策信号灯周期开始前，当前路口的流量，车辆滞留情况及相邻路口

的当前周期决策方案（多路口时使用）可捕获。

基本假设4：模型优化目标为车辆延误时间最短。

3 问题分析与模型建立

3.1单点十字路口实时配时优化模型 3.1.1 符号说明：

图1 单点十字路口

我们按图1标定路口中的四个通行道。

2

T：周期长

TMAX:周期上限

TWTWi:一个周期内全体车辆总延误时间

:一个周期内第i相位全体车辆总延误时间

:绿灯时头车启动以及色灯响应，信号灯转换的损失时间

个相位的绿灯时间

TlostTi:一个周期内第inij:从第

i通行道到第j通行道的车流量

tmin:每个相位最小配时

tmax:每个相位最长配时

?ij：在一个周期开始时在路口已积累的需要从i通行道流向j通行道的车辆数

3.1.2 模型描述

该模型的主要考察目标为使得单位时间单个车辆平均等待时间最短。首先考察第一相位所有车辆等待时间TW1，问题的重点转化为计算该相位一个周期内的所有等待车辆数。

由于我们认为在一个周期内车流量保持不变，所以我们有如下假设。

单点模型假设1:第一相位开始时的流量就是该周期内的流量。

我们首先考虑在第一相位绿灯时间结束前到达第一相位的车辆。对于模型的初始状态来说，在第一相位有在该相位开始时即累积在该处的车辆?12??34(此数据可通过观测捕捉)，这些车辆它们在第一相位开始时均延误了Tlost的时间，并且由于我们假设道路非饱和，则它们在第一相位结束后均通过了路口，无延误时间，而同时在Tlost的时间

Tlost中有车辆到达第一相位，它们所延误的时间加总应为?i，所以我们可以得到以下结果。

i?1

单点模型推论1：第一相位绿灯时间结束前到达第一相位的车辆延误时间为

Tlost(?12??34)*Tlost+(n12+n34)*?i

i?13

下面我们考虑在第一相位结束后到来的车辆，从实际情况上看，当一个路口出现红灯时，在该路口等待排队的车辆并不是同时出现的，而是经过一段时间累积而成的，而先开始等待的车辆所延误的时间与后到来的车辆所延误的时间是不同的。由此我们对于问题给出如下假设。

单点模型假设2:若车流量为nij，则当从i路口向j路口的方向变为红灯后，我们认为在此相位等待的车辆从零开始，每秒钟增加nij辆。

以在第一相位通行的车辆为例，因为我们考虑的路口是非饱和的，当第一相位刚刚结束时的下一秒在该路口停滞的车辆共有n12+n34辆，这些车辆中每辆车因为红灯所延误的时间均为T-T1，而当下一秒时在该路口停滞的车辆增加了n12+n34辆，这些新增的车辆中每辆车因为红灯所延误的时间为T-T1-1，依此类推。

由此我们得到如下推论。

单点模型推论2:第一相位绿灯时间结束后到达第一相位的车辆在该周期由于红灯所延误的时间加总为(n12+n34)*?i。

i?1T?TI

而该相位的车辆在该周期所延误的时间还因包括第一相位绿灯时头车启动以及色灯响应，信号灯转换的损失时间，其对于每一辆车而言我们都认为是一个常数，由实际观测得到，记为Tlost,对于我们的模型，我们可以近似的认为实际上绿灯的有效通行时间应该为T1?Tlost,则我们有如下推论。

单点模型推论3: 第一相位绿灯时间结束后到达第一相位的车辆在该周期内总延误

T?TI?Tlost时间为(?i?1i)*(n12+n34)。

我们所计算的一周期内车辆在第一相位总延误时间应该为推论1和推论3所导出的值的和。所以我们有

单点模型推论4：第一相位车辆在一个周期内总的延误时间为

TlostT?TI?TlostTW1=(?12??34)*Tlost+(?i)*(n12+n34)+(i?1?i?1i)*(n12+n34)

4

接着我们可以得到其他相位的车辆在该周期内的总延误时间。由于其计算较为复杂，所以在这里我们仅列出第二相位的车辆在该周期内的总延误时间的计算过程，其余两相位只给出结果。

对于第二相位，我们将车辆的情况分为第二相位绿灯结束前到达第二相位的车辆以及第二相位绿灯结束后到达第二相位的车辆。前者可以分为两部分，一部分是在这一周期开始时就已经在第二相位等待的车辆?13??31，它们延误的时间为

(?13??31)*(T1?Tlost)T1，另一部分是在该周期第一相位绿灯时到达的车辆，它们延误的

时间为(?i)*(n13+n31)。因此第二相位绿灯结束前到达第二相位的车辆总延误时间为

i?1(?13??31)*(T1?Tlost)+(?i)*(n13+n31)。

i?1T1依此类推，我们也可以得出在第二相位绿灯结束后到达第二相位的车辆在该周期内总延误时间为

T3?T4?Tlost(?i?1i)*(n13?n31)

根据上面的分析，我们得到：

单点模型推论5：第二相位车辆在一个周期内总的延误时间为

T1T3?T4?TlostTW2?(?13??31)*(T1?Tlost)?(?i)*(n13?n31)?(i?1?i?1i)*(n13?n31)

同理，我们得到第三相位和第四相位在一个周期内的总延误时间分别为

T1?T2T4?TlostTW3=(?23??41)(T1?T2?Tlost)?(?i)*(n23?n41)?(i?1T?T4?i?1i)(n23?n41)

TlostTW4=(?24??42)(T1?T2?T3?Tlost)?(?i)*(n24?n42)?(?i)(n24?n42)

i?1i?1从而总延误时间即为：

4TW??T

Wii?1因此我们的目标优化函数即为单位时间内的单位车辆的平均延误时间（即将总延误时间TW除以周期时间T以及车辆总数?nij+??i）。

Z(T1,T2,T3,T4)=TW/(T*T*(?n?ij??i)),因为我们是在假设周期时长足够短的情况

5

下才能给出在该周期内车流量保持不变的假定，因此有必要给T一个上界TMAX,同时每个相位的绿灯时间也不能太短或太长，太短则车辆来不及通过路口，不能保证路口是非饱和的，太长则司机心理上无法忍受，因此我们有约束条件:

T?TMAX,tmin?Ti?tmax(界限值由经验值给出)

从而问题转化为在已知各个路口的流量情况nij下以及在上述两约束条件的前提下，求出使得Z(T1,T2,T3,T4)最小的Ti的值。 3.1.3 模型建立

根据3.1.2的讨论，我们得到了如下模型。

单点十字路口实时配时优化: 目标函数：

minZ(T1,T2,T3,T4)=TW/(T*T*(?n?ij4??i))

TW?Tlost?T

Wii?1T?TI?TlostTW1?(?12??34)*Tlost?(?i)*(n12?n34)?(i?1T1?i?1i)*(n12?n34)

T3?T4?TlostTW2?(?13??31)*(T1?Tlost)?(?i)*(n13?n31)?(i?1T1?T2?i?1i)*(n13?n31)

T4?TlostTW3=(?23??41)(T1?T2?Tlost)?(?i)*(n23?n41)?(i?1T?T4?i?1i)(n23?n41)

TlostTW4=(?24??42)(T1?T2?T3?Tlost)?(?i)*(n24?n42)?(?i)(n24?n42)

i?1i?1约束条件:

T?TMAX

tmin?Ti?tmax

3.1.4 模型求解

这是一个优化问题。我们比较了多种算法之后，最终选择粒子群优化算法(PSO)来求解此问题。

PSO优化算法[1，2]是由James.Kennedy（肯尼迪）博士和R．C．Eberhart博士于1995年提出的。该算法源于对鸟群、鱼群觅食行为的模拟。在PSO中，首先初始化一群随机粒子(随机解)，然后通过迭代寻找最优解。在每一次迭代中，粒子通过跟踪两个极值来

6

更新自己的速度和位置。第一个就是粒子本身所找到的最优解，这个解叫做个体极值；另一个极值是整个种群目前找到的最优解，这个极值是全局极值，另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。PSO 算法简单易实现，不需要调整很多参数。

PSO优化算法是基于群体的演化算法,其思想来源于人工生命和演化计算理论。Reynolds 对鸟群飞行的研究发现,鸟仅仅是追踪它有限数量的邻居, 但最终的整体结果是整个鸟群好像在一个中心的控制之下,即复杂的全局行为是由简单规则的相互作用引起的。PSO即源于对鸟群捕食行为的研究,一群鸟在随机搜寻食物,如果这个区域里只有一块食物,那么找到食物的最简单有效的策略就是搜寻目前离食物最近的鸟的周围区域。人们从鸟群捕食模型中得到启示,并应用于解决优化问题。在PSO中,每个优化问题的解都是搜索空间中的一只“鸟”,称之为粒子(Particle)。所有的粒子都有一个由被优化的函数决定的适应值(Fitness.Value),每个粒子还有一个速度(Velocity)决定它们飞翔的方向和距离。PSO初始化为一群随机粒子(随机解)。然后,粒子们就追随当前的最优粒子在解空间中搜索找到最优解。在每一次迭代中,粒子通过跟踪两个“极值”来更新自己，即跟踪个体极值(Personal Best)和全局极值(GlobalBest)。PSO算法就是从这种模型中得到启示而产生的,并用于解决优化问题的。另外,人们通常是以他们自己及他人的经验来作为决策的依据,这就构成了PSO 的一个基本概念。PSO求解优化问题时, 问题的解对应于搜索空间中一只鸟的位置, 称这些鸟为“粒子”(particle) 或“智能体”(agent)。每个粒子都有自己的位置和速度(决定飞行的方向和距离),还有一个由被优化函数决定的适应值。各个粒子记忆、追随当前的最优粒子,在解空间中搜索。每次迭代的过程不是完全随机的,如果找到较好解,将会以此为依据来寻找下一个解。令PSO 初始化为一群随机粒子(随机解),在每一次迭代中, 粒子通过跟踪两个“极值”来更新自己: 第一个就是粒子本身所找到的最好解,这个个体极值点用pbest[]表示（其位置）, 全局版PSO中的另一个极值点是整个种群目前找到的最好解,这个全局极值点用gbest表示（其位置),而局部版PSO不用整个种群而是用其中一部分作为粒子的邻居,所有邻居中的最好解就是局部极值点(用lbest表示其位置)。

下面给出算法中粒子的速度和位置的更新方程。 速度更新方程：

Vid(t?1)?w*Vid(t)?c1*rand()*(Pid(t)?Xid(t))?c2*Rand()*(Pgd(t)?Xgd(t))

位置更新方程：

Xid(t?1)?Xid(t)?Vid(t?1)

其中，Vid(t)是粒子原来的速度，Vid(t?1)是粒子当前的速度， Xid(t)是粒子当前的位置，Xid(t?1)是粒子产生的新位置，Pid(t)为个体最优解，Pgd(t)为全体最优解，c1,c2为加速系数，是正常数，也称为学习因子，rand()和Rand()为[0，1]之间的随机数。

Vid(t)是粒子

i在t时刻(或第t次迭代)第d维的速度;c1,c2分别调节向全局最好粒

子和个体最好粒子方向飞行的最大步长,若太小,则粒子可能远离目标区域,若太大则会导致突然向目标区域飞去,或飞过目标区域。合适的c1,c2可以加快收敛且不易陷入局部最优,通常令c1?c2?2。Pid是粒子i在第d维的个体极值点的位置(即坐标)。Pgd是整

7

个群在第d维的全局极值点的位置。为防止粒子远离搜索空间,粒子的每一维速度都会被限定在[?Vdmax,?Vdmax]之间,太大,粒子将飞离最好解,太小将会陷入局部最优。假设将搜索空间的第d维定义为区间[Xdmin,Xdmax],则通常Vdmax?k*(Xdmax?Xdmin)/2,0.1≤k≤1.0,每一维都用相同的设置方法。下面给出算法的流程。

Step1 初始化 初始搜索点的位置及其速度通常是在允许的范围内随机产生的,每个粒子的pbest坐标设置为其当前位置,且计算出其相应的个体极值(即个体极值点的适应度值),而全局极值(即全局极值点的适应度值)就是个体极值中最好的,记录该最好值的粒子序号,并将gbest设置为该最好粒子的当前位置。

Step2 评价每一个粒子 计算粒子的适应值,如果好于该粒子当前的个体极值,则将pbest设置为该粒子的位置,且更新个体极值。如果所有粒子的个体极值中最好的好于当前的全局极值,则将gbest设置为该粒子的位置,记录该粒子的序号,且更新全局极值。

Step3 粒子的更新 用粒子的速度和位置的更新方程对每一个粒子的速度和位置进行更新。

Step4 检验是否符合结束条件 如果当前的迭代次数达到了预先设定的最大次数(或达到最小误差要求),则停止迭代,输出最优解, 否则转到Step2。

该算法流程图如下：（算法实现）

图2 PSO算法流程图

3.2线状双十字路口实时优化配置模型 3.2.1 符号说明

8

图2 双十字路口图

T甲：甲路口的周期 ：乙路口的周期

i相位的緑信比 T乙ki甲:甲路口ki乙:乙路口i相位的緑信比 内部通行道：即指通行道3、5 其余符号与单路口模型相同。

3.2.2 模型描述：

对于线状双十字路口，我们可以看到对于外围6个通行道的流量是互相不受干扰的。所以我们得到：

线状模型假设1：除了从通行道3，5出发的车之外，所有的流量数据我们均可直接获得。

现在需要考虑的就是内部的两个通行道的流量情况会受到彼此红绿灯配置方案的影响，因此我们的模型的关键就在于给出对于内部两个路口的流量预测方式并根据其分别利用单路口的优化配置方案进行优化配置。为此，该模型的关键就在于如何预测两内部通行道的流量。我们给出如下假定以预测两通行道的流量，

线状模型假设2：内部两通行道的流量，例如从通行道3出发的车流量，由乙路口上一周期的优化配置方案决定。

下面给出预测方法。

当甲路口需要调度时，我们可以捕获的信息为甲路口当前的通行道1，2，4的流量信息、通行道3的滞留车辆信息以及乙路口当前周期的配置方案，这时我们采用如下方法预测路口3的流量， 在乙的上个周期中流入甲的通行道3的车辆应为，

T乙*(k2乙*n75?k3乙*n85?n65)，我们用这个车辆数除以T乙做为该时刻通行道3的总车

9

流量

?n，并假设通行道3驶向1，2，4通行道的车辆基本上是一样多的，于是我们

3ii?1,2,4得到：

线状模型推论1：通行道3的流量数据预测值：

n3i?(k2乙*n75?k3乙*n85?n65)/3

由对称性我们亦可得到通行道5的流量数据预测值。

然后根据该预测值以及通行道1，2，4的流量信息按照上文的单路口优化模型给出甲路口此时的调度方案。当乙路口需要调度时方法同理。

3.2.3 模型求解

我们的线状双十字路口配置方案将在单十字路口的基础上产生，下面给出构造双路口配置方案的算法。

Step1:路口甲（乙）处在需调度时刻，捕获路口乙（甲）的配置方案以及 路口甲（乙）的1，2，4三通行道的流量信息。

Step2:根据路口乙（甲）的配置方案计算出3路口可能的流量信息。

Step3:根据1，2，4三通行道的流量信息以及计算出的通行道4的流量信息，依照单路口模型的配置方案给出甲路口此时的调度方法。

Step4:考察路口甲和路口乙谁先结束绿灯周期，先结束绿灯周期的路口即为需要调度的路口。

Step5:对于需要调度的路口依照从1开始到4的步骤进行循环。 3.3网状五十字路口实时优化配置模型 3.3.1 符号说明

同线状路口模型

10

图3 网状十字路口图

3.3.2 模型叙述

对于网状模型，我们基本上可以利用线状模型的结果来生成，与线状模型相同，我们可以得到：

网状模型假设1：所有外部通行道的数据我们均可直接得到。 网状模型假设2：所有内部通行道的数据由其相邻路口的信号灯上一周期优化配置情况决定。

4 数值试验与模型结果分析

因此我们仿照线状模型的讨论方式即可得到对于网状模型需要的所有数据并生成优化配置方案。具体步骤与线状模型基本相同。

4.1 交通流序列的生成

某一固定时间内到达的车辆数服从一定的分布，因此，我们设计了一种根据历史数据训练，生成相应分布的随机数序列来模拟交通流序列。

首先，常见的交通流分布有Poisson分布，二项分布及负二项分布三种。其中Poisson分布用来描述间隔时间极短，车流密度不大，车辆间相互影响较小，其他外界干扰基本不存在的交通状况，二项分布用于描述车辆比较拥挤，自由行驶机会不多的车流状况，负二项分布用于描述车辆稀密相同，具有高方差的车流。由于我们的模型假设是建立在非饱和的基础上的，综合考虑，我们决定使用Poisson分布来生成交通流序列。

交通流服从的Poisson分布如下：

P[N(t)?K]?(?t)KK!e??t， K?0,1,2,.....;

11

其中，N(t)表示时间t时到达的车辆数。P[N(t)?K]表示t时刻到达K辆车的概率。

?t表示计数间隔t内平均到达的车辆数，?表示车辆平均到达率，t为时间间隔持续的

时间。e为自然对数的底数,e=2.7182818。

其次，生成交通流序列，需要生成符合Poisson分布的随机数序列。生成符合某一分布随机数的算法一般是利用线性同余法生成符合均匀分布的随机数，然后在均为分布随机数的基础上利用反函数法，舍选法等算法来进一步产生符合其他分布的随机数。考虑到自己写算法所产生随机数的可用性，在我们的实验中，我们使用Matlab提供的Possion分布随机数函数来生成我们需要的随机数序列。

Matlab是根据Poisson分布的原型P[m?K]?(m)KK!e??t来生成Poisson分布随机数

的，所以这里传入的m的值对于本模型来说是?t,所以我们生成的随机数序列再除掉时间间隔t既为我们所生成的模拟交通流序列。

最后，根据以上分析，在生成Poisson分布随机数的过程中，需要传入?t，我们认为该值应该是个经验拟合值，是由历史数据拟合出来的。

在本模型中，我们认为每个通行道的车流分为3个流向，每个流向的车流都是服从Poisson分布的，对于单路口模型来说，我们需要生成4个通行道共12个流向的车流序列。对于线性双十字路口来说，我们需要生成外部6个通行道的18个流向的车流序列，内部的2个通行道的车流序列则根据流向该通行道的车辆随机分配来计算。

下面是根据上述分析给出的单通道一个流向的交通流序列生成算法：

Step1:选取某一实际路口，记录其在固定时间间隔t观察的平均到达车辆数数据，根据频率使用最大似然概率法等方法拟合出?t，同时记下时间间隔t。

Step2:根据?t，利用Matlab生成符号Poisson分布的随机数序列。 Step3:将上述随机数序列除以时间间隔t,从而得到模拟交通流序列。

4.2 模型试验

1、交通流序列生成要求：

对于各个模型，我们均生成各个通行道车辆到达率为40-120辆/分钟（随机）的数据五组进行试验。

2、根据交通流序列进行实际的模拟，分为两种方式进行红绿灯的优化配置。（1）我们给出的优化方案，（2）固定信号灯周期为360s，每相位固定为90s的红绿灯控制方案。试验模拟时间为10小时

3、以试验中两者的车辆总滞留时间为比较对象，对比两者的优劣。

4.3模型结果分析

以下只给出每次数据试验我们的实时优化方案和固定周期方案的总滞留时间。

12

单路口 实时方案 固定周期方案 第1次试验 39855509 46961411 第2次试验 35653356 40940251 第3次试验 32401046 38434350 第4次试验 41561615 43832865 第5次试验 26283353 32853676 双路口 实时方案 固定周期方案 实时方案/固定方案 第1次试验 48644467 74712297 65.1% 第2次试验 4756635 87469243 54.3% 第3次试验 59715771 88640380 67.3% 第4次试验 52347614 87187620 60.0% 第5次试验 48363493 81164341 59.6% 五路口 实时方案 固定周期方案 实时方案/固定方案 第1次试验 113605036 142969853 79.4% 第2次试验 123124707 182789823 67.3% 第3次试验 89858188 124986356 71.9% 第4次试验 110507074 140074042 78.9% 第5次试验 133040157 156306112 85.1% 由表格可见，我们的方案使得车辆的滞留时间有了近25%的减少，因此我们认为我们的实时方案是有效的。

（单位：s） 实时方案/固定方案 84.8% 87.0% 84.3% 94.8% 80.0% 5 模型评价和建议

5.1 模型优点

1、PSO算法求解速度快，可以全局搜索，得到很好的近似解。

2、模型中对于车辆的延误时间有精确的分类讨论以得到优化函数，可以保证配置方案的最优化。

3、将单路口模型的配置方案经过简单的处理即可用到其余的多路口模型上。

5.2 模型缺陷

1、模型需要捕捉车流量以及当前路口车辆滞留量为外部参数，这要求对于当前路口的车流量有准确的测量方法。

2、对于路口饱和的情况本模型未予考虑。 5.3 算法复杂性分析

PSO算法的时间复杂性很小，假设粒子个数为n，搜索次数为m，则此算法的时间复杂性为O（n*m）。这是PSO算法的最大的优点之一。可以满足实时调控的需要。此算法可以保证模型的可行性。

13

5.4 应用建议

1、模型仅适用于处理路口非饱和的情况。

2、使用该模型时应考虑路面流量此时是否处于平稳状态，若是，则使用该模型。 3、采用测量上个周期的实际流量数做为我们进行下个周期决策时的流量参考值。

参考文献

[1] J.Kennedy,R.C.Eberhart,Particle Swarm Optimization,In: Proceedings of IEEE International Conference on Neural Network,Perth,Australia,Nov.1995, pp.1942–1948

[2] Y.Shi,R.C.Eberhart,A modified particle swarm optimizer,In: Proceedings of IEEE International Conference on Evolutionary Computation,1998,(5):69～73 [3] 徐勋倩, 黄卫, 单路口交通信号多相位实时控制模型及其算法, 控制理论与应用, 2005年03期

[4]陈琳 , 刘翔 , 孙优贤，单交叉路口交通流的通用多相位智能控制策略, 浙江大学学报（工学版），2006年11期

14

本文来源：https://www.bwwdw.com/article/tbi7.html