浙江大学学报(工学版), 2019, 53(5): 950-956 doi: 10.3785/j.issn.1008-973X.2019.05.016

交通工程

基于改进Newman算法的动态控制子区划分

田秀娟,, 于德新, 周户星,, 邢雪, 王世广

Dynamic control subdivision based on improved Newman algorithm

TIAN Xiu-juan,, YU De-xin, ZHOU Hu-xing,, XING Xue, WANG Shi-guang

通讯作者: 周户星,男,讲师. orcid.org/0000-0002-5979-3741. E-mail: zhouhx@jlu.edu.cn

收稿日期: 2018-04-25  

Received: 2018-04-25  

作者简介 About authors

田秀娟(1990—),女,讲师,从事智能交通系统及交通信号控制研究.orcid.org/0000-0001-7697-7481.E-mail:jidatianxj@126.com , E-mail:jidatianxj@126.com

摘要

为了优化现有控制子区划分方法,以区域协调控制为目标,提出基于改进的Newman社团快速划分的动态子区划分方法. 综合考虑路网中相邻交叉口之间的距离、交通流量、行程时间、车流离散特性、信号周期和路段交通流密度等因素,定量分析交叉口关联性;分别计算相邻交叉口的流量关联系数、信号周期关联系数和路段交通流密度关联系数,建立相邻交叉口的总关联度模型;对传统Newman算法进行改进,引入交叉口关联度,依据不同交通特性对区域路网进行动态子区划分;选取实际区域路网,进行模型验证分析. 结果表明:Newman算法子区划分结果不能随着交通特性的改变而改变;与之相比,所提出模型的子区划分结果更加细致,更加符合实际交通流特性,且可以依据不同时段交通特性实现动态子区划分,可以为信号控制方案制定提供良好基础.

关键词: 信号控制 ; 改进Newman算法 ; 子区划分 ; 交叉口关联性 ; 区域控制

Abstract

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: signal control ; improved Newman algorithm ; subdivision ; relevance of intersections ; regional control

PDF (899KB) 元数据 多维度评价 相关文章 导出 EndNote| Ris| Bibtex  收藏本文

本文引用格式

田秀娟, 于德新, 周户星, 邢雪, 王世广. 基于改进Newman算法的动态控制子区划分. 浙江大学学报(工学版)[J], 2019, 53(5): 950-956 doi:10.3785/j.issn.1008-973X.2019.05.016

TIAN Xiu-juan, YU De-xin, ZHOU Hu-xing, XING Xue, WANG Shi-guang. Dynamic control subdivision based on improved Newman algorithm. Journal of Zhejiang University(Engineering Science)[J], 2019, 53(5): 950-956 doi:10.3785/j.issn.1008-973X.2019.05.016

作为城市交通控制系统的协调控制功能单元,交通信号控制子区划分结果直接影响区域协调控制策略的制定和控制效果. 交通控制子区划分的基本思路是以路段和与之相连的信号交叉口的静态空间几何特征和动态交通流特性为依据,依托关联性分析、最优化理论和先进的计算机技术,将控制区域划分为若干个合理的控制子区,为子区内和子区间协调控制方案设计提供基础.

针对子区划分,国内外进行了大量研究,大致集中在交叉口合并/关联度指标计算和子区划分方法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. 流量关联系数

车队从上游交叉口驶出后,在到达下游交叉口之前,会发生离散现象. 在计算相邻交叉口之间的关联度时,要考虑交通流的离散特性. 对于交通流离散模型的研究较多,Pacey模型[15-16]和Robertson模型[17]最为常用. 与Pacey模型相比,Robertson模型所需参数较少,计算简单,能够较准确地描述车流的离散现象,因此,应用更为广泛. 在信号控制系统TRANSYT和SCOOT中,Robertson模型被用来计算下游交叉口的车辆到达情况. 其中,离散系数的表达式为

$F = {1/}({{1 + aT}}).$

式中: $a$ 为常数, $T$ 为2个研究路段断面之间车辆平均行程时间的0.8倍. 研究表明, $a$=0.10~0.15,较符合我国实际交通流的特性[18].

经典的Whitson关联度模型[19]考虑交叉口之间行程时间和交通流量,综合反映关联度与距离、流量之间的耦合关系,但是没有考虑车流离散性的影响. 此外,相邻交叉口之间路段上的交通流通常是双向的,因此,在计算交叉口关联度时,还应该考虑双向关联度. 考虑交通流的双向性和离散特性,引入Robertson模型中的离散系数,对Whitson关联度模型进行改进:

$I_{q\left( {i \to j} \right)}^{} = \frac{{0.5}}{{1 + a{T_{i \to j}}}}\left( {\frac{{{n_{i \to j}}q_{\max }^{i \to j}}}{{\sum {{q_{i \to j}}} }} - 1} \right).$

式中: $I_{q\left( {i \to j} \right)}^{}$ 为交叉口 $i$$j$ 之间的流量关联度; ${T_{i \to j}}$ 为车辆从交叉口 $i$ 行驶至交叉口 $j$ 的行程时间 ${t_{i \to j}}$ 的0.8倍, ${t_{i \to j}}$等于交叉口间距 ${L_{i \to j}}$ 与车辆平均速度 ${V_{i \to j}}$ 的比值; ${n_{i \to j}}$ 为上游交叉口 $i$ 车流驶入下游交叉口 $j$ 的分支数,对于典型十字交叉口而言, ${n_{i \to j}}{{ = }}3$$q_{\max }^{i \to j}$ 为交叉口 $i$ 驶向交叉口 $j$ 的最大进口道交通流量; $\sum {{q_{i \to j}}} $ 为交叉口 $i$ 驶向交叉口 $j$ 的进口道交通总流量. 同样地,可以求出反向关联度 $I_{q\left( {j \to i} \right)}^{}$.

交叉口总流量关联度 $I_{q\left( {i \leftrightarrow j} \right)}^{}$ 选取 ${I_{q\left( {i \to j} \right)}}$${I_{q\left( {j \to i} \right)}}$ 两者中的较大值:

$I_{q\left( {i \leftrightarrow j} \right)}^{} = \max \;\left( {{I_{q\left( {i \to j} \right)}},\;{I_{q\left( {j \to i} \right)}}} \right).$

1.2. 信号周期关联系数

为了保证信号协调控制效果,增加交叉口的通行效率,同一控制子区内相邻交叉口应尽量设置相同的周期时长和稳定的相位差. 当对相邻交叉口实施信号协调控制时,若交叉口之间周期时长相差过大,则周期时长小的交叉口的车辆延误将会增加;若交叉口之间周期时长相差较小,则容易达到较好的控制效果. 因此,在进行子区划分时,应考虑交叉口周期时长的影响.

在对相邻交叉口实施信号协调控制时,交叉口之间的信号周期须满足相等或者成倍条件. 基于现有研究[20],定义相邻交叉口的信号周期关联系数表达式为

${I_{C\left( {i, j} \right)}} = \frac{2}{{R - 1}} \min\;\left( {\left| { {\frac{{R + 1}}{2} - \frac{{\max\;\left( {{C_i}, {C_j}} \right)}}{{\min\;\left( {{C_i}, {C_j}} \right)}}} } \right|,\; 0.5} \right).$

式中: ${I_{C\left( {i, j} \right)}}$ 为信号周期关联系数,IC (i, j) $\in $ [0,1.0]; ${C_i}$${C_j}$ 分别为交叉口 $i$$j$ 的信号周期; $R$ 为相邻交叉口信号控制周期比值的最大可能值,通常为2.

1.3. 路段交通流密度关联系数

除了考虑交叉口间距、关联路段交通流量、信号周期时长外,为了使具有相似交通状态的路段和交叉口尽可能划分至同一个控制子区,在子区划分时,还应该考虑路段的交通流密度. 路段的交通流密度可以更加直观地体现路段的拥挤程度,参照现有研究,建立路段密度关联系数模型[20]

${I_{\rho \left( {i \leftrightarrow j} \right)}} = \min\;\left(\max \;\left(\frac{{{\rho _{\left( {i \to j} \right)}}}}{{{\rho _{{\rm{s}}\left( {i \to j} \right)}}}},\;\frac{{{\rho _{\left( {j \to i} \right)}}}}{{{\rho _{{\rm{s}}\left( {j \to i} \right)}}}}\right),\;1\right),$

${\rho _{\left( {i \to j} \right)}}{{ = }}{{\sum {{q_{i \to j}}} }}/({{{N_{i \to j}} {L_{i \to j}}}}).$

式中: ${I_{\rho \left( {i \leftrightarrow j} \right)}}$ 为交叉口 $i$$j$ 之间的路段交通流密度关联系数, $I_{\rho(i \leftrightarrow j)}$ $\in $ [0,1.0]; ${\rho _{\left( {i \to j} \right)}}$ 为交叉口 $i$$j$ 方向上的路段交通流密度; ${\rho _{{\rm{s}}\left( {i \to j} \right)}}$ 为饱和状态下交叉口 $i$$j$ 方向上的路段交通流密度; ${N_{i \to j}}$ 为相应方向路段上的车道数.

