郑黎黎 王世广 王 伟 丁同强

(吉林大学汽车仿真与控制国家重点实验室1) 长春 130022) (吉林大学交通学院2) 长春 130022)(吉林大学吉林省道路交通重点实验室3) 长春 130022)

城市道路交通网络关键节点辨识方法研究*

郑黎黎1,2,3)王世广2)王 伟2)丁同强2)

(吉林大学汽车仿真与控制国家重点实验室1)长春 130022) (吉林大学交通学院2)长春 130022)(吉林大学吉林省道路交通重点实验室3)长春 130022)

综合考虑城市道路网络的拓扑结构特征和交通流特性，建立城市道路交通网络关键节点评价指标体系；设计了基于P-灰色加权关联分析的关键节点辨识方法，利用长春市区域路网进行了实例分析，并和其他方法的排序结论进行了对比，证实文中提出的方法可行、有效.通过进一步数据拟合，给出了节点重要度和相关指标的拟合公式.

交通工程；关键节点辨识；复杂网络理论；主成分分析；灰色加权关联分析

0 引 言

就城市交通网络的演化特征而言，网络拓扑对城市交通网络上的流量分布、出行阻抗分布，以及其他动力学过程具有潜在的巨大影响[1-2].从这一角度，许多学者借鉴其他领域利用复杂网络理论几何特征指标对节点重要性评价的思路开展了交通领域的研究[3-6].文献[7-9]分别提出最短路径介数、最小生成树和参数I(i)=Ce(i)×M(i)×K(i)等作为指标来衡量节点的重要性.文献[10]提出了一种以路段阻抗为权重、以凝聚度为指标的加权节点收缩方法.另外，从路网的交通流特性角度出发，文献[11]基于节点删除法提出了考虑级联失效的交通网络节点重要度评价方法，认为出行网络结构、出行者行为对节点重要度有重要影响.文献[12]选取行程车速、延误和饱和度等对城市道路交通关键节点进行辨别.本文综合考虑城市道路网络的拓扑结构特征和交通流特性，提出基于道路等级的节点度、基于行程时间的节点介数和平均路径长度变化率与交通流主要特性指标共同构成关键节点评价体系，并运用主成分分析与灰色加权关联分析相结合的方法来实现城市道路交通网络关键节点的辨识，最后进行实例分析.

1 城市道路交通网络关键节点评价指标体系的构建及优化

1.1 交叉口重要度函数

图1为关键节点评价体系.定义交叉口重要度λ是评价指标体系中各参数的一个函数，若设A为复杂网络特性指标集合；B为交通特性指标集合,则有λ=f(A;B).

图1 关键节点评价指标体系

1.2 复杂网络特性指标

1) 基于道路等级的节点度k结合复杂网络理论中节点度的概念，本文定义基于道路等级的节点度为交叉口所连路段各进口道与出口道车道数之和的均值.

(1)

式中:n为交叉口进口道数；kjo为交叉口出口道车道数；kji为交叉口进口道车道数.

通常，度越大代表着该节点在网络中越重要，它描述了节点的连接程度.

2) 平均路径长度变化率ΔL基于行程时间的平均路径长度变化率

(2)

式中：L0为在自由行驶条件下的平均路径长度；Li为任意节点i删除后道路交通网络的平均路径长度.

其中，平均路径长度是交通网络中所有节点对之间距离的平均值，即

(3)

式中：N为道路交通网络中节点的个数；dij为从节点i到节点j的最短距离；V为道路交通网络中的节点集.

通常，平均路径长度变化率越大，表明该节点在交通网络中越重要.

3) 基于行程时间的介数Bi基于行程时间的节点介数可定义为道路交通网络中所有的最短路径中经过该节点的数量比例.节点i的介数Bi由下式计算.

(4)

式中：njk为任意连接点j和k的最短路径的数量；njk(i)为连接点j和k且经过点i最短路径的数量.此处最短路径是指从i到j所需行程时间最小的路径，可通过Floyd算法计算出所有节点对之间的最短路径.

