基于Ncut的城市路网交通子区划分方法

(浙江工业大学 计算机科学与技术学院，浙江 杭州 310023)

随着城市的发展，交通路网规模扩大，城市车辆不断增加，区域性拥堵频发，使得本就复杂的交通网更加难以管理。为应对城市交通问题，城市交通协调控制策略被提出并不断完善[1]。交通流的空间分布情况决定了协调控制策略必须有合理的目标区域，交通子区划分在协调控制中扮演着重要角色，直接影响到交通协调控制策略的效率与性能。交通子区划分是协调控制策略实施之前的必要步骤。交通子区划分的作用主要有：1) 把庞大而复杂的交通路网分为相对较小、更易管理的交通子区，以分治的方法解决交通管理问题；2) 根据每个子区的特点实施灵活的交通控制策略，以提高每个子区交通控制的性能；3) 在各个子区内部执行独立的交通控制策略，避免了大规模集中式控制方法带来的问题，提高系统的可靠性。交通子区划分的概念由Walinchus[2]在1971 年提出，以子区划分是否依据动态交通状态，可以分为静态子区划分与动态子区划分。在1969 年开发的TRANSYT[3]与1979 年开发的SCOOT[4]交通控制系统中，以静态路网特征与历史交通流信息作为划分依据，均采用了静态子区划分方法。静态划分方法在划分后子区不再改变，不能根据交通流变化做出调整，会影响交通协调控制策略的效率。随着实时交通流参数测量方法越来越成熟，动态子区划分方法的研究成为主流。沈国江等[5]提出了一种路口过饱和状态识别方法，基于路口拥堵等级与相邻路口关联度，提出过饱和交通状态下的控制子区动态划分方法。莫汉康等[6]提出在路线诱导条件下，可同时获得实时与预测的交通流数据，并依据距离原则、流量原则和周期原则等分别建立交通控制子区自动划分过程。Lin等[7]基于MFD设计了需求平衡模型，使得交通子区根据实际交通态势调整，配合控制策略，对整个路网进行优化。

子区划分主要根据交叉口间的关联度进行，关联度是交叉口间静态结构特征和动态交通流参数的组合,关联度大的交叉口需要划分到同一子区中，以更好地配合协调控制策略。Hu等[8]提出了一种新的车辆检测器布设方法来收集、存储高精度交通数据，并建立基于交通状态数据的干道相邻交叉口关联度模型。李瑞敏等[9]考虑路口间距、交通流离散性和交通流量等要素，应用模糊推理确定路口间协调控制需求系数并用协调系数进行控制子区划分。Zhao等[10]提出了基于Newman快速算法的交通子区划分方法，应用于大规模路网划分上，但其方法会划分出规模相差巨大的子区。卢凯等[11]提出相邻交叉口关联度与多交叉口组合关联度的计算公式，并建立协调控制子区的划分模型，但所提方法时间复杂度高，在实际大规模路网中很难应用。交通子区划分虽然已进行多年系统性研究，但还存在着一些问题。现有方法中大都以小规模路网中历史数据或仿真数据进行研究，难以保证在实际大规模路网上应用的可行性，同时对划分的目标与原则缺少明确定义。归一化分割[12](Normalized cut，简写为Ncut)是一种普聚类算法，首先应用在图的分割领域，在划分时以整体效益为目标，均衡地划分图。通过简化路网构建成图，可以应用Ncut在大规模路网的划分中，快速得到理想的划分结果。实时交通状态是交通控制的基础数据[13]，对子区划分有显著影响，笔者依据主要交通流参数，给出路段与交叉口运行态势计算方法，并考虑交叉口距离因素，给出动静态结合的关联度计算方法，并应用Ncut对大规模交通路网进行划分。

1 交通运行态势

1.1 路段态势

速度可以直观地反映出路段的运行水平，我国制定了城市道路交通运行等级标准，规定了每个等级的道路速度与所处拥堵等级，如表1所示。拥堵等级表以粗略的方式把速度划分为5 个运行等级，但这种表示方法太过离散，不利于在研究中精确表示路段运行水平。以Lj→i代表交叉口j到交叉口i的路段，为更精细化表示路段的拥堵水平，定义SLj→i为路段Lj→i的运行态势，SLj→i是属于[0,1]区间的浮点数据，由0到1代表交通运行态势从畅通到严重拥堵，定义为

(1)

式中：vj→i为路段Lj→i的速度；vu为交通畅通和轻度拥堵的速度分解线；vd为中度拥堵与严重拥堵的分界线。如果速度vj→i高于vu，设置SLj→i=0，表示交通态势处于最好的状态。当路段速度vj→i低于vd，设置SLj→i=1，表示交通处于严重拥堵。

表1 路段交通运行等级划分Table 1 Running level of link in different speed km/h

1.2 交叉口态势

交叉口流量能一定程度上反映交叉口运行态势。交叉口态势可以表示为交叉口流量与通行能力的比值，当比值较小时表示处于畅通状态，较大时表示处于拥堵状态。交叉口不同的方向交通流量一般不同，所以拥堵水平有所差别，这里设置RFi,j表示交叉口i在j方向上的流量与这个方向的通行能力的比值，用来表示交叉口在这个方向的交通态势，其计算式为