综上,综合考虑流量关联系数、信号周期关联系数和路段交通流密度关联系数,建立相邻交叉口总关联度模型:

${I_{i \leftrightarrow j}} = I_{q\left( {i \leftrightarrow j} \right)}^{} {I_{C\left( {i, j} \right)}} {I_{\rho \left( {i \leftrightarrow j} \right)}}.$

2. 基于改进Newman算法的子区划分

运用图论的思想,将道路网络中的交叉口抽象为点,相邻交叉口之间的路段抽象为边,则区域路网将被抽象为网络拓扑结构图. 道路网络中的交通流周期特性明显,在不同时段,波动性较明显,因此,与其他网络结构不同,道路交通网络拓扑结构图中各个元素之间的关系并不是简单的布尔关系. 考虑到路网中相邻交叉口的关联性,在节点 $i$$j$ 之间引入交叉口关联度 ${I_{i \leftrightarrow j}}$ 作为连接边的权值,对经典的Newman社团快速划分算法进行改进,提出新的子区划分算法.

2.1. Newman快速划分算法

Newman快速划分算法是Newman等[21-22]基于GN算法[23]提出的社团快速划分聚合算法. 该算法基于贪婪算法的思想,在划分初期,将社团中的每个节点看作单独的社团,然后按照一定的规则对各节点进行合并,进而实现社团结构划分. Newman划分算法的基本思路是沿着社团合并前后模块度增量 $\Delta Q$ 增大最多的方向进行,当所有节点合并为一个社团时,算法终止,输出可以直观反映节点连接关系的树状图;在树状图上任意画一条横线,即可得到相应的划分结果. 当模块度 $Q$ 取最大值时,社团划分结果达到最优,可作为最终结果. 算法的具体步骤如下.

1)选取网络,抽象为拓扑结构图. 假设共含有 $n$ 个节点,则网络初始被划分为 $n$ 个社团,每个节点即为1个社团.

2)定义辅助矩阵 ${{E}}$ 和一维数组 ${{A}}$,其中,矩阵 ${{E}}$ 的行数和列数代表网络节点数,数组 $A$ 中元素的个数等于网络节点数.

3)分别初始化矩阵 ${{E}}$ 和数据 ${{A}}$ 中的所有元素 ${e_{ij}}$${a_i}$

${e_{ij}} = \left\{ {\begin{array}{*{20}{l}} {{1}/({{2m}}),\;\;{\text{节点}}i{\text{、}}j}{\text{之间有边直接相连;}}\\ {0,}\;\;\;\;\qquad{\text{其他,}} \end{array}} \right.$

${a_i}{{ = }}{{{k_i}}}/({{2m}}).$

式中: ${k_i}$ 为节点 $i$ 的度, $m$ 为网络中连接节点的边的总数.

4)对有边相连的节点对进行合并,计算更新模块度增量:

$\Delta Q = {e_{ij}} + {e_{ji}} - 2{a_i}{a_j} = 2\left( {{e_{ij}} - {a_i}{a_j}} \right).$

5)选择模块度增量最大的节点,进行合并,更新元素 ${e_{ij}}$.

6)转至步骤4)继续执行,直至整个网络合并为1个社团,算法结束.

在Newman算法执行过程中,最多须进行 $n - 1$ 次社团合并. 在算法结束后输出社团划分树状图,当模块度取得最大值时对应的社团划分结果,即为最优社团划分结果.

2.2. Newman算法改进

为了使Newman算法更加适用于有权网络划分,基于现有研究[24],对传统Newman算法进行改进. 首先,对模块度计算公式进行改进. 假定网络中共含有 $n$ 个社团,记作 $\left( {{c_1}, {c_2}, \cdots, {c_n}} \right)$,记 $n$ 维对称矩阵 ${{c}} = \left[ {{c_{ij}}} \right]$,矩阵元素 ${c_{ij}}$ 等于社团 $i$$j$ 的边权和,表征社团内部边权占网络边权比; ${v_i} = $ $\sum\nolimits_{j}c_{ij}$ 为矩阵 ${{c}}$ 每行元素之和,表征社团 $i$ 内部节点与外部节点连接边权占网络边权比; $\left\| {{{{c}}^2}} \right\|$ 为矩阵 ${{{c}}^2}$ 所有元素之和. 可以得到改进的模块度:

${Q^{\rm{w}}} = \sum\limits_i {\left( {{c_{ii}} - v_i^2} \right)} = {\rm{Tre}} - \left\| {{{{c}}^2}} \right\|.$

式中:Tre为矩阵c对角线上元素之和,表示社团内部的边权占所有边权的比例.

改进算法考虑了网络节点之间的关联性,而边权代表节点之间的关联性,因此对矩阵 ${{E}}$ 中的元素 ${e_{ij}}$ 进行改进:

${e_{ij}} \!=\! \left\{ {\begin{array}{*{20}{l}} {{{{R_{ij}}}}/{{\sum\limits_{i, j} {{R_{ij}}} }},\;{\text{节点}}i{\text{与节点}}j{\text{有边直接相连;}}}\\ {0,}\;\qquad\quad\;\;{\text{其他.}} \end{array}} \right.$

式中: ${R_{ij}}$ 为连接节点 $i$$j$ 的边的权值. ${a_i}$ 的表达式为

${a_i} = {{\sum\limits_j {{e_{ij}}} }}{\Big/}{{\sum\limits_{i, j} {{R_{ij}}} }}.$

在社团合并过程中,须重新计算 $\Delta Q$;合并原则与Newman算法一致,都是沿着 $Q$ 增大最多或者减少最小的方向. 在每一次合并之后都须重新计算 ${e_{ij}}$${a_i}$,并且把与社团 $i$$j$ 有关的行与列相加;对社团进行不断合并,直至所有节点合并为1个社团,算法结束. 输出社团划分树状图,选取 $Q$ 取得最大值时的社团划分作为最终划分结果.

2.3. 动态子区划分流程

众多研究表明,道路交通网络是典型的复杂网络,结合复杂网络中的社团划分算法进行动态控制子区划分具有可行性和优越性. 依据改进的Newman算法进行交通控制子区划分,步骤如下.

1)对给定的交通网络进行简化,将交叉口简化为节点,交叉口之间的路段简化为边.

2)对简化后的网络图中的节点和边进行标号.

3)采集和统计网络中节点与边的交通信息,代入关联度计算模型,得到相邻交叉口之间的关联度.

4)对交通网络进行初始划分,每个节点为1个独立的社团.

5)定义并初始化辅助矩阵 ${{E}}$ 和数组 $A$ 中的所有元素 ${e_{ij}}$${a_i}$

${e_{ij}} \!=\! \left\{ {\begin{array}{*{20}{l}} \!\!\!\!{{{{I_{i \leftrightarrow \!j}}}}\!/\!{{\sum\limits_{i, j} {{I_{i \leftrightarrow \!j}}} }},\;\!{\text{节点}}i{\text{与节点}}j{\text{有边直接相连;}}}\\ \!\!\!\!{0,}\!\qquad\qquad\;{\text{其他,}} \end{array}} \right.$

${a_i} = {{\sum\limits_j {{e_{ij}}} }}{\Big/}{{\sum\limits_{i, j} {{I_{i \leftrightarrow j}}} }}.$

6)对有边相连的节点对进行合并,计算更新模块度增量,如式(10)所示.

7)选择模块度增量最大的节点,进行合并,更新元素 ${e_{ij}}$.

8)转至步骤6)继续执行,直至整个网络合并为1个社团.

9)算法结束,输出控制子区划分树状图.

10)选取模块度最大时的划分结果作为信号控制子区划分的最优结果.

3. 模型验证

为了验证所提出模型的有效性,选择部分区域路网进行模型验证. 相关道路信息数据和交通流数据均来源于OpenITS网络开放数据路网选取安徽省宣城市水阳江大道内的部分路网,包括昭亭路、双塔路、宛陵路、西林路、叠嶂西路、梅溪路、梅园路等部分路段. 选取的部分路网共包含19个信号控制交叉口,46条路段,如图1所示. 为了直观性和子区划分的方便性,对图1的路网进行简化,将信号控制交叉口抽象为网络节点,将路段抽象为网络的边,分别对路网中的节点和边进行编号,得到路网简化图,如图2所示.

图 1

图 1   子区划分验证区域路网

Fig.1   Regional road network for subdivision validation


图 2

图 2   区域路网简化图

Fig.2   Simplified diagram for regional road network


3.1. 关联度计算

以网络开放数据为基础,结合百度地图,可以得到各交叉之间的距离和车道数目;选取上午8:00~9:00交通检测数据进行模型验证分析. 首先,统计交通流和行程时间等信息,然后分别计算各关联交叉口的流量关联系数、信号周期关联系数和路段交通流密度关联系数,进而得到相邻交叉口之间的总关联度,如表1所示.