依据最短行程时间计算的介数反映了节点在整个交通网络中的作用和影响力，具有很强的现实意义.

对于交通特性指标的详细定义参见相关书籍，限于篇幅在此不再赘述.

1.3 评价指标的优化

为了提高算法的精度和效率，选取主成分分析法(principal component analysis)来确定关键节点的主要影响因素.它是一种设法将原来变量重新组合成一组新的互相无关的几个综合变量，同时根据实际需要从中可以取出几个较少的总和变量尽可能多地反映原来变量的信息的统计方法，在数学上经常用于处理降维问题.

在获得各个指标xi(i=1,2,…,n)的数据之后，对其进行主成分分析，选取特征值大于1且一般累积贡献率大于85%的成分作为主成分yj(j=1,2,…,m)(m≤n)，则λ=f(y1,y2,…,ym).

2 基于P-灰色加权关联分析的城市道路交通网络关键节点评估算法

基于P-灰色关联分析的城市道路交通网络关键节点评价步骤如下.

步骤1 假设路网中共有N个节点，m个节点评价指标，则第α(1≤α≤N)个节点的比较数列为

yα(j)=[yα(1),yα(2),yα(3),...,yα(m)]

式中：yα(j)为第α个节点的第j个主成分.

步骤2 综合比较后得出这些节点的评价指标参考序列Y= [Y(1)，Y(2)，…，Y(m)].其中：该序列中的Y(j)是所有节点中第j个主成分的最优值.

步骤3 数据量纲一的量化处理 这里可以采用SPSS对数据进行标准化处理，得到比较数据序列

量纲一的量化后得到参考数据序列

Y*= [Y*(1)，Y*(2)，…，Y*(m)]

根据

(5)

分别求出最大值Δmax和最小值Δmin.

步骤4 确定各指标对应的权重 可由主成分分析中的特征值近似确定各指标对应的权重w=w(j),j=(1,2,…,m).

步骤5 计算判断指标关联系数

(6)

式中：ρ为分辨系数，取值在0-1之间，通常取ρ=0.5.

步骤6 计算灰色加权关联度，得到交叉口重要度

(7)

步骤7 计算每个节点的灰色加权关联度大小，一般地，关联度越大节点就越重要，关联度最大的节点为关键节点.

3 实例分析

3.1 数据获取及指标优化

本文选取长春市亚泰大街、解放大路、民康路和三道街包围的路网作为分析对象，见图2.根据2013年12月24日早高峰调查的基础数据并经

过相关计算得到10个节点的7类评价指标，见表1.

图2 交通网络拓扑结构

序号指标kΔLBi流量q/(pcu·h-1)饱和度x排队长度l/m延误/s16.750.04760.07456530.51730.0924.8727.800.08040.10475110.69822.6440.2036.000.03820.06724340.6956.6431.1442.500.06420.11121470.49710.1012.9453.000.09840.09628980.5497.3012.5064.000.04570.06717510.6798.2018.1277.330.03680.08951990.74119.6223.9086.000.02450.16364230.53012.417.7392.500.10200.12614480.3036.2412.84102.250.12500.1049890.4042.1410.31

利用SPSS对数据进行主成分分析，选取2个主成分yj(j=1,2)，经标准化的各个指标xi(i=1,2,…,7)分别代表节点度、平均路径变化率、介数、流量、饱和度、排队长度、延误.则有各主成分表达式

y1= 0.48x1-0.33x2-0.13x3+

0.41x4+0.38x5+0.39x6+0.42x7

(8)

y2= 0.08x1+0.03x2+0.77x3+

0.44x4-0.39x5+0.21x6-0.10x7

(9)

第一主成分y1中，除平均路径变化率和介数与其呈负相关之外，y1与其他指标为正相关关系，且各系数大体相当，可看成是反映这些变量的综合指标；第二主成分y2中，与其呈负相关关系的指标是饱和度和延误，介数、流量、排队长度的系数比较大，可以看成是主要反映这些变量的综合指标.不难看出，两个主成分对于城市路网拓扑性质和交通流特性的反映各有侧重.

