上海理工大学研究生课程(论文类)试卷(网络交通控制原理)
研究生课程(论文类)试卷
2012/2013 学年第 2 学期 课程名称: 课程代码: 论文题目: 学生姓名: 专业﹑学号: 学院: 管理学院 网络交通控制原理
课程(论文)成绩: 课程(论文)评分依据(必填) :
任课教师签字: 日期: 年 月 日
课程(论文)题目: 内容:
摘要:城市交通网络是一种复杂的网络结合体,是混合型网络。利用
复杂网络理论为基本研究工具, 综合考虑实际交通流的动态变化特性, 选取节点度、节点介数及交叉口高峰小时流量为评价指标,基于 FCM 模糊聚类方法,确定交通网络中的关键节点;以关键节点为参考点, 按照一定的子区划分原则对“面控”的控制子区进行划分。通过一简 单案例,说明本文所提出的子区划分方法的可行性与实用性。
关键词:区域交通信号控制,复杂网络,FCM,关键节点,子区划分 一 引言
城市交通网络是一种复杂的网络结合体,是混合型网络[1]。区域交通信号控制系统 在缓解城市交通拥堵、提升交通运行效益等方面发挥了重要的作用。 “面控”中的一个重 要问题是如何合理确定交通网络中的关键节点及如何利用关键节点确定“面控”中的信 号控制子区。著名的 SCOOT 系统依据交叉口交通流量、交叉口间距等因素依据人工判 定来选择关键节点并划分控制子区建立系统控制结构。类似地,SCATS 系统的关键控 制节点、信号控制子区等系统结构的建立同样依赖于人工经验,采用无计算模型和理论 支撑的方法。 国内外相关研究人员、 学者等也对区域交通信号控制系统中关键节点的选取和控制 子区的划分进行了较深入的研究。尚德申等提出了一种以静态区域控制为基础,通过对 城市交通拥堵进行分类,采取不同的判断标准,实现动态分区控制的方法[2];段后利等 建立了基于超图表示的城市路网模型,并设计了相应的超图划分算法,通过对超图的分 割来实现交通控制子区的动态划分[3];卢凯等利用交叉口关联度量化分析方法,给出了
相邻交叉口关联度与多交叉口组合关联度的计算公式, 通过定义控制子区划分方案的解 集空间、约束条件与评价准则,建立了协调控制子区划分模型[4]。 本文以复杂网络理论为基础研究工具,综合考虑实际交通流的动态变化特性,利用 FCM 模糊聚类方法,提出了一种新的交通信号控制子区划分方法。
二
基于 FCM 模糊聚类的 Hub 点选取方法研究
城市交通网络可以抽象为复杂赋权网络,交叉口抽象为节点,路段抽象为边,边的
权重可以是交叉口间的距离或路段流量。理论分析证明,复杂交通赋权网络具有无标度 (free-scale)网络特性,即对于随机性攻
击的强鲁棒性和选择性攻击的结构脆性[5]。
2.1 无标度网络简介
Barabasi 和 Albert 于 1999 年首次提出了无标度网络[6]。 无标度网络具有严重的异质 性,其各节点之间的连接状况(度数)具有严重的不均匀分布性:网络中少数称之为 Hub 点的节点拥有极其多的连接,而大多数节点只有很少量的连接。少数 Hub 点对无 标度网络的运行起着主导的作用。从广义上说,无标度网络的无标度性是描述大量复杂 系统整体上严重不均匀分布的一种内在性质。 现实中的交通网、电话网和 Internet 都是无标度网络,在这种网络中,存在拥有大 量连接的集散节点,比如交通枢纽就是这样的节点。
2.2 节点重要性评价指标
复杂网络的非同质拓扑结构,决定了网络中每个节点的重要程度是不同的。本文选 取节点度、节点介数及交叉口高峰小时流量作为交叉口节点重要度的评价指标。这三个 评价指标既能反映复杂网络的拓扑结构特性, 又能体现现实复杂交通网络的动态变化特 性。 2.2.1 节点度
节点度,即与节点连接的边数,也是与该节点建立连接的节点数[7]。设复杂网络中 有 n 个节点, k 为节点度,则节点 i 的度为:
Cd (i) k (i)
(1)
2.2.2 节点介数 节点介数定义为网络中节点对最短路径中经过节点 i 的个数占所有最短路径数的比 例。 g st ,i 表示节点对 s 和 t 最短路径经过 i 点的路径数,nst 表示节点 s 和节点 t 之间存在 用 所有路径的路径数,则节点 i 的节点介数 Cb (i ) 的计算公式如下:
Cb (i) 2 g st ,i nst
s t
n(n 1)
(2)
2.2.3 交叉口高峰小时流量 交叉口高峰小时流量表征了交叉口节点的通行量, 反映了交通网络的交通流动态变 化特性。
2.3 基于 FCM 模糊聚类的 Hub 点选取方法
FCM 算法是一种基于划分的聚类算法,它的思想就是使得被划分到同一族的对象 之间相似度最大,而不同簇之间的相似度最小。它在普通 C 均值(HCM)的基础之上 做一定的改进,普通 C 均值算法对于数据的划分是硬性的,而 FCM 则是一种柔性的模 糊划分,它通过引入隶属度函数来表示每个数据属于不同类别的程度,对数据进行软划 分。 设 n 个样本数据集合为 X x1 , x2 ,, xn ( R m ) , xk xk1 , xk 2 ,, xkm ( R m ) 为样本 xk
T
的 特 征 向 量 ; c(2 c n) 是 要 将 数 据 样 本 分 成 的 类 别 数 目 ; 第 i 类 的 聚 类 原 型 为
pi pi1 , pi 2 ,, pim ( R m ) , 则 P p1 , p2 ,, pc ( R mc ) 构 成 一 聚 类 原 型 矩 阵 ;
T
U ( ik )en ( Ren ) 是隶属度矩阵,其中 ik 表示样本 xk 对于聚类原型 pi 的隶属程度,且
ik [0,1] ,则基于目标函
数的模糊聚类分析可以表示为:
n c min J b (U , P) ( ik )b ( dik ) 2 , b [1, ) k 1 i 1 c s.t. 1, k 1, 2,, n ik i 1
(3)
其中, b 为模糊化程度指数,是一个控制算法的柔性参数,如果 b 过大,则算法的 聚类效果较差, 反之, FCM 算法接近传统的硬 C 均值算法, 的取值范围通常为 [1.5, 2.5] , b 一般取 2.0; dik 表示样本 xk 与聚类原型 pi 之间相异度的度量,通常可以取为欧氏距离, 即:
dik
(x
j 1
m
kj
pij ) 2
(4)
三
交通信号控制子区划分研究
3.1 控制子区划分原则
当确定好交通网络中的 Hub 点后,接下来以 Hub 点为参考点,进行区域交通信号 控制子区的划分,控制子区划分遵循以下原则: (1)干线协调控制下的交叉口宜划分于同一交通信号控制子区内; (2)每一个信号控制子区内的交叉口数量不宜大于 10 个; (3)各个信号控制子区内的交通流量应当平衡; (4)假设节点 i 被选为复杂交通网络的 Hub 点,其周边节点 r 相对于节点 i 的重要 程度的计算公式如下:
I (r | i )
P ( r ,i ) j 1
pj
(5)
其中,P(r , i) 表示节点 r 至节点 i 的路径集,p j 表示节点 r 至节点 i 的路径集中第 j 条 路径的长度, 是比例因子( 1 ) ,文中 取为 2.0。
3.2 控制子区划分算法
本文所提出的区域交通信号控制系统的交通信号控制子区划分算法步骤如下: Step1: 参数设置: 设置类别数为 c , 取模糊化程度指数 b 2.0 , 迭代终止阈值 103 , 迭代计数器 t 1 ,产生初始聚类中心 P(t ) ; Step2:计算隶属度矩阵 U (t ) :
ik
1 d d ik j 1 jk
c 2
(6)
b 1
Step3:更新聚类原型矩阵 P (t 1) :
pi(t 1)
n k 1 n k 1
(t ) b ik
xk
2
(7)
(t ) b ik
Step4: 如果 P ( t ) P ( t 1)
pij(t ) pij(t 1) ,则算法停止,并输出划分矩阵 U 和
m c i 1 j 1
聚类原型矩阵 P ,否则令 t t 1 ,转向步骤 2; Step5:选定 Hub 点,并根据控制子区划分原则进行信号控制子区划分。
四
案例
我们选定杨浦区某区域为本文的研究区域,如下图 1 所示。三个节点重要度评价指
标如下表 1 所示,由于欠缺交叉口高峰小时流量数据,此项数据基于假设,但并不妨碍 本文总体研究目标。
图 1 研究路网 表 1 节点重要度评价指标 节点 节点号 节点度 介数 1 2 3 4 5 6 7 8 9 10 4 4 4 3 4 3 4 4 3 3 流量 高峰小时 节点号 节点度 介数 11 12 13 14 15 16 17 18 19 20 3 3 3 3 3 3 4 3 4 4 流量 节点 高峰小时
0.0245 0.0238 0.0193 0.0113 0.0243 0.0160 0.0105 0.0
282 0.0263 0.0165
909 1319 727 680 4346 2898 2749 724 4265 3110
0.0187 0.0176 0.0062 0.0090 0.0141 0.0069 0.0253 0.0058 0.0067 0.0051
1754 2566 2009 379 1199 616 919 1199 2086 248
21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
4 3 4 3 3 3 3 4 4 4 4 3 3 4 4 4 5 3 4 3 3 3 3
0.0068 0.0130 0.0093 0.0277 0.0129 0.0055 0.0272 0.0294 0.0131 0.0033 0.0077 0.0122 0.0178 0.0078 0.0181 0.0213 0.0066 0.0035 0.0089 0.0095 0.0127 0.0152 0.0025
4513 4723 2454 2446 1688 4500 1846 556 3901 1948 1208 2019 482 659 4710 4780 2876 298 1173 1765 4105 577 215
44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
4 3 3 3 3 4 4 3 4 3 4 3 4 4 4 3 3 4 4 4 3 3 3
0.0078 0.0240 0.0008 0.0279 0.0219 0.0146 0.0173 0.0071 0.0137 0.0289 0.0164 0.0156 0.0069 0.0146 0.0187 0.0204 0.0118 0.0110 0.0297 0.0011 0.0266 0.0274 0.0239
844 3245 3658 3238 2254 2735 1481 3723 944 3433 917 1842 3128 3901 405 4646 3878 2433 2179 2233 1531 2542 2553
利用 FCM(Fuzzy Clustering Method)聚类方法,并在 MATLAB 中进行算法实现。 图 2 为聚类类别数目 c 3 时的三维图,其中类别 1 的聚类中心为(3.4689,0.0156,2351), 类别 2 的聚类中心为(3.4151,0.0151,4195),类别 3 的聚类中心为(3.6028,0.0144,767)。并 选取类别 2 中高峰小时流量大于 4000 的交叉口作为交通网络的 Hub 点, 分别为节点 5、
9、21、22、26、35、36、41 和 59 等 9 个节点,以此 9 个 Hub 点为基础对交通网络进 行交通信号控制子区的划分;子区划分结果如图 3 所示,共划分了 7 个信号控制子区。
5000
高 峰 小 时 流 量 ( 辆 /小 时 )
4000
3000
2000
1000
0 0.03 0.02 0.01 3.5 节点介数 0 3 节点度 4 5 4.5
图2
c=3 时的聚类图
图 3 信号控制子区划分结果
由图 3,路网共被划分为 7 个交通信号控制子区,节点 1、23、34、47、54 及 66 由于属于干线协调控制,并未划入任何信号控制子区之内;由图可见,信号控制子区划 分结果较为合理,具有较强的实用性。
五
结束语
本文尝试利用复杂网络理论为基本研究工具,综合考虑实际交通流的动态变化特
性,选取节点度、节点介数及交叉口高峰小时流量作为评价指标,并基于 FCM 模糊聚 类方法,确定交通网络中的关键节点(Hub 点) ;其次,以关键节点为参考点,按照一 定的子区划分原则对“面控”的控制子区进行了较为合理的划分。通过一简单案例,说明 了本文所提出的子区划分方法的可行性与实用性。 在对区域交通信号控制系统的信号控制子区划分和关键节点的选择上, 本文的研究 基本上还是处于静态分析阶段;后续研究中,在静态方法研究的基础上,实现关键节点 的动态选择和控制子区边缘的动态划分与合并, 实现根据实际道路交通状况自适应地调 节系统的控制结构,是下一步的研究重
点与难点。
参考文献
[1] 魏路. 基于复杂网络的区域交通信号控制系统优化研究[D]. 北京:北方工业大 学, 2012. [2] 尚德申, 石建军, 隋莉颖, 等. 交通区域动态划分及其控制研究[J]. 交通科技, 2007, 225:82-84. [3] 段后利, 李志恒, 张毅, 等. 交通控制子区动态划分模型[J]. 吉林大学学报(工学 版), 2009, 39(2):13-18. [4] 卢凯, 徐建闽, 李轶舜. 基于关联度分析的协调控制子区划分方法[J]. 华南理工
大学学报(自然科学版), 2009, 37(7):6-9,20. [5] 王力, 于欣宇, 李颖宏, 等. 基于 FCM 聚类的复杂交通网络节点重要性评估[J]. 交通运输系统工程与信息, 2010, 10 (6):169-173. [6] A L Barabasi, R Albert. Emergence of scaling in random networks [J].Science, 1999, 286: 173-175. [7] 荣莉莉, 郭天柱, 王建伟. 复杂网络节点中心性[J]. 上海理工大学学报, 2008, 30(3):227-230, 236.