表 1   交叉口总关联度

Tab.1  Total correlation degree model for intersections

ij Iij ij Iij
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

新窗口打开| 下载CSV


3.2. 子区划分结果分析

为了验证所提出方法的有效性,分别采用经典的Newman社团快速划分算法[11]和本研究提出的改进Newman算法进行区域路网子区划分. 1)不考虑路网节点之间的权重,以交叉口之间的关联矩阵作为模型输入,运用MATLAB编程,基于Newman算法对如图2所示的区域路网进行控制子区划分,划分结果如图3所示. 图中,k为交叉口个数. 在算法执行过程中,每一合并过程对应的模块度如图4所示. 2)考虑到交叉口之间的关联性,引入交叉口的关联度,采用本研究改进的Newman算法对验证路网进行子区划分,划分结果如图5所示;子区合并过程中模块度变化曲线如图6所示.

图 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算法划分得到的交通控制子区. 对比图78中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算法相比,本研究所提出的模型能依据实际交通特性,充分考虑交叉口之间的关联性,对控制子区实现动态划分,且划分结果更加细致,更加符合不同时段的交通流特性,为信号控制方案的制定提供良好的基础. 在下一步研究中,将进行控制子区及子区之间的协调控制方法研究.

参考文献

WALINCHUS R J

Real-time network decomposition and subnetwork interfacing

[J]. Highway Research Record, 1971, 366: 20- 28

[本文引用: 1]

YAGODA N H, PRINCIPE E H, VICK C E, et al

Subdivision of signal systems into control areas

[J]. Traffic Engineering, 1973, 43 (12): 42- 45

[本文引用: 1]

PINNELL C, WILSHIRE M R L

Area wide multilevel traffic control systems

[J]. IFAC Proceedings Volumes, 1976, 9 (4): 339- 348

DOI:10.1016/S1474-6670(17)67310-5      [本文引用: 1]

MOORE J E, JOVANIS P P

Statistical designation of traffic control subareas

[J]. Journal of Transportation Engineering, 1985, 111 (3): 208- 223

DOI:10.1061/(ASCE)0733-947X(1985)111:3(208)      [本文引用: 1]

李瑞敏, 陆化普, 史其信

交通信号控制子区模糊动态划分方法研究

[J]. 武汉理工大学学报: 交通科学与工程版, 2008, 32 (3): 381- 384

[本文引用: 1]

LI Rui-min, LU Hua-pu, SHI Qi-xin

Research on traffic control sub-area fuzzy automatic division method

[J]. Journal of Wuhan University of Technology: Transportation Science and Engineering, 2008, 32 (3): 381- 384

[本文引用: 1]

卢凯, 徐建闽, 李轶舜

基于关联度分析的协调控制子区划分方法

[J]. 华南理工大学学报: 自然科学版, 2009, 37 (7): 6- 9

[本文引用: 1]

LU Kai, XU Jian-min, LI Yi-shun

Division method of coordinated control subareas based on correlation degree analysis

[J]. Journal of South China University of Technology: Natural Science Edition, 2009, 37 (7): 6- 9

[本文引用: 1]

杨庆芳, 陈林. 交通控制子区动态划分方法[J]. 吉林大学学报: 工学版, 2006, 36(增2): 145–148.

[本文引用: 1]

YANG Qing-fang, CHEN Lin. Division approach of traffic control work zone[J]. Journal of Jilin University: Engineering and Technology Edition, 2006, 36(Suppl. 2): 145–148.

[本文引用: 1]

尹洪英, 徐丽群, 曹永荣

基于谱聚类算法的城市路网动态分区研究

[J]. 交通信息与安全, 2010, 28 (1): 16- 19

DOI:10.3963/j.issn.1674-4861.2010.01.004      [本文引用: 1]

YIN Hong-ying, XU Li-qun, CAO Yong-rong

City transportation road network dynamic zoning based on spectral clustering algorithm

[J]. Journal of Transport Information and Safety, 2010, 28 (1): 16- 19

DOI:10.3963/j.issn.1674-4861.2010.01.004      [本文引用: 1]

陈宁宁. 信号控制子区动态划分及区域自适应协调控制研究[D]. 广州: 中山大学, 2010.

[本文引用: 1]

CHEN Ning-ning. Research on sub-area dynamic division and adaptive coordinated signal control [D]. Guangzhou: Sun Yat-sen University, 2010.