3.2 关键节点评估与分析

利用式(8),(9)计算初始数据，然后按照评估算法计算可得到如下的交叉口重要度分布图，见图3.

图3 重要度分布

由图3可见，交叉口2的重要度最大，为该路网的关键节点.这与交通流运行情况相符，调查日区域交通拥挤最先出现在该交叉口，因而该方法具有一定的有效性和可行性.

为了进一步说明本文算法的精度，下面将把本文算法与经典的节点删除法、节点收缩法和灰色关联度法[13]进行对比分析.需要指出，交通网络为加权复杂网络，节点收缩法考虑了交通阻抗的影响；而灰色关联度法采用的是本文选取的指标,重要度排序对比见表2.

由表2可见，本例中各个方法对于关键节点的判定结果是一致的，对于其他节点的重要度排序存在较大差异.经过对比分析可获得以下结论.

1) 节点删除法与本文算法对比 排序第2的节点分别为8和7.虽然两个节点皆为主次干路相交，但节点7中民康路为双向六车道，而节点8中大经路为双向4车道；删除节点7后路网平均路径长度变化幅度更大；节点7的饱和度、排队长度、延误明显高于节点8.因而按照本文关键节点的定义，节点7对路网结构安全、可靠及路网整体性能发挥更为重要.其他分析过程类似.故本文算法更优.节点删除法认为去掉该节点以及相关联的链路后使得图的生成树数目最小的为关键节点.对交通网络来讲，单纯从路网拓扑结构的角度考虑是不尽合理的.因而本文借鉴其思路进行了改进，并且取得了更强的解释性.

表2 重要度排序对比

2) 节点收缩法与本文算法对比 排序第2的节点分别为9和7.首先，节点7为主次干路相交，节点9为次干路与支路相交；节点7和9的高峰小时流量分别为5 199,1 448 pcu/h，交通功能相差悬殊.因而本文认为节点7更为重要.其他分析过程类似.故本文算法更优.节点收缩法认为收缩后使得网络凝聚程度越高的节点就越重要，其定义的凝聚度的概念对于交通网络突出特性的体现并不充分；(3)灰色关联度法与本文算法对比.两种方法的争议主要在排序第2的节点：节点1和7.由重要度分布图中不难看出，两者的重要度非常相近.为了表现本文算法的辨识性深入对比分析一下.两个节点都是主次干路相交，但节点7中民康路为双向6车道，节点1中大经路为双向4车道，且大经路西北-东南方向为特殊的1车道，东岭街为支路；有更多的最短路径经过节点7；流量大体相当的情况下节点7的饱和度明显高于节点1.因而节点7对于路网整体性能的发挥、稳定更为关键.可以认为，本文算法的结论更合理一些.

综合以上分析，P-灰色加权关联分析算法更为合理、有效.

3.3 模型简化

城市道路交通网络中该算法参数同时获取难度较大、计算相对复杂，下文将根据算例对模型进行简化分析，以期获得更好的应用.

首先，将重要度与SPSS给出的标准化数据进行逐步回归分析，得到

λ=3.708+0.480k′+0.364q′

(10)

式中：λ为重要度；k′为标准化的节点度；q′为标准化的流量.修正R2=0.979.

然后，从单个变量入手进一步探究各指标与结论之间的关系.其中与排序相关系数较大的指标有节点度、流量、延误、排队长度，相关系数分别为0.963，0.944，0.848，0.838，相互关系见图4.

图4 排序结论与相关变量的关系

此处延误与排队长度变化趋势大体一致，未给出对比图.其中基于道路等级的节点度可以反映城市路网的拓扑性质，流量、延误、排队长度可以反映城市路网的交通流特性.考虑到各指标的获取难度和相关程度，分别对节点度和流量与重要度进行拟合，可以根据实际情况进行参照使用.拟合关系式为

