基于均衡k划分的动态子区划分方法

修伟杰, 王 力, 张立立, 李 敏, 张玲玉

(1.北方工业大学 城市道路交通智能控制技术北京市重点实验室, 北京 100144;2.北京石油化工学院 信息工程学院, 北京 102617; 3.北京中合云通科技发展有限公司, 北京 100041)

0 引 言

一个规模较大城市的路网交通信号控制系统通常会将路网按照辖区属性、交叉口关联性或路网控制策略进行区域动态划分, 以减小控制系统的复杂度。近年来，交通子区动态划分的研究主要集中在指标的选取和划分两方面。

在指标选取方面：别一鸣等[1]从交通控制系统整体角度出发, 研究了子区划分与信号配时方案优化的内在联系, 以饱和度为指标，将交叉口状态划分为4个等级, 并根据状态等级确定交叉口的控制目标, 由此建立子区划分原则; 杨洁等[2]利用协调系数与不均衡系数两类路段关联度指标, 分析交叉口群交通关联特征, 提出交叉口群信号协调控制范围动态划分方法; 沈国江等[3]在引入路段车辆容量比和路段交通需求影响度的基础上, 提出基于路口拥堵等级划分与相邻路口关联度的一种子区分级动态划分策略；Liu等[4]利用Pearson相关系数和数据归一化, 提出了一种新的组合特征参数用于聚类划分算法。

在划分算法研究领域：首艳芳等[5]建立了一套基于相邻交叉口间距最大-最小原则和交叉口相聚度分析的控制子区划分模型, 设计了一种交叉口群聚类算法, 实现了对控制子区划分方案的综合分析评价; 马旭辉等[6]从路网拓扑结构入手, 设计了一种基于路网可达性的交通子区划分方法; 王力等[7]以社区模块度为评价指标, 利用凝聚社区发现算法实现了控制子区划分; 以此为基础, 张正华等[8]通过分析相邻路口的路段长度、排队长度和信号周期等3个因素建立相邻交叉口总关联度模型, 提出一种基于改进社区发现算法的交通控制子区动态划分方法; 卢凯等[9]建立了基于关联度分析的子区动态划分模型, 并结合遗传算法的优化求解模型的解, 但遗传算法在搜索效率与寻优能力方面存在不足, 使得控制子区划分算法不能更快更准地搜索到最优或次优子区划分方案；Cebecauer等[10]根据路段相邻性采用聚类方法将大型路网转换成一个具有特定结构的图, 并提出了一个基于谱聚类的子区划分算法；An等[11]设计了一种包括4个步骤的交通子区聚类划分方法, 该方法引入了λ关联度的概念, 采用了基于聚类的区域增长技术和启发式算法, 解决了谱聚类等图割方法要求路网信息完整的问题。

上述研究多未考虑多交叉口之间总体关联性大小, 也未将影响控制子区划分的各种因素进行有效综合，且分区指标选取往往集中在一种或几种交通参数的综合选取上, 并未考虑路网的全局特性，算法缺乏理论支撑。本文通过路网交叉口和路段权重建模, 将路网抽象成加权拓扑网络, 将城市交通路网子区划分转化为图划分问题, 按照指定的约束条件将路网划分为若干个子域并不断动态优化目标函数，对于划分结果, 进一步提出多交叉口状态可控的判据为路网协调控制策略设计提供依据。

1 问题描述

1.1 路网拓扑建模

1.2 基于均衡k划分的子区动态划分问题描述

1.3 交叉口权重模型

各交叉口对区域总体状态影响具有差异性, 交叉口权重体现对网络特定结构和功能的影响。

1.3.1 交叉口节点阻抗权重——信号控制相关 交叉口节点阻抗主要是指交叉口处车辆产生的延误, 是反映车辆在信号交叉口的受阻情况以及行驶时间损失情况的指标。

(1)

式中:y=1-(1-K/Kj)2，Kj=n/(l+l0);c为信号周期;λ为绿信比;q为该车道车辆到达率;x0为饱和度临界值;K为交通密度;Kj为理论阻塞密度;n为单向机动车车道条数;l0为平均阻塞车间净距, 取1.5 m;l为平均车身长度, 取5 m。

1.3.3 交叉口综合权重 将3个权重相乘并进行归一化, 得到交叉口的总体权重模型

(2)

1.4 路段权重模型

1.4.1 路段综合长度权重 路段权重体现路段状态对区域整体状态的影响程度。路段综合长度权重反映了不同等级路段在路网中所承担的交通运输功能, 承载交通量越大的路段, 对路网整体状态影响越大, 应赋予其较大的权重。

1.4.2 BPR路段阻抗函数权重 BPR函数是反映路段行程时间与路段流量相互关系的函数, 是目前计算道路阻抗中应用最广泛的函数之一。

wFI=t0[1+α(Q/C)β],

(3)

式中:wFI为两交叉口间的路段阻抗权重;t0为自由流状态下路段行程时间;Q为路段交通量;C为路段通行能力；α、β为阻抗影响参数, 美国公路局推荐α=0.15和β=4。

1.4.3 路段综合权重 权重越大, 说明路段越重要, 连线上的两个顶点关联性越大。将以上两个权重相乘并归一化, 得到路段Lij的总体权重wij模型为

(4)

2 基于禁忌搜索的路网子区动态划分

城市交通网络的均衡k划分[12]的目的是形成规模相似且关联性较弱的交通子区, 即图划分中割权最小、子集权值和均衡的目标即为路网k划分的目标。选取禁忌搜索算法[13]来求解图划分问题, 能够满足子区间交叉口合并和分离的划分。

