基于整数规划模型的交通信号相位设计方法

摘要

本发明公开了一种基于整数规划模型的交通信号相位设计方法，包括下述步骤：S1、计算备选相位矩阵，具体为：建立灯组相容关系图Gh，处理两股以上车流的合流冲突，除掉合流冲突中灯组集合是两两相容但非相互相容的相位列，计算备选相位集合；S2、当灯组相容关系图Gh确定后，输入目标相位数，保证在一个相位周期CP内，每个灯组至少出现一次，所述相位周期CP是指从备选相位矩阵中选出的若干相位组成的相位周期；S3、建立考虑冲突因素的各车道流量、车头时距、人行过街长度的相位设计模型。本发明减化了相位设计中人为判断调整，利用模型进行自动从多种的相位组合情况中筛选合适交叉口的相位设计，减少了人力，也减少了对管理者的技术要求。

说明书

技术领域

本发明涉及智能交通中道路信号控制领域，更具体地说，涉及一种基于整数规划模型的交通信号相位设计方法。

背景技术

交通信号控制是从时间和空间上对网络的交通流进行分配，目的是将交通流均衡地分配到网络中去，以保障交通的安全、畅通、与有序。信号相位是交通信号控制的重要环节，信号相位设计是尽量把相互冲突或干扰严重的交通流适当的分离，减少交叉口交通冲突的干扰。

现有交通信号控制中的相位设计是通过对交叉口的基础数据进行采集，包括车道数、渠化划分、车流量等数据，通过人为的判断进行相位设计，判断依据是是否有冲突、时空利用率是否最大化。相位设计会出现多种的相位组合情况，从多种且大量的相位组合中挑选合适交叉口的相位设计是通过反复的人工调整，全凭管理者的经验，因此传统的交叉口的相位设计的科学性和合理性不能得到有效的保证。

发明内容

本发明的主要目的在于克服现有技术的缺点与不足，一种基于整数规划模型的交通信号相位设计方法，在面对已知相位数的情况下，从众多的相位组合情况中，能快速的找到适合该交叉口的相位设计，减少对经验的依赖，也减少人力成本。

为了达到上述目的，本发明采用以下技术方案：

本发明的公开的基于整数规划模型的交通信号相位设计方法，包括下述步骤：

S1、计算备选相位矩阵，具体计算方法包括下述步骤：

S11、建立灯组相容关系图G_h，以每个灯组为节点，若灯组i，j是相容的，则存在一条从结点i到结点j的无向的边，由这些结点和边组成的无向图即为灯组相容关系图G_h；

S12、除去冗余相位，在原始相位矩阵中，对比任意两列，按照冗余相位的定义，剔除冗余的相位列；

S13、处理两股以上车流的合流冲突，除掉合流冲突中灯组集合是两两相容但非相互相容的相位列，所述两两相容是指在对于一个灯组集合，任意两个灯组允许同时放行；相互相容是指所有灯组允许同时放行；

S14、计算备选相位集合；

S2、当灯组相容关系图G_h确定后，输入目标相位数，保证在一个相位周期C_P内，每个灯组至少出现一次，所述相位周期C_P是指从备选相位矩阵中选出的若干相位组成的相位周期；

S3、建立考虑冲突因素的各车道流量、车头时距、人行过街长度的相位设计模型。

作为优选的技术方案，步骤S1中，将备选相位矩阵A，每一列代表一个备选相位则：

其中α_ij＝0或1。

作为优选的技术方案，步骤S11中，在灯组相容关系图G_h中，一个灯组集合能组成一个相位的必要条件是，该集合中所有灯组两两相容；即：一个相位对应G_h中的一个完全子图，G_h的一个完全子图也可成为一个相位；并通过求解灯组相容关系图G_h的所有完全子图，得到所有相容灯组集合，作为原始备选相位矩阵，记该原始相位矩阵为A₀，然后筛选掉其中冗余和两两相容但不是互相相容的列。

作为优选的技术方案，步骤S12中，冗余相位的定义如下：

相位相对于是冗余的，当且仅当且U_i＝U_j，此时称为冗余相位。