[本文引用: 1]

ZHOU Z, LIN S, XI Y. A dynamic network partition method for heterogenous urban traffic networks [C] // 15th International IEEE Conference on Intelligent Transportation Systems. Anchorage: IEEE, 2012: 820–825.

[本文引用: 1]

王力, 陈智, 刘小明, 等

基于社区发现的交通控制子区优化方法研究

[J]. 交通运输系统工程与信息, 2012, 12 (6): 164- 169

DOI:10.3969/j.issn.1009-6744.2012.06.025      [本文引用: 2]

WANG Li, CHEN Zhi, LIU Xiao-ming, et al

Sub-control-area division optimization of traffic network based on community discovery

[J]. Journal of Transportation Systems Engineering and Information Technology, 2012, 12 (6): 164- 169

DOI:10.3969/j.issn.1009-6744.2012.06.025      [本文引用: 2]

卢凯, 徐建闽, 郑淑鉴, 等

协调控制子区快速动态划分方法研究

[J]. 自动化学报, 2012, 38 (2): 137- 145

DOI:10.3969/j.issn.1003-8930.2012.02.025      [本文引用: 1]

LU Kai, XU Jian-min, ZHENG Shu-jian, et al

Research on fast dynamic division method of coordinated control subarea

[J]. Acta Automatica Sinica, 2012, 38 (2): 137- 145

DOI:10.3969/j.issn.1003-8930.2012.02.025      [本文引用: 1]

SHEN G, YANG Y

A dynamic signal coordination control method for urban arterial roads and its application

[J]. Frontiers of Information Technology and Electronic Engineering, 2016, 17 (9): 70- 81

[本文引用: 1]

徐建闽, 鄢小文, 荆彬彬, 等

考虑交叉口不同饱和度的路网动态分区方法

[J]. 交通运输系统工程与信息, 2017, 17 (4): 149- 156

[本文引用: 1]

XU Jian-min, YAN Xiao-wen, JING Bin-bin, et al

Dynamic network partitioning method based on intersections with different degree of saturation

[J]. Journal of Transportation Systems Engineering and Information Technology, 2017, 17 (4): 149- 156

[本文引用: 1]

PACEY G M. The progress of a bunch of vehicles released from a traffic signal [R]. Wokingham: Transport and Road Research Laboratory, 1956.

[本文引用: 1]

GRACE M J, POTTS R B

A theory of the diffusion of traffic platoons

[J]. Operations Research Society of America, 1964, 12 (2): 255- 275

[本文引用: 1]

ROBERTSON D I

" TRANSYT”method for area traffic control

[J]. Traffic Engineering and Control, 1969, 11 (6): 276- 281

[本文引用: 1]

林晓伟. 基于路网关联度分析的城市路网划分方法研究[D]. 长春: 吉林大学, 2017.

[本文引用: 1]

LIN Xiao-wei. Study on urban road network division method based on road network correlative degree analysis [D]. Changchun: Jilin University, 2017.

[本文引用: 1]

美国运输部联邦公路局. 交通控制系统手册[M]. 北京: 人民交通出版社, 1987.

[本文引用: 1]

沈国江, 钱晓杰

主干道动态协调控制技术

[J]. 控制与决策, 2013, 28 (12): 150- 154

[本文引用: 2]

SHEN Guo-jiang, QIAN Xiao-jie

Dynamic coordination control technique for trunk road

[J]. Control and Decision, 2013, 28 (12): 150- 154

[本文引用: 2]

NEWMAN M E J, GIRVAN M

Finding and evaluating community structure in networks

[J]. Physical Review E, 2004, 69 (2): 026113

DOI:10.1103/PhysRevE.69.026113      [本文引用: 1]

NEWMAN M E J

Fast algorithm for detecting community structure in networks

[J]. Physical Review E, 2004, 69 (6): 066133

DOI:10.1103/PhysRevE.69.066133      [本文引用: 1]

GIRVAN M, NEWMAN M E J

Community structure in social and biological networks

[J]. Proceedings of the National Academy of Sciences of the United States of America, 2002, 99 (12): 7821- 7826

DOI:10.1073/pnas.122653799      [本文引用: 1]

林丹. 基于有权网络子区划分的区域交通协调控制研究[D]. 南京: 南京邮电大学, 2017.

[本文引用: 1]

LIN Dan. Regional traffic coordination research based on the subarea of weighted network [D]. Nanjing: Nanjing University of Posts and Telecommunications, 2017.

[本文引用: 1]

/