(2)

式中：qi,j为交叉口i在j方向上的交通流量；ni,j为交叉口i在j方向上进口车道数；c为单车道通行能力。

图1为15 min内3 车道和2 车道道路交通车辆数与速度关系，可以看出速度受交通流量影响很大。流量的增加让道路上车流密度变大，使速度降低，进而影响到流量，使流量被限制在道路的通行能力之内。可以看出：在15 min内3 车道车辆数最大值在420左右，2 车道最大值在280左右，所以单车道通行能力c取560 pcu/h。

图1 15 min交通车辆数与速度关系图Fig.1 Diagram of vehicle number and speed in 15 minutes

1.3 拟合态势

由于交通流时空连续的特点，路段拥堵水平与其下游交叉口有很强关联性。交叉口过饱和会显著影响上游路段车辆汇入交叉口的速率，造成路段的拥堵。因此，可以使用路段拥堵水平反映其下游交叉口的拥堵水平。一般的，每个交叉口有4 条与其相连的路段，最为拥堵的路段对交叉口的影响最大。所以，定义SNi来表示交叉口i的拟合交通态势，其计算式为

(3)

用以拟合拥堵态势整合交叉口方向流量信息与相连路段速度信息，取(0,1)之间的浮点数，值越高表示交叉口越拥堵。

2 基于Ncut的交通子区划分

交通子区的动态划分要考虑路网结构特点和交通状态，划分出的子区应有利于交通管理和协调控制策略的实施。基于对动态子区划分的理解和前人工作的总结，笔者提出4 点划分原则：1) 子区内部交叉口的交通态势度尽可能相似，以利于使用同一套配时方案；2) 距离是影响交叉口间关联度的重要因素，距离越小关联度越大；3) 同一子区的交叉口必须是空间上连通的，否则不利于交通管理；4) 子区的规模应限制在合适的范围内，因为规模过大的子区其内部交叉口的态势差异势必过大，同时也会更加复杂，不利于交通控制的实施，子区的最大交叉口数目设置为15比较合适[14]。

2.1 关联度计算

相邻交叉口之间静态关联度主要由交叉口间距离(或者说路段长度)构成。距离越短，关联度越大，当距离小于等于200 m，关联度达到最大值。设置FS(i,j)表示交叉口i与交叉口j之间的关联度，定义式为

(4)

式中：a(i,j)为交叉口之间的邻接关系，设置a(i,j)=1表示交叉口i与交叉口j直接相连，反之a(i,j)=0；li,j为交叉口i与j之间路段的长度；σX为配置参数，取值为160；FS(i,j)反映了路网静态部分中交叉口之间邻接关系与距离关系，相邻交叉口随着距离增大，关联度逐渐变小。

整合交叉口的交通态势，定义交叉口i与j的关联度w(i,j)为

(5)

式中配置参数σI取值为0.2。此关联度整合了动静态要素，动态要素中，2 个交叉口之间拥堵态势差异越大，关联度越小。直接相连的2 个交叉口，距离越近、交通态势越相近关联度越大，反之越小。

2.2 路网初步划分

Ncut在分割图时，把图G=(V,E)(V是图中节点的集合，E是图中边的集合)划分为A和B两部分时，其中A∪B=V，A∩B=∅，即移走所有连接A，B两部分的边，被移走的边的权值之和定义为cut(A,B)，表示子图A，B之间的割值，即

(6)

式中w(u,v)为节点u和v之间边的权重。Ncut使用了子图之间归一化割值(Ncut)和子图内部归一化关联度(Nassoc)来衡量划分的优劣，并定义为

(7)

(8)

Ncut(A,B)=2-Nassoc(A,B)

(9)

寻找最小的Ncut值问题可以通过解特征方程高效计算出来，其计算式为

(D-W)x=λDx

(10)

式中：W为图G的边权矩阵；D为W的度矩阵。求解特征方程式(10)，可以利用第二小的特征解对应的特征向量二分图G。

把Ncut算法应用到交通子区的划分问题上，对路网进行初步划分，步骤如下：

1) 基于交通路网构建带权图G=(V,E)，图G中节点为路网中交叉口，边为路段，权重为交叉口之间的关联度，构建边权矩阵W。

2) 解特征方程(D-W)x=λDx。

3) 利用解得的第二小的特征值对应的特征向量，划分图G。

4) 如果子图中节点数多于15 个，则递归地调用此过程对子图划分，直到子图中节点数小于或等于15 个。

2.3 边界调整

Ncut每次对图的划分以当前最优的归一化割值为目标进行二分，而当前划分在其子图的划分结果中不一定是最优的，随着划分次数的增加，使得划分结果偏离最优划分目标。在经过多次划分后，可能有子区边界上个别节点在划分结果里并非最优，需要做调整。调整以子区总关联度最大为目标，每次移动子区边界上的交叉口到相邻子区，最终形成更加紧密的子区。子区总关联度的计算为

(11)

