基于改进社区发现算法的交通控制子区动态划分

张正华, 钱 锦, 房崇鑫, 张嘉烽, 顾逸枫

(扬州大学信息工程学院, 江苏 扬州 225127)

对区域交通网络的合理划分可降低区域交通网络整体控制与管理的复杂性[1-2]．针对复杂交通网络下的子区域动态划分, 国内外学者开展了大量研究．Etemadnia等[3]结合网络出口函数(network exit function, NEF)对不同道路结构的交通性能实现分区, 但是此方法无法适用于大型交通网络; Ramezani等[4]引入基于整个交通网络的聚合模型, 结合动力学原理实现分区,但因仅考虑了路段交通流量这一因素的影响,导致划分结果不够全面; Johnson等[5]采用双层规划模型预先定义若干互连子区域, 但该方法提前假设的子区域数目较为武断; Lin等[6]考虑交通网络流量的移动性和吞吐量, 基于宏观基本图论(macroscopic fundamental diagram, MFD)提出一种需求平衡子区域划分模型; Kouvelas等[7]运用非线性模型描述划分的子区随时间变化的关系, 由于子区域划分策略频繁切换, 从而导致区域内部不稳定; An等[8]提出交通网络四步划分方法, 因增加了交通拥堵的划分, 导致算法复杂度太大,而无法适用于大型网络; Dong等[9]基于文献[6]方法通过回归分析计算各个子区域的交通状态值并合并若干小的子区域, 验证了小规模交通网络的MFD存在, 但该算法限制了交通网络外部边界的车流流入; 徐建闽等[10]采用Mcut算法, 以路口饱和度表示交叉口的拥堵程度,从而建立路段权值模型进行子区域划分,该方法因须已知网络节点数目, 故无法适用于未知网络; Li等[11]利用交通多源数据采集系统进行交通信息预测, 采用k-means算法对交通网络进行划分,其聚类中心节点的选取存在主观性．上述算法大部分针对无权网络且划分的结果具有不确定性,难以保证划分的客观性和有效性．社区发现算法[12-13]可以向着最优模块度的方向不断合并网络节点得到划分结果,能够保持较高的准确性且适应交通网络的拓扑结构;因此,本文拟改进社区发现算法,以网络模块度作为划分的评价指标, 综合考虑相邻交叉口之间的距离、路段交通流量时空特性、交通信号配时参数和车辆排队长度等因素,建立动态子区域划分模型, 并以江苏省扬州市部分区域的交通为案例进行对比实验, 验证方案的可行性和合理性．

1 相邻交叉口的关联度分析

1.1 路段长度关联度

当两交叉口间的距离较小时, 二者表现出强相关性; 反之, 距离较大时, 则表现出弱相关性．交叉口i、j之间的路段长度关联度

(1)

其中lij为交叉口i、j之间的距离,σ为缩小函数值域的配置参数,lmin为两交叉口间允许的最小距离．

1.2 车辆排队长度关联度

车辆排队长度主要由前一个周期未通行车辆和上游路口驶入的车辆组成．假设交叉口i处由北驶入向左转弯的车流量为qNLi, 由南驶入向右转弯的车流量为qSNi, 交叉口j处前一个周期未通行的车流量为qoddj, 平均车身长度为Δl．故交叉口i、j的车辆排队长度关联度

(2)

1.3 信号周期关联度

当两交叉口的信号周期相同或呈倍数关系且相位差保持稳定时,两交叉口间表现出强相关性;反之,若两者信号周期相差较大且相位差参差不齐,两交叉口间表现出弱相关性．交叉口i、j间的信号周期关联度

(3)

其中cmax、cmin分别为交叉口i、j信号周期的最大值和最小值;R为相邻交叉口周期的关联度,一般取值为2;λ为信号周期关联权重系数,λ=ent(R+1).

综合考虑上述相邻交叉口的路段长度、车辆排队长度及信号周期关联度,建立总关联度模型:

Dij=Dlij·Dqij·Dcij.

(4)

2 改进的社区发现算法

2.1 社区模块度

社区模块度[14]被专用于社区划分的性能评价．假设有x个节点, 每个节点都代表一个输出,现将其划分成N个社区, 其中一共有m个节点相连接．i和j为x中的任意两个节点, 当两个节点相连时Aij等于1, 反之则等于0．ki为节点i的度, 2m则为整个社区节点的度,si用来判断i是否属于同一社区, 属于则为1不属于则为-1．定义模块度

(5)

(6)

模块度Q值越大代表社区网络划分的效果越好, 当Q值为[0.3,0.7]时划分结果较优．

将式(5)改写为

(7)

式中

(8)

(9)