2.1 基于禁忌搜索的均衡k划分算法

Step2: 参数准备。采用历史交通流数据, 包括各交叉口的流量、路段车道数、路段长度、通行能力、路段旅行时间等基础参数, 计算交叉口与路段的权重系数, 构建路网的有权拓扑图。

Step4: 定义禁忌对象和移动操作。算法的移动操作是从当前解产生新解的途径。首先从不同子集中选择两交叉口v1∈Vi,v2∈Vj, 且v1(v2)和目标子集Vj(Vi)至少有一个交叉口相连，再将交叉口v1(v2)移动到Vj(Vi)。禁忌对象是交叉口v移动到原始的子集, 在本文中禁忌长度为6(经过6步搜索之后v可以重新被移动到原始子集)。

Step5: 选择策略。如果不止一个邻域有最小割权, 选择策略设计为: 先考虑邻域对象是否处于禁忌状态; 再考虑移动频数, 即每个交叉口移动到不同子集的频数。将惩罚移动频数较高的交叉口给予较高的优先选择权。

Step6: 算法停止准则。子区划分既要保证子区内各交叉口的密度近似, 又要保证各子区间饱和度具有较大差异。因此选用密度相似性指标来评价子区的划分结果:

(5)

式中:k表示分区总数；d表示子区路段密度；C表示子区集;NI、NJ分别表示子区I和J包含的节点数;DSIk是衡量子区I划分合理与否的指标;DSII表示子区内部密度的相似性;DSNIJ表示相邻子区之间密度的相似性;NeiI表示与子区A相邻的相似性最大的子区;DSI为所有分区密度相似性均值, 若DSI<1, 子区划分较合理。

2.2 子区的动态调整

3 实验分析

采集潍坊市部分路网的实际流量数据, 结合路网的物理拓扑特性, 验证所提划分方法的有效性, 路网如图1所示。该路网包含32个灯控交叉口, 104条路段。当前路网为分时段固定配时方案, 选取早高峰时段的数据: 路网中配时方案包含2处两阶段运行路口, 6处三阶段运行路口, 其余14处为四阶段运行。

图1 潍坊实际路网(a)与拓扑(b)示意图

路网的交叉口和路段权重分布如图2所示。可知, 不同交叉口和路段, 其权重大小有明显的差异。权重值较高的交叉口5、11、15、30主要集中在医院和商圈附近, 一方面负担了大量的交通流量, 另一方面是城市交通量的主要发生、吸引源, 这些交叉口附近呈现明显的交通流量聚集性, 故权重较大。

图2 交叉口(a)与路段(b)权重

邻接节点之间存在重要依赖性关系, 结合交叉口自身的位置信息, 交叉口权重的大小搭配能够使路网的节点群均匀分布, 以避免出现重要性太大的节点群影响路网的综合调控指标。

表1为不同子区划分结果根据2.1节k值的选取原则, 在潍坊实际路网中, 计算所得的k=4为最优的划分形式。如图3所示, 在选取k=4进行路网子区划分时可有两种划分结果适应路网不同交通流量规模和交通状态, 可以看出, 路口13、16和17是划分子区的重要边界节点, 在交通流量变化时会发生子区归属变化。

图3 k=4子区划分结果

表1 不同分区数的子区划分结果

由表2的划分结果可知, 对于节点权重较大的关键路口, 选择较小权重的交叉口与其组成控制子区, 通常权重较大的路口需要更多的空间来分散其交通流, 因此，本文一方面将路网划分为权重较均衡的交叉口群；另一方面能够为均衡控制策略提供初始解, 使得系统更快收敛至控制目标。

表2 k=4各项指标结果

在相同路网的控制策略下, 本文选取一种基于交叉口关联度模型, 综合考虑各路段关联度及交叉口相似度值的分区方法[14]与本文方法进行比较, 验证不同分区方法对控制效果的影响, 选取路网的平均延误和平均密度作为评价指标。引用文献[15-16]的均衡控制方法来评价不同子区划分的路网控制效果(表3)。可以看出, 传统划分方法的子区均衡指数偏高, 说明子区内交叉口的密度方差较大; 从控制效果来看, 本文的分区方法能够降低路网的平均延误, 而且路网内各路段的密度较传统方法更均衡, 能够有效缓解路网流量不均衡分布的现象, 提高了路网的效率。

表3 两种方法划分结果比较

同时, 将本文采用的启发式方法与传统k-means方法进行比对, 在算法运行过程中选取8个计算点对算法运行的时间复杂度进行计算, 如图4所示。可以看出, 采用启发式方法在计算初始中心选取方法计算初始近似解时具有更低的时间复杂度, 即在相同计算精度下该方法用时更少, 尤其是随着算法运行了两种方法的时间复杂度差持续增加, 表明启发式方法具有更好的实时性。

图4 两种算法的时间复杂度对比

4 结 论

本文从交通路网控制子区划分问题入手, 提出基于均衡k划分的动态子区划分方法。首先, 构建交叉口和路段权重模型,并将路网抽象成为带权拓扑图; 再采用改进的禁忌搜索算法进行优化求解;最后,利用实际数据将所提方法与已有方法进行对比。结果显示,由于采用启发式方法为禁忌搜索算法提供初始近似解能够有效降低其复杂度, 提高计算的实时性; 以任意子区内节点权重之和差异最小及连接不同子区的边权之和最小为目标, 从全局角度考虑路网均衡划分, 能够避免拥堵路口集中分布在一个子区的现象, 更好降低路网协调控制的难度, 避免多个高负荷交叉口聚集而影响路网运行效率。