作为优选的技术方案，步骤S13中，所述合流冲突的定义如下：

当两股或以上来自不同进口的车流汇入同一出口，此时产生合流冲突，合流冲突是否相容，取决于合流的进口车道数是否不超过出口的车道数；

指定是n股合流车流，(m₁,m₂,....m_n)是每股车流对应的车道数，m₀是出口的车道数，定义

作为优选的技术方案，步骤S14中，计算备选相位集合的具体方法为：

S141、通过交叉口的路面渠化情况及相容经验表、冲突值经验表，计算灯组相容矩阵H及灯组冲突值矩阵Ω；

S142、利用合流冲突原则，以及根据现场情况人为判断，修正灯组相容矩阵H；

S143、由修正后的灯组相容矩阵H得到灯组相容关系图G_h，计算相容关系图的所有团，得到原始相位集合矩阵A₀；

S144、计算原始矩阵A₀每一列的冲突值ω_j，剔除冗余相位的列；

S145、利用合流冲突原则，在A₀中剔除灯组两两相容但不是相互相容的相位列，最后得到备选相位矩阵A。

作为优选的技术方案，步骤S141中，所述灯组相容矩阵H具体为：

建立灯组相容矩阵，设灯组的编号为1-N，定义灯组相容矩阵H∈R^N×N为N×N的0-1矩阵：

其中，

最终可得

且由相容关系的对称性可知，灯组相容矩阵H为对称阵；

所述灯组冲突值矩阵Ω具体为：

建立灯组冲突值矩阵Ω，设灯组编号1～N，定义交叉口的灯组冲突值矩阵Ω∈R^N×N为N×N的矩阵

其中ω_ij∈[0,1)，为灯组i，j同时放行产生的冲突值，范围在[0,1)中

由冲突值关系的对称性可知，灯组冲突值矩阵Ω也是一个对称阵。

作为优选的技术方案，步骤S3具体为：

假设已知各个的车流量及饱和流量的比值为人行过街时取0，以及各个的人行需求时间取值由过街长度及人行速度计算得到，当为车道时取值为0，从而得到每个灯组的y值：

以及各个灯组的y^p值：

由此可得备选相位矩阵A中，每个备选相位的人行需求时间，记为

每个灯组，都有对应的损失时间l_i，当为人行过街灯组时；目标函数如下：

整个周期内满足每个灯组的人行需求：

把一个灯组看成一个水桶，根据水桶模型的原理，可知所有含灯组i的备选相位的时间和，应该满足：

其中

依然取d_j为0-1变量，λ_j＝180，由于每个含人行灯组的相位时间t_j必须满足该相位的人行需求时间

确定目标相位数：

记L＝(l₁,l₂,....l_N)^T，y＝(y₁,y₂,....y_N)^T矩阵A_y＝(y,y,....y)_m为N×m矩阵，综上，得到步骤S3中的相位设计模型为：

s.tAt≥y^p

(A-A_Y)t≥L

其中，d_j是0-1变量，t_j为非负整数，λ_j＝180,j＝1,2,......m。

作为优选的技术方案，所述水桶模型的构建方法如下：

假设有m个水桶并排放着，编号为1到m，每个水桶都足够高，不用考虑水是否会溢出，每个水桶的上方均有水以匀速q_j注入桶内，可以让密闭的桶内水平线匀速上升，桶底有一个漏水的开关阀，打开阀门后，需要等待启动时间l_j，桶内的水立刻以匀速S_j流出，S_j>q_j，非负且不全为0；

初始状态各个水桶均空，并准备有水开始注入，依次打开桶的阀门让水排出，每次只能打开一个桶，并且要求每次打开阀门，一定要把水排空，排空后立刻关上并开启下一桶的阀门，当关上最后一个桶的阀门时再次打开第一个桶的阀门，不失一般性，假定l₁不为0，每个桶的阀门打开与上一次打开的时间间隔称为周期，若干个周期后，整个系统会收敛到一个稳定状态，C会收敛到一个稳定值，记为C₀，在这个周期，所有桶的水都依次刚好放完，没有剩余也没有空放，并且周而复始；