式中：cor(G)为路网G的总关联度；N为子区总数。通过对子区边界节点调整，让处于子区边界上的节点回到能使得总关联度最大的子区中，使划分趋于最优。具体步骤如下：

1) 计算当前划分的总关联度，并记为cor(G)pre。

2) 对所有子区边缘的交叉口i(i∈A)，如果在i并入其相邻的子区B后，B中交叉口数目没达到子区规模上限，计算当节点i加入子区B之后总的cor(G)值。

3) 选择步骤2)中所算出来的最大的cor(G)，判断其是否大于cor(G)pre，如果大于，则让其对应节点加入对应子区，返回步骤1)并继续。否则，调整结束。

3 实 验

3.1 路网描述

为检验上述讨论方法，设计实验使用真实的路网数据来加以验证。实验路网是绍兴市柯桥区，共有23条路，223 个路段和69 个交叉口，从主城区到郊区，交叉口和路段上全都覆盖了交通检测器。实验以2017 年6 月6 日17：00—17：15晚高峰的数据来作研究，路网交通态势如图2所示。同时在交通图2中圈出了路网的一部分，其中交叉口已做编号，交通流量和运行态势在如表2所示。交通运行态势由交叉口的方向饱和度和相连路段的拥堵态势组成，数值越大表示拥堵程度越高。

图2 路段交通态势图Fig.2 Map of link traffic state

表2 路网部分交叉口流量及态势Table 2 Traffic flow and traffic state of part road network

3.2 交通子区划分

应用基于归一化分割的子区划分方法在柯桥区路网上进行子区划分，图3为划分过程。图3(a)为划分的路网范围。图3(b)中，经过第1 次分割路网被划分为地图最下部的6 个交叉口与路网其他部分。可以看出地图最下面的6 个路口通过1 条干道组成1 个子区，它们与路网的其他部分只有1 条道路相连,因此容易形成独立子区。图3(c～g)中，每次划分都近似为对目标网络的均衡划分，并且产生2 个形状良好且空间上紧密相连的子区。Ncut划分从原则上要求子区内部交叉口间有较强的关联度，而较强的关联度倾向于让子区形成较规则的形状。在图3(g)中，最后把16 个交叉口划分形成了子区C和D，根据图2与表2中路网的交通状态数据，子区C同D相比，交叉口流量更大，更为拥堵，而C和D在子区内部各自拥有较短路段距离，分别形成较高关联度，Ncut均衡分割的特点最后形成2 个交叉口数目相近的稳定子区。可以看出：基于Ncut划分方法能有效把拥堵相近、距离紧密的交叉口划分到同一子区内。路网最后被划分为7 个子区，各子区交叉口数目及关联度值如表3所示，总关联度为22.36。

经过边界调整，共有3 个节点从原来的子区移动到临近子区中。最终的划分如图3(h)所示，对应的总关联度值为22.43，其中每个子区的交叉口数目和关联度对应如表4所示。

图3 路网子区划分过程Fig.3 Partition process of road network

表3 初步划分结果Table 3 Preliminary partition result

表4 边界调整后划分结果Table 4 Partition result after boundary adjustment

3.3 对比实验

为了验证Ncut在子区划分中的优越性，用层次聚类的方法在相同条件下作为对照，对交通路网进行划分。凝聚的层次聚类在子区划分中是一种较常用的基础算法，其贪心的思想能在划分中取得不错的效果。在划分时，层次聚类算法每次寻找两个关联度最为密切的交叉口并合并到同一子区，保证了划分结果总关联度值接近最大。作为对照，实验采用上面的路网与关联度矩阵，同样要求划分的子区规模不能超过15 个交叉口，不限制最后生成几个子区。划分结果如表5所示。层次聚类划分结果所得到的总关联值为22.03，较小于基于Ncut子区划结果。但是层次聚类的划分结果里常会出现单交叉口作为子区的情况，在上面的划分中有2 个子区包含1 个交叉口，1 个子区包含2 个交叉口，这些少量交叉口形成的子区大都分布在路网的边缘地带。究其原因，层次聚类在划分时让关联度最大的优先合并，在路网内部关联度较大的合并达到子区最大规模时，路网边缘交叉口则无法再并入子区，因而成为独立子区。单交叉口形成子区往往给管理增加负担，在子区划分中应尽量避免。基于Ncut的子区划分方法能均衡划分，因此可以避免少数交叉口形成独立子区的情况。

表5 基于层次聚类的子区划分结果Table 5 Partition result based on hierarchical clustering

4 结 论

在交通子区动态划分中，交通态势对划分结果产生重要影响。应用重要交通流参数计算交通运行状态，得到路段、交叉口拥堵态势，结合路网静态参数计算路网关联度矩阵。基于Ncut的交通子区划分方法让交通态势相似，空间上临近的交叉口划分到同一子区，Ncut的每次分割是对目标网络进行均衡分割，形成两个互相关联较小而内部紧密的子区，并且避免少数交叉口形成独立子区的情况。通过边界调整，让子区总关联度达到最大，同时划分结果趋于最优。经过真实路网数据验证与对比实验分析，该方法在满足子区划分要求的同时能出色完成子区划分任务。