其中evw表示一个节点在社区v内、另一个节点在社区w内的边;hvv则代表在社区v内所有的边与整个社区网络所有边的比值;av为v社区节点的度占整个社区网络度的比值．

2.2 改进算法

参照文献[15], 改进文献[13]中点权与边权的表达式, 使得其更适用于有权网络．将模块度Q改写为

(10)

式中对称矩阵C表示网络被划分为k个社区的集合, 每个社区为一个矩阵c,c中元素cij为社区内部边权在整个网络边权中的占比,vi=∑jcij代表社区i内部节点与外部相连节点的边权和整个网络边权的比值．sum(C2)为C2中所有元素之和．

为了表示节点间关联性的大小,现将式(8)(9)改写为权值形式:

(11)

(12)

式中gij为节点i和j之间边的权值．

本文算法流程如下:

步骤1: 初始化社区网络, 将Y个节点划分成各自独立的社区．初始的evw满足:

(13)

式中t为社区网络的总边数;

步骤2: 合并有边相连的节点形成新的社区, 记录每次合并后的模块度增量ΔQ:

ΔQ=evw+ewv-2avaw=2(evw-avaw).

(14)

整个算法的运行沿着模块度Q增大最多或减少最小的方向进行,每一次合并后更新相应的元素evw,并将v,w社区有边相连的节点进行合并;

步骤3: 重复执行步骤2,直至整个网络成为一个整体, 共执行n-1次合并, 由此可得社区网络的划分结构, 进一步选择对应模块度最大的Q值, 即可得到最优的社区网络划分．

3 实例分析

3.1 交通网络选取

本文以扬州市部分交通网络为实验对象,对改进的算法进行论证．选取以文昌阁为中心的全部安装有交通信息检测器的区域路网(如图1所示), 其中包含23个路段和21个交叉口．为了直观地说明, 现将图1等效为如图2所示的网络节点图, 交叉口等效为网络节点, 路段等效成网络的边,并对各节点进行相应的编号．

3.2 子区域划分结果分析

采集2020年5月19日21个交叉口的交通数据信息,经误差分析剔除误差较大的数据．选取14:00-15:00交通数据通过关联度模型计算23个路段的关联度,计算结果如表1所示．

分别采用传统的社区发现算法和本文算法对选取的区域交通网络进行子区域划分, 两种最优划分结果如图3所示．由图3可见: 1) 传统的社区发现算法的Q最大值为0.564 0, 整个网络被划分为4个社区: 交叉口1、5、6、21为子区域Ⅰ; 交叉口2、4、10、11、12为子区域Ⅱ;交叉口7、8、9为子区域Ⅲ; 交叉口3、13、14、15、16、17、18、19、20为子区域Ⅳ．图3(a)中交叉口1与交叉口5被划分在同一区域内,而交叉口1与交叉口5在实际交通网络中的距离远大于交叉口1与交叉口2、4的距离, 所以此类划分方法存在不合理性,无法准确显示出交叉口之间的关联性．

2) 改进后算法的Q最大值为0.604 1, 整个网络被划分为5个社区: 交叉口1、2、3、4、10、11、12、13、14为子区域Ⅰ; 交叉口5、6、21为子区域Ⅱ; 交叉口7、8、9为子区域Ⅲ; 交叉口15、16、19、20为子区域Ⅳ; 交叉口17、18为子区域Ⅴ．

结果表明: 本文算法在进行子区域划分时兼顾了相连交叉口路段长度的固有属性和交通环境的动态特性, 并且Q值比传统算法的高7.2%,本文算法划分效果更优．

表1 交叉口的关联度计算结果

3.3 动态划分结果分析

选取当日16:00-17:00数据验证本文算法的动态划分效果, 此时Q值为0.602 7, 划分结果如图4所示．整个网络被划分为5个社区: 交叉口1、2、3、4、7、10、11、12、13、14为子区域Ⅰ; 交叉口5、6、21为子区域Ⅱ; 交叉口8、9为子区域Ⅲ; 交叉口15、16、19、20为子区域Ⅳ; 交叉口17、18为子区域Ⅴ．与图3(b)划分结果相比, 交叉口7划分到区域Ⅰ中．结果表明本文算法可以实现不同时段的动态划分, 并且划分的区域结果差异小,能够保持整个交通网络控制的稳定性．

4 结论

本文综合考虑交叉口之间的静态和动态特性建立交叉口关联度模型,改进社区网络节点和边的权值,进而改进社区发现算法．结果表明: 本文算法可以达到动态划分的目的,能促进子区域内信号协调控制决策的生成;有利于降低城市交通信号的联合控制的复杂度,保证在同一个子区域内的路口具有较强的内聚性,而在不同子区域内的路口具有较低的耦合性．