在一个时间间隔C₀内，一个桶会积累q_jC₀的水，这些水排出需要的时间为q_jC₀/S_J及启动时间L_J，记Y_j＝q_j/S_j，如果各个桶都刚好放完，没有剩余或空放，C₀满足：

记,则

此为韦伯斯特的最小周期公式，q、S、l对应每个相位的关键车流量、饱和流量、损失时间，C₀描述的状态是在稳态的假设下，各个相位刚好放完车流且没有空放，如果把人行专用相位时间全部看成相位的损失时间的话，以上公式同样适用。

作为优选的技术方案，通过数学优化方法求解出相位周期C_p，求解得到的是平衡了冲突因素后的理论最小周期。

本发明与现有技术相比，具有如下优点和有益效果：

1、本发明利用建立考虑冲突因素的各车道流量、车头时距、人行过街长度的相位设计模型，在确定相位数的情况下，从众多的相位组合中自动筛选出符合该相位数的相位设计方案。

2、本发明是减化了相位设计中人为判断调整，利用模型进行自动从多种的相位组合情况中筛选合适交叉口的相位设计，减少了人力，也减少了对管理者的技术要求。

附图说明

图1是本发明相位设计方法的流程图；

图2为本发明实施例中的灯组相容关系图；

图3为本实施例中处理合流冲突时的放行示意图；

图4为本发明水桶模型的结构原理示意图。

具体实施方式

下面结合实施例及附图对本发明作进一步详细的描述，但本发明的实施方式不限于此。

实施例

如图1所示，本实施例基于整数规划模型的交通信号相位设计方法，包括下述步骤：

S1、计算备选相位矩阵，将备选相位矩阵A的每一列代表一个备选相z则：

其中α_ij＝0或1。

备选矩阵A的具体计算方法包括下述步骤：

S11、建立灯组相容关系图G_h，以每个灯组为节点，若灯组i，j是相容的，则存在一条从结点i到结点j的无向的边，由这些结点和边组成的无向图即为灯组相容关系图G_h；

连接相邻节点的边是无向边，是因为相容关系是对称的。显然，G_H以为连接矩阵，其中对灯组相容矩阵H的每个元素进行逻辑取反所得的矩阵，称为H的补。灯组i，j相容，表明两者允许同时放行。更进一步说，两者允许放在同一相位。即一个灯组集合能组成一个相位的必要条件，是集合内所有灯组两两相容。换句话说，一个相位对应G_H的一个完全子图。如图2所示的灯组相容关系图中，灯组1,2,4,7将可能组成一个相位。

相容关系值是一个布尔值，二值化无法衡量实际的冲突程度或相容程度，该程度将用冲突值来表示。

一个灯组集合能组成一个相位的必要条件是，该集合中所有灯组两两相容。在灯组相容关系图G_h中，一个灯组集合能组成一个相位的必要条件是，该集合中所有灯组两两相容；即：一个相位对应G_h中的一个完全子图，G_h的一个完全子图也可成为一个相位；并通过求解灯组相容关系图G_h的所有完全子图，得到所有相容灯组集合，作为原始备选相位矩阵，记该原始相位矩阵为A₀，然后筛选掉其中“不够好”的列，所述“不够好”的列是指冗余和两两相容但不是互相相容的列。

其中，求解一个图的所有完全子图，核心问题是图论中经典的最大团问题，属于NP完全问题，R中有现成的算法包igraph可以实现求解。

最大团问题具体为：

大团问题又称最大独立集问题，通俗来说是在一个无向图中找出一个阶数最大(节点最多)的完全子图，属于NP完全问题。确定性求解算法有：回溯法、分支界限法等。启发式求解算法有局部搜索启发式算法、智能搜索启发式算法、遗传算法、模拟退火算法、禁忌算法、神经网络法、改进的蚁群算法antMCP等。R语言的igraph包专门求解图论中的各种问题，最大团问题的求解算法已封装在该包中。

S12、除去冗余相位，在原始相位矩阵中，对比任意两列，按照冗余相位的定义，剔除冗余的相位列；一个只包含一个灯组的相位，在实际工程中可能会对时空利用造成浪费。因为在放行该灯组的同时，或许可以令其他与之相容的灯组也一起放行，将这样的相位称为冗余相位。

冗余相位的定义如下：

相位相对于是冗余的，当且仅当且U_i＝U_j，此时称为冗余相位。

表明中存在没有的灯组，允许和一起放行，这样肯定会优先选择用p_j来替代p_i。

S13、处理两股以上车流的合流冲突，除掉合流冲突中灯组集合是两两相容但非相互相容的相位列，所述两两相容是指在对于一个灯组集合，任意两个灯组允许同时放行；相互相容是指所有灯组允许同时放行；

所述合流冲突的定义如下：

当两股或以上来自不同进口的车流汇入同一出口，此时产生合流冲突，合流冲突是否相容，取决于合流的进口车道数是否不超过出口的车道数；

指定是n股合流车流，(m₁,m₂,....m_n)是每股车流对应的车道数，m₀是出口的车道数，定义

如图3所示，记4号灯组控制的东直行两股车流为A，5号灯控制的一股北右转车流为B，10号灯组控制的一股南左转车流为C。三股车流的目标出口为西出口。

按照合流冲突的原则，车流A和B相容，车流B和C相容，车流C和A相容，但是车流A、B、C不允许同时放行。

但是，在灯组相容关系图中，无法表现相互相容的关系，故此，需在中，剔除掉合流冲突中灯组集合是两两相容但非相互相容的相位列。

S14、计算备选相位集合；

S141、通过交叉口的路面渠化情况及相容经验表、冲突值经验表，计算灯组相容矩阵H及灯组冲突值矩阵Ω；其中相容经验表以及冲突值为行业内的公知常识，且该相容经验表和冲突值经验表可以根据实际情况进行修改，在此不再具体进行赘述。

所述灯组相容矩阵H具体为：

建立灯组相容矩阵，设灯组的编号为1-N，定义灯组相容矩阵H∈R^N×N为N×N的0-1矩阵：

其中，

最终可得

且由相容关系的对称性可知，灯组相容矩阵H为对称阵；

所述灯组冲突值矩阵Ω具体为：

建立灯组冲突值矩阵Ω，设灯组编号1～N，定义交叉口的灯组冲突值矩阵Ω∈R^N×N为N×N的矩阵

其中ω_ij∈[0,1)，为灯组i，j同时放行产生的冲突值，范围在[0,1)中

由冲突值关系的对称性可知，灯组冲突值矩阵Ω也是一个对称阵。

S142、利用合流冲突原则，以及根据现场情况人为判断，修正灯组相容矩阵H；

S143、由修正后的灯组相容矩阵H得到灯组相容关系图G_h，计算相容关系图的所有团，得到原始相位集合矩阵A₀；

S144、计算原始矩阵A₀每一列的冲突值ω_j，剔除冗余相位的列；

S145、利用合流冲突原则，在A₀中剔除灯组两两相容但不是相互相容的相位列，最后得到备选相位矩阵A。

S2、当灯组相容关系图G_h确定后，输入目标相位数，保证在一个相位周期C_P内，每个灯组至少出现一次，所述相位周期C_P是指从备选相位矩阵中选出的若干相位组成的相位周期；

所述目标相位数是通过下述方法确定的：

将相位数范围的问题转化为图论中的色数问题，通过得到的一个灯组的相容关系图G_H，以及相容关系图G_H的补图利用色数问题原理找出一个的分割，分割后的每个集合均对应G_H的一个完全子图的所有顶点，这实质便是的色数，进而便将求解合适相位数范围的问题转化为了图论中的色数问题。

S3、建立考虑冲突因素的各车道流量、车头时距、人行过街长度的相位设计模型，本发明采用水桶原理来设计相位模型：

如图4所示，考虑以下一个理想的水桶模型：有m个水桶并排放着，编号为1到m。每个水桶都足够高，不用考虑水是否会溢出。每个水桶的上方均有水以匀速q_j注入桶内，可以让密闭的桶内水平线匀速上升。桶底有一个漏水的开关阀，打开阀门后，需要等待启动时间l_j，桶内的水立刻以匀速S_j流出。S_j>q_j。非负且不全为0。

初始状态各个水桶均空，并准备有水开始注入。你需要依次打开桶的阀门让水排出。每次你只能打开一个桶。并且要求每次打开阀门，一定要把水排空，排空后要求立刻关上并开启下一桶的阀门。当关上最后一个桶的阀门时再次打开第一个桶的阀门。不失一般性，假定l₁不为0。每个桶的阀门打开与上一次打开的时间间隔称为周期C。若干个周期后，整个系统会收敛到一个稳定状态，C会收敛到一个稳定值，记为C₀。在这个周期，所有桶的水都依次刚好放完。没有剩余也没有空放，并且周而复始。

在一个时间间隔C₀内，一个桶会积累q_jC₀的水，这些水排出需要的时间为q_jC₀/S_J及启动时间L_J，记Y_j＝q_j/S_j，如果各个桶都刚好放完，没有剩余或空放，C₀满足：

记则

此为韦伯斯特的最小周期公式。q、S、l对应每个相位的关键车流量、饱和流量、损失时间。C₀描述的状态是在稳态(q均匀到达)的假设下，各个相位刚好放完车流且没有空放。注意，如果把人行专用相位时间全部看成相位的损失时间的话，以上公式同样适用。

因为相位其实灯组集合组成，灯组才是包含车道和人行的对象。可把q、S、y、l的概念从传统的相位级别推广到灯组级别。并有上面水桶模型作为启发，把一个水桶(相位)看成一堆小水桶(灯组)的物理参数q、S、y、l由其中的关键小水桶控制。相位设计的模型可描述成在系统达到满足每个灯组的放行需求，并尽量少空放的均衡状态下，包含冲突因子下的总周期最小。这样则可绕过相位周期C和放行需求f_i相互依赖的问题，并将C作为变量之一加入到模型中。

假设已知各个的车流量及饱和流量的比值为人行过街时取0，以及各个的人行需求时间取值由过街长度及人行速度计算得到，当为车道时取值为0，从而得到每个灯组的y值：

以及各个灯组的y^p值：

由此可得备选相位矩阵A中，每个备选相位的人行需求时间，记为

每个灯组，都有对应的损失时间l_i，当为人行过街灯组时；目标函数如下：

整个周期内满足每个灯组的人行需求：

把一个灯组看成一个水桶，根据水桶模型的原理，可知所有含灯组i的备选相位的时间和，应该满足：

其中

依然取d_j为0-1变量，λ_j＝180，由于每个含人行灯组的相位时间t_j必须满足该相位的人行需求时间

确定目标相位数：

记L＝(l₁,l₂,....l_N)^T，y＝(y₁,y₂,....y_N)^T矩阵A_y＝(y,y,....y)_m为N×m矩阵，综上，得到步骤S3中的相位设计模型为：

s.t At≥y^p

(A-A_Y)t≥L

其中，d_j是0-1变量，t_j为非负整数，λ_j＝180,j＝1,2,......m。

本实施例中，推荐使用mosek求解出相位周期C_p，求解得到的是平衡了冲突因素后的理论最小周期。该模型参照韦伯斯特最短周期的思想，结合整数规划，将最小周期作为参数加入到模型中，更符合实际工程的数据输入。求解出的相位周期C_p也充分体现了时空利用率最大化及其与冲突因素的平衡。也改进了每个含人行灯组的相位时间必须满足该相位的人行需求时间，而非仅是整个周期内对应的相位时间之和满足。上述模型也是相位设计核心部分的最终模型。

上述实施例为本发明较佳的实施方式，但本发明的实施方式并不受上述实施例的限制，其他的任何未背离本发明的精神实质与原理下所作的改变、修饰、替代、组合、简化，均应为等效的置换方式，都包含在本发明的保护范围之内。