λ=3.708+0.794k′

(11)

λ=3.708+0.777q′

(12)

式中：λ为重要度；k′为标准化的节点度；q′为标准化的流量.

4 结 束 语

本文基于道路交通网络的拓扑结构特征和交通流特性，研究并建立了路网中关键节点的评价指标体系及辨识方法，并通过实例分析验证了该方法的有效性和实用性，根据实际数据给出了可供参考的关键节点重要度与相关指标的拟合公式，为交通管理者在交通控制和应急管理方面确定关键节点提供了新方法和新思路.

[1]沈鸿飞,贾利民,王笑京,等.基于公路网结构特性的关键节点评价指标与辨识方法[J].公路交通科技,2012,29(9):137-142.

[2]吴建军.城市交通网络拓扑结构复杂性研究[D].北京:北京交通大学,2008.

[3]BONACICH P. Factoring and weighting approa-ches to status scores and clique identification[J].The Journal of Mathematical Sociology,1972,2(1):113-120.

[4]FREEMAN L C. Centrality in social networks conceptual clarification[J].Social Networks,1979(3):215-239.

[5]陈 勇,胡爱群,胡 骏,等.通信网中最重要节点的确定方法[J].高技术通讯,2004,14(1):21-24.

[6]谭跃进,吴 俊,邓宏钟.复杂网络中节点重要度评估的节点收缩方法[J].系统工程理论与实践,2006,26(11):79-83,102.

[7]高 洁.交通运输网络节点重要度评价体系研究[J].聊城大学学报:自然科学版,2010,23(3):92-95,110.

[8]ENRICO N, GUIDO P, PETER W. Finding the most vital node of a shortest path[J].Theoretical Computer Science,2003(1):167-177.

[9]LIU Y J, TAN Y. Complexity modeling and stability analysis of urban subway network:wuhan city case study[J]. Procedia-social and Behavioral Sciences,2013,96:1611-1621.

[10]李颖宏,王 力,尹怡欣.区域交通信号系统节点分析及优化策略研究[J].计算机应用,2010,30(4):1107-1109.

[11]王正武,况爱武,王贺杰.考虑级联失效的交通网络节点重要度测算[J].公路交通科技,2012,29(5):96-101.

[12]王建强,代磊磊,李 娅,等.基于交通流运行特征的城市干线关键交叉口判别方法[J].交通信息与安全,2013,31(3):49-52.

[13]管 青.区域交通信号控制与交通诱导协同理论与关键技术研究[D].长春:吉林大学,2009.

Study on the Identification Method of Hub Node in Urban Road Network

ZHENG Lili1,2,3)WANG Shiguang2)WANG Wei2)DING Tongqiang2)

(StateKeyLaboratoryofAutomobileSimulationandControl,JilinUniversity,Changchun130022,China)1)(CollegeofTransportation,JilinUniversity,Changchun130022,China)2)(JilinProvinceKeyLaboratoryofRoadTraffic,JilinUniversity,Changchun130022,China)3)

Identifying the key node of urban road network is an important technical problem in the current urban traffic control and emergency management. An evaluation index system of key node is raised, which includes the road network topology indicators and traffic flow main characteristics. The key node is identified by using a P-gray weighted correlation analysis method. At last, a road network in Changchun is used as a test area to validate the proposed approach compared with other ways. The result shows that the method is feasible and effective. Through further data fitting, the fitting formulas between the node importance degree and the related indicators are given.

traffic engineering; key node identification; complex network theory; principal component analysis; weighted gray correlational analysis

2015-03-10

*国家自然科学基金项目(批准号：51308249)、国家科技支撑计划(批准号：2014BAG03B03)、山东省省管企业科技创新项目(批准号：20122150251-5)资助

U491

10.3963/j.issn.2095-3844.2015.04.001

郑黎黎(1975- )：女，工学博士，副教授，主要研究领域为交通系统控制与优化理论