基于改进Newman算法的动态控制子区划分
Dynamic control subdivision based on improved Newman algorithm
通讯作者:
收稿日期: 2018-04-25
Received: 2018-04-25
作者简介 About authors
田秀娟(1990—),女,讲师,从事智能交通系统及交通信号控制研究.orcid.org/0000-0001-7697-7481.E-mail:
为了优化现有控制子区划分方法,以区域协调控制为目标,提出基于改进的Newman社团快速划分的动态子区划分方法. 综合考虑路网中相邻交叉口之间的距离、交通流量、行程时间、车流离散特性、信号周期和路段交通流密度等因素,定量分析交叉口关联性;分别计算相邻交叉口的流量关联系数、信号周期关联系数和路段交通流密度关联系数,建立相邻交叉口的总关联度模型;对传统Newman算法进行改进,引入交叉口关联度,依据不同交通特性对区域路网进行动态子区划分;选取实际区域路网,进行模型验证分析. 结果表明:Newman算法子区划分结果不能随着交通特性的改变而改变;与之相比,所提出模型的子区划分结果更加细致,更加符合实际交通流特性,且可以依据不同时段交通特性实现动态子区划分,可以为信号控制方案制定提供良好基础.
关键词:
A dynamic subdivision method based on the improved Newman community fast division algorithm was proposed with the goal of regional coordinated control, in order to optimize the existing control subdivision method. The relevance of intersections was analyzed quantitatively by taking the factors including the distance between adjacent intersections, traffic volume, travel time, traffic flow discrete characteristic, signal cycle and road traffic flow density into consideration synthetically. The traffic flow correlation coefficient, signal cycle correlation coefficient and traffic flow density correlation coefficient of adjacent intersections were calculated respectively, and the total correlation degree model of adjacent intersections was established. The traditional Newman algorithm was improved and the correlation degree of intersections was brought in to divide the regional network into dynamic sub-regions according to different traffic characteristics. An actual regional road network was selected to verify the effect and performance of the proposed model. Results showed that control subdivision by Newman algorithm could not change with traffic characteristics. By contrast, the control subdivision result of the proposed model was more elaborate and more in line with the actual traffic flow characteristics. Moreover, dynamic subdivision could be realized according to the traffic characteristics of different time periods, which could provide a good basis for the formulation of the signal control scheme.
Keywords:
本文引用格式
田秀娟, 于德新, 周户星, 邢雪, 王世广.
TIAN Xiu-juan, YU De-xin, ZHOU Hu-xing, XING Xue, WANG Shi-guang.
作为城市交通控制系统的协调控制功能单元,交通信号控制子区划分结果直接影响区域协调控制策略的制定和控制效果. 交通控制子区划分的基本思路是以路段和与之相连的信号交叉口的静态空间几何特征和动态交通流特性为依据,依托关联性分析、最优化理论和先进的计算机技术,将控制区域划分为若干个合理的控制子区,为子区内和子区间协调控制方案设计提供基础.
针对子区划分,国内外进行了大量研究,大致集中在交叉口合并/关联度指标计算和子区划分方法2个方面. Walinchus[1]首次提出交通控制子区概念,指出在划分子区时,须同时考虑道路物理特性、交叉口饱和度以及相位差误差等因素的影响,为后续子区划分方法研究奠定了基础. Yagoda等[2]对关联性进行分析,将路段交通流量与路段长度的比值作为衡量2个交叉口之间关联性的指标. Pinnell等[3]考虑上游交叉口交通流量、路段长度和上游车辆到达规律对于关联性的影响. Moore等[4]以交叉口流量比为特征属性,运用聚类分析方法,对控制子区进行划分. 李瑞敏等[5]综合考虑交叉口间距、交通流离散特性、主干路交通构成、交通流量和信号周期的影响,分别计算各因素影响系数,最终建立了协调系数模糊推理模型. 卢凯等[6]考虑路段排队车辆、交通流量及周期时长等,分别对相邻两交叉口关联度与多交叉口组合关联度模型进行研究. 在划分算法研究方面,杨庆芳等[7]提出周期子区和相位差/绿信比子区,对动态子区划分方法进行研究. 尹洪英等[8]考虑交叉口位置、饱和度和信号周期的影响,提出基于谱聚类算法的城市路网动态分区方法. 以流量、距离和信号周期为原则,以协调控制优化目标为基础,陈宁宁[9]根据路段关联度指标,提出从大到小遍历路网内所有路段的搜索算法,对子区进行初始划分,进而考虑交通状态变化与控制效果,构建子区动态调整流程. Zhou等[10]针对城市异构交通网络,提出动态子区划分方法,首先建立关联度模型,定量衡量相邻交叉口之间的关联性,然后提出模块化的子区划分方法. 为了弥补传统控制子区划分方法对于交通网络拓扑结构复杂特性考虑不充分的问题,王力等[11]借助复杂网络理论,以社区模块度为指标,基于凝聚社区发现算法,对控制子区优化方法进行研究. 针对子区划分过程中可能存在的维数灾难问题,卢凯等[12]结合降维处理与遗传算法,提出子区快速划分方法. Shen等[13]分析路段距离、交通流密度和信号周期对交叉口关联性的影响,建立基于模糊算法的子区划分方法. 徐建闽等[14]针对交叉口不同状态,提出基于不同饱和度的路网动态划分方法,建立各子区内交叉口之间的关联度和相似度模型,并利用谱图理论对路段和交叉口进行动态划分.
总结国内外研究现状,不难发现,现有子区划分方法大体上是依据交通特征相似性,借助聚类或搜索方法将相似性高的路段和交叉口划分至同一个子区;未充分考虑交通网络拓扑结构,划分指标大多仍是建立在距离、流量和周期的基础上,或是由交通管理者根据交叉口间距及交通流特性粗略划分,难以保证划分的客观性和统一性. 因此,动态子区划分指标和划分方法皆有改进空间.
为了弥补现有研究的不足,提出基于改进的Newman社团快速划分的动态子区划分方法. 综合考虑路网中相邻交叉口之间的距离、交通流量、车流离散特性、行程时间、信号周期和路段交通流密度等因素,定量分析交叉口关联性,建立关联度模型. 对传统Newman算法进行改进,引入交叉口关联度,依据不同交通特性对区域路网进行动态子区划分.
1. 交叉口关联性分析
相邻交叉口关联性的主要影响因素为交叉口间距、路段交通流量和信号配时参数. 交叉口间距为静态影响因素,对交叉口关联性的影响程度不变;路段交通流量和信号配时参数属于动态影响因素,对交叉口关联性的影响程度会随着交叉口实际交通特性动态改变. 综合考虑路网中相邻交叉口之间的距离、交通流量、行程时间、车流离散特性、信号周期和路段交通流密度等因素,对交叉口关联性进行定量分析,分别计算相邻交叉口的流量关联系数、信号周期关联系数和路段交通流密度关联系数,进而得到相邻交叉口的总关联度模型,为子区划分提供数据基础.
1.1. 流量关联系数
式中:
经典的Whitson关联度模型[19]考虑交叉口之间行程时间和交通流量,综合反映关联度与距离、流量之间的耦合关系,但是没有考虑车流离散性的影响. 此外,相邻交叉口之间路段上的交通流通常是双向的,因此,在计算交叉口关联度时,还应该考虑双向关联度. 考虑交通流的双向性和离散特性,引入Robertson模型中的离散系数,对Whitson关联度模型进行改进:
式中:
交叉口总流量关联度
1.2. 信号周期关联系数
为了保证信号协调控制效果,增加交叉口的通行效率,同一控制子区内相邻交叉口应尽量设置相同的周期时长和稳定的相位差. 当对相邻交叉口实施信号协调控制时,若交叉口之间周期时长相差过大,则周期时长小的交叉口的车辆延误将会增加;若交叉口之间周期时长相差较小,则容易达到较好的控制效果. 因此,在进行子区划分时,应考虑交叉口周期时长的影响.
在对相邻交叉口实施信号协调控制时,交叉口之间的信号周期须满足相等或者成倍条件. 基于现有研究[20],定义相邻交叉口的信号周期关联系数表达式为
式中:
1.3. 路段交通流密度关联系数
除了考虑交叉口间距、关联路段交通流量、信号周期时长外,为了使具有相似交通状态的路段和交叉口尽可能划分至同一个控制子区,在子区划分时,还应该考虑路段的交通流密度. 路段的交通流密度可以更加直观地体现路段的拥挤程度,参照现有研究,建立路段密度关联系数模型[20]:
式中:
综上,综合考虑流量关联系数、信号周期关联系数和路段交通流密度关联系数,建立相邻交叉口总关联度模型:
2. 基于改进Newman算法的子区划分
运用图论的思想,将道路网络中的交叉口抽象为点,相邻交叉口之间的路段抽象为边,则区域路网将被抽象为网络拓扑结构图. 道路网络中的交通流周期特性明显,在不同时段,波动性较明显,因此,与其他网络结构不同,道路交通网络拓扑结构图中各个元素之间的关系并不是简单的布尔关系. 考虑到路网中相邻交叉口的关联性,在节点
2.1. Newman快速划分算法
1)选取网络,抽象为拓扑结构图. 假设共含有
2)定义辅助矩阵
3)分别初始化矩阵
式中:
4)对有边相连的节点对进行合并,计算更新模块度增量:
5)选择模块度增量最大的节点,进行合并,更新元素
6)转至步骤4)继续执行,直至整个网络合并为1个社团,算法结束.
在Newman算法执行过程中,最多须进行
2.2. Newman算法改进
为了使Newman算法更加适用于有权网络划分,基于现有研究[24],对传统Newman算法进行改进. 首先,对模块度计算公式进行改进. 假定网络中共含有
式中:Tre为矩阵c对角线上元素之和,表示社团内部的边权占所有边权的比例.
改进算法考虑了网络节点之间的关联性,而边权代表节点之间的关联性,因此对矩阵
式中:
在社团合并过程中,须重新计算
2.3. 动态子区划分流程
众多研究表明,道路交通网络是典型的复杂网络,结合复杂网络中的社团划分算法进行动态控制子区划分具有可行性和优越性. 依据改进的Newman算法进行交通控制子区划分,步骤如下.
1)对给定的交通网络进行简化,将交叉口简化为节点,交叉口之间的路段简化为边.
2)对简化后的网络图中的节点和边进行标号.
3)采集和统计网络中节点与边的交通信息,代入关联度计算模型,得到相邻交叉口之间的关联度.
4)对交通网络进行初始划分,每个节点为1个独立的社团.
5)定义并初始化辅助矩阵
6)对有边相连的节点对进行合并,计算更新模块度增量,如式(10)所示.
7)选择模块度增量最大的节点,进行合并,更新元素
8)转至步骤6)继续执行,直至整个网络合并为1个社团.
9)算法结束,输出控制子区划分树状图.
10)选取模块度最大时的划分结果作为信号控制子区划分的最优结果.
3. 模型验证
图 1
图 2
3.1. 关联度计算
以网络开放数据为基础,结合百度地图,可以得到各交叉之间的距离和车道数目;选取上午8:00~9:00交通检测数据进行模型验证分析. 首先,统计交通流和行程时间等信息,然后分别计算各关联交叉口的流量关联系数、信号周期关联系数和路段交通流密度关联系数,进而得到相邻交叉口之间的总关联度,如表1所示.
表 1 交叉口总关联度
Tab.1
i↔j | Ii↔j | i↔j | Ii↔j | |
1↔2 | 0.012 | 9↔10 | 0.126 | |
1↔5 | 0.002 | 10↔11 | 0.055 | |
2↔3 | 0.009 | 10↔17 | 0.037 | |
3↔4 | 0.093 | 11↔12 | 0.004 | |
4↔5 | 0.011 | 11↔16 | 0.076 | |
4↔7 | 0.005 | 12↔15 | 0.022 | |
5↔6 | 0.020 | 14↔15 | 0.030 | |
6↔7 | 0.046 | 14↔19 | 0.030 | |
6↔13 | 0.042 | 15↔16 | 0.081 | |
7↔8 | 0.007 | 16↔17 | 0.078 | |
7↔12 | 0.053 | 16↔19 | 0.005 | |
8↔9 | 0.014 | 18↔19 | 0.011 | |
8↔11 | 0.008 | — | — |
3.2. 子区划分结果分析
图 3
图 3 Newman算法交通子区划分结果
Fig.3 Traffic subdivision results based on Newman algorithm
图 4
图 4 Newman算法子区划分模块度
Fig.4 Modular values of subdivision results based on Newman algorithm
图 5
图 5 改进Newman算法交通子区划分结果
Fig.5 Traffic subdivision results based on improved Newman algorithm
图 6
图 6 改进Newman算法子区划分模块度
Fig.6 Modular values of subdivision results based on improved Newman algorithm
由图4可知,在基于Newman算法的子区划分中,当子区合并至编号34时,模块度达到最大值0.433 2,此时子区划分结果最优,验证区域路网共被划分为4个控制子区. 对应图3的子区划分树状图,可知,交叉口1、2、3、4、5、6、13为控制子区1;交叉口7、12为控制子区2;交叉口8、9、10、11、16、17为控制子区3;交叉口14、15、18、19为控制子区4. 由图6可知,在基于改进Newman算法子区划分中,当子区合并至编号33时,模块度达到最大值0.540 1,此时子区划分结果最优,验证路网被划分为5个控制子区. 由图5的子区划分树状图可知,此时,交叉口8、9、10,交叉口11、15、16、17,交叉口14、18、19,交叉口1、2、3、4,交叉口5、6、7、12、13分别属于一个控制子区.
为了更加直观地展示和对比2种算法对于区域路网子区划分的情况,分别绘制子区组成图示. 如图7所示为基于Newman算法划分得到的交通控制子区,如图8所示为基于改进的Newman算法划分得到的交通控制子区. 对比图7、8中2种算法的控制子区划分结果,可知,所提出的改进算法对于控制子区的划分更细致,更符合实际的交通流特性,且可以根据不同时段交通特性对子区进行动态划分. 这是因为在子区划分过程中,Newman算法并未考虑交叉口之间的关联特性,交叉口之间的距离、流量等因素对于子区的划分结果的影响,仅以交叉口之间的关联矩阵作为模型输入;而对于某给定路网来说,关联矩阵是固定的,因此,子区划分结果也是固定的,并不随着交通特性的改变而改变. 而本研究改进的Newman算法充分将交通流量、交叉口之间的距离、行程时间、信号周期、路段交通流密度的影响考虑在内,引入了交叉口之间的关联度,划分结果会随着交通特性的改变而改变,可以实现对控制子区的动态划分. 对比结果验证了本研究所提出算法的有效性.
图 7
图 7 Newman算法交通控制子区组成
Fig.7 Traffic control sub-region composition based on Newman algorithm
图 8
图 8 改进Newman算法交通控制子区组成
Fig.8 Traffic control sub-region composition based on improved Newman algorithm
4. 结 语
以区域协调控制为目标,基于改进的Newman社团快速划分算法,提出新的动态子区划分方法. 验证结果表明,对于某给定路网,基于Newman算法的子区划分结果不随交通特性改变. 与Newman算法相比,本研究所提出的模型能依据实际交通特性,充分考虑交叉口之间的关联性,对控制子区实现动态划分,且划分结果更加细致,更加符合不同时段的交通流特性,为信号控制方案的制定提供良好的基础. 在下一步研究中,将进行控制子区及子区之间的协调控制方法研究.
参考文献
Real-time network decomposition and subnetwork interfacing
[J].
Subdivision of signal systems into control areas
[J].
Area wide multilevel traffic control systems
[J].DOI:10.1016/S1474-6670(17)67310-5 [本文引用: 1]
Statistical designation of traffic control subareas
[J].DOI:10.1061/(ASCE)0733-947X(1985)111:3(208) [本文引用: 1]
交通信号控制子区模糊动态划分方法研究
[J].
Research on traffic control sub-area fuzzy automatic division method
[J].
基于关联度分析的协调控制子区划分方法
[J].
Division method of coordinated control subareas based on correlation degree analysis
[J].
基于谱聚类算法的城市路网动态分区研究
[J].DOI:10.3963/j.issn.1674-4861.2010.01.004 [本文引用: 1]
City transportation road network dynamic zoning based on spectral clustering algorithm
[J].DOI:10.3963/j.issn.1674-4861.2010.01.004 [本文引用: 1]
基于社区发现的交通控制子区优化方法研究
[J].DOI:10.3969/j.issn.1009-6744.2012.06.025 [本文引用: 2]
Sub-control-area division optimization of traffic network based on community discovery
[J].DOI:10.3969/j.issn.1009-6744.2012.06.025 [本文引用: 2]
协调控制子区快速动态划分方法研究
[J].DOI:10.3969/j.issn.1003-8930.2012.02.025 [本文引用: 1]
Research on fast dynamic division method of coordinated control subarea
[J].DOI:10.3969/j.issn.1003-8930.2012.02.025 [本文引用: 1]
A dynamic signal coordination control method for urban arterial roads and its application
[J].
考虑交叉口不同饱和度的路网动态分区方法
[J].
Dynamic network partitioning method based on intersections with different degree of saturation
[J].
A theory of the diffusion of traffic platoons
[J].
" TRANSYT”method for area traffic control
[J].
主干道动态协调控制技术
[J].
Dynamic coordination control technique for trunk road
[J].
Finding and evaluating community structure in networks
[J].DOI:10.1103/PhysRevE.69.026113 [本文引用: 1]
Fast algorithm for detecting community structure in networks
[J].DOI:10.1103/PhysRevE.69.066133 [本文引用: 1]
Community structure in social and biological networks
[J].DOI:10.1073/pnas.122653799 [本文引用: 1]
/
〈 |
|
〉 |
