梁坤,孙莉,罗建锋,戴权

(1.淮阴工学院管理工程学院,江苏淮安 223003;2.淮阴工学院研究生处,江苏淮安 223003)



基于故障传播有向图的交通拥堵传播研究∗

梁坤1,孙莉2,罗建锋1,戴权1

(1.淮阴工学院管理工程学院,江苏淮安 223003;2.淮阴工学院研究生处,江苏淮安 223003)

摘要:城市交通拥堵已成为亟需解的城市发展中的重大问题。文中将故障传播有向图方法应用于交通拥堵传播研究,提出了交通拥堵传播有向图模型和基于该模型的拥堵传播推理方法,并进行了基于K均值聚类的交叉口拥堵识别,为研究城市交通拥堵传播规律提供参考。

关键词:城市交通;交通拥堵;拥堵传播;有向图;交叉口;拥堵识别

近些年来,随着经济的快速发展和城市化、机动化的加快,交通需求增长和城市交通供给不足的矛盾不断扩大,中国城市普遍出现了交通拥堵问题。交通拥堵造成出行者出行成本增加、交通事故、空气和噪音污染等,严重影响城市的可持续发展,交通拥堵的缓解和预防成为城市迫切需要解决的难题之一。目前,人们对于城市道路交通拥堵传播规律缺乏足够、准确的认识,这导致交通拥堵的治理多采用事后疏导策略,实际缓解交通拥堵过程中存在一定的盲目性,缺乏有效的缓解与预防手段。物联网、智能交通和信息技术的不断发展为研究城市道路交通拥堵成因和传播规律提供了必要的实时交通数据条件,这使交通拥堵主动治理成为可能。交通拥堵传播规律的认识是主动交通拥堵治理的前提之一。

目前国内外对交通拥堵传播进行了一些研究:李树彬等运用改进的中观交通流模型研究了网络拓扑结构对交通拥堵的影响,分析了复杂网络上的交通传播动力学特征和传播规律;潘捷、龙建成等利用元胞传输模型研究了由突发性事件引起的交通拥堵传播特性;高自友应用微观与宏观相结合的方法建立了拥堵传播模型;谢琛等利用双随机转移矩阵提出了一个流量分配模型,并从级联反应角度分析了拥堵现象的传播过程;Shu-bin Li等利用双向网格对交通拥堵传播进行了分析;曾宇怀研究了基于有向图的城市交通堵塞模型;袁绍欣利用传染病模型分析了城市交通拥堵传播机理及其控制策略。从国内外现有研究成果来看,交通拥挤传播研究还处于起步阶段,尽管相关研究已经积极开展,但理论方法还有待进一步丰富和深入。

故障传播有向图方法在机械复杂系统的故障诊断中已被成功使用,并取得了良好效果。交通拥堵传播和机械复杂系统中部件故障影响传播存在一定的类似,故将故障传播有向图方法应用于城市道路拥堵传播研究,以准确认知城市交通拥堵传播规律,为城市交通拥堵的疏散和治理提供参考依据。

1 交通拥堵传播有向图模型

将城市交通路网视为一个大规模的提供给交通参与者的服务生产系统,其中各交叉口之间、路段之间及路段和交叉口的交通流量之间相互关联。在一个交叉口或路段的交通拥堵(即交叉口或路段故障)迅速传播到其他交叉口或路段的过程中,相应的交叉口和路段将产生大量交通流特征参数(流量、密度和速度等)的异常信息。交通拥堵传播推理系统必须利用这些信息产生一个精确的诊断结果,交通拥堵(故障)传播模型是表达交通系统拥堵动态传播的简单和有效的方法。使用两个交叉口之间的拥堵传播概率和时间间隔表示交通系统的动态特性。当出现交通拥堵征兆时,通过从拥堵报警开始反向搜索确定拥堵传播路径,同时使用交通波理论从拥堵源开始用于预报将要发生的拥堵路段和交叉口。

拥堵(故障)传播有向图可用于表示拥堵(故障)传播关系。交通拥堵传播有向图定义为TCPSDG ={V,E,D,Γ,Υ},其中:

(1)V节点集,且V≠0,表示路网中的交叉口。

(2)有向边集合E=(V×V),表示交叉口间的关联关系、反映路段上交通流信息,“关系对”分别表示每一路段的起始交叉口和终止交叉口,记为:

∂+:E→V(路段的起始交叉口)

∂-:E→V(路段的终止交叉口)

(3)D表示路网上的路段和交叉口采集的交通信息(流量、车速、检测器占有率等)。

(4)函数Γ:E→{+,0},其中Γ(ei)(ei∈E)称为路段的符号。用“+”表示拥堵在路段ei传播、“0”表示拥堵在路段ei不传播。

(5)函数Υ:v→{1,0,?}(?表示无采集交通信息交叉口),表示交叉口vj的交通状态:

式中:X为交叉口vj对应检测的交通特征值即流量、车速、检测器占有率等;ε为交叉口vj交通运行正常状态的阈值。

2 拥堵传播的推理

基于TCPSDG模型的故障传播推理是基于TCPSDG模型中的主要要素Υ(vj)的状态估算实现的,步骤如下:

(1)针对初始Υ(vj)的状态进行判断,分析潜在交通拥堵传播的路径集合。交通拥堵在路网上通过相容通道才能进行传播。在有向图SDG模型中,如果Υ(∂+ei)Γ(ei)Υ(∂-ei)=+,则该支路ei称为相容,由相容支路组成的路径称为相容通路。所以交通拥堵传播路径研究的是SDG图的最大相容子图,由有效节点和相容通路描述拥堵的传递关系。

(2)根据交叉口或路段当前检测信息估计的交通状态,分为交通运行畅通交叉口节点集合VN、拥堵交叉口节点集合VC。

(3)从检测的拥堵节点出发,沿交通流方向回溯,对其经过的路段ei,若Υ(∂+ei)Γ(ei)Υ(∂-ei)=0,则该路径不相容。将不相容路径截断,即构成最大相容子图。该最大相容子图即为交通拥堵传播路径。

3 交叉口拥堵识别

随着智能交通的发展,城市路网上布置的交通检测器越来越多,为城市道路交叉口交通状态识别提供了大量交通数据。运用无监督的K均值自动聚类技术,将道路交叉口交通拥堵状态看成一个特殊的分类问题,实现城市交叉口交通拥堵状态判别,得出Υ(vj)值,然后根据拥堵传播的推理即可得到拥堵传播路径。

3.1 聚类特征参数

国内外对于交通状态的识别进行了一些研究。20世纪60年代美国加利福尼亚州运输部开发的加州算法采用检测截面占有率进行交通状态识别;校准偏差算法采用交通量或占有率判别交通状态;双指数平滑算法采用速度、流量、占有率和密度三者之一进行交通拥堵判别;由加拿大Mc Master大学土木工程系开发的Mc Master算法采用速度和占有率识别交通状态。这里根据数据采集的方便性和可行性,选用速度、流量和占有率(时间占有率)作为交叉口聚类参数。

3.2 数据的采集与处理

如图1所示,采集各入口的速度、流量和占有率;vj表示第j个交叉口,vjn(n=1,2,…)表示第n个入口方向,vjns、vjnv、vjno分别表示j交叉口n入口的速度、流量和占有率;采集位置在离交叉口100 m处。对于信号控制交叉口,vjns、vjnv、vjno选用检测时刻t的前5个信号周期长度T内检测到的vjns、vjnv、vjno均值作为交叉口交通状态相似度的特征参数;对于非信号控制交叉口,采用检测时刻t的前5 min内检测到的vjns、vjnv、vjno均值作为交叉口交通状态相似度的特征参数。

图1 交叉口数据采集示意图(单位:m)

3.3 基于K均值聚类的交叉口拥堵识别

基于K均值聚类的交叉口拥堵识别的原理是聚类中的小样本事件是异常事件。在城市路网中,一般同时拥堵的交叉口数量较少,应用交叉口入口交通运行状态的相似度进行聚类,聚类簇中样本数少的类识为拥堵交叉口,拥堵传播方向为入口路段交通流反方向。输入为t时刻采集的交叉口各入口数据Xvj,输出为K个类C1,C2,…,CK。

算法流程如下:

(1)随机选择K个交叉口入口的数据作为初始聚类中心,令I=1,Cg(I),g=1,2,…,K。

(2)计算交叉口每个入口数据点与K个初始聚类中心的距离d[v-jn,Cg(I)](采用欧氏距离),其中j表示交叉口,n表示交叉口的入口,g表示初始聚类中心。如果满足d[v-jn,Cg(I)]=min{d[v-jn,Cg(I)],g=1,2,…,K},则vjn∈Cg。

(3)计算K各新的聚类中心:

(4)若Cg(I+1)≠Cg(I),g=1,2,…,K,则I =I+1,返回第2步;否则算法结束。

(5)找出最少样本的类Cg=min{Ng,g=1,2,…,K},vjn∈Cg。该类中的交叉口属于拥堵交叉口,入口方向为拥堵方向。

采用S.Ray等提出的在迭代过程中类内距离与类间距离的比值最小时的K作为确定最优K值的判断条件。

对识别出的拥堵交叉口vj的交通量特征值(流量、车速和检测器占有率)与该交叉口交通运行正常状态的阈值ε进行比较,确定vj的交通状态Υ(vj)值。同时确定该交叉口拥堵方向路段Γ(ei)值为“+”,非拥堵传播方向路段的Γ(ei)值为零,根据上文拥堵传播推理即可得到交通拥堵在城市路网中的传播路径。

4 结语

传统的拥堵事后疏导策略对缓解和预防交通拥堵的效果不佳,认知交通拥堵传播规律是交通拥堵主动治理的前提之一,而目前智能交通和信息技术的快速发展使研究交通拥堵主动治理方法成为可能。该文引入故障传播有向图方法研究交通拥堵传播规律,建立了城市路网交通拥堵传播有向图模型,提出了交叉口拥堵识别方法和拥堵传播的推理方法。该文尝试把复杂系统的故障诊断方法应用于交通拥堵传播研究,希望能抛砖引玉,使更多其他领域的方法应用到交通拥堵研究中。

参考文献:

[1]周堂.物联网背景下城市交通拥堵事前疏导研究[D].长沙:湖南大学,2014.

[2]李树彬,吴建军,高自友,等.基于复杂网络的交通拥堵与传播动力学分析[J].物理学报,2011,60(5).

[3]潘捷.城市交通拥堵的传播及处理[D].西安:长安大学,2014.

[4]龙建成.城市道路交通拥堵传播规律及消散控制策略研究[D].北京:北京交通大学,2009.

[5]Long J C,Gao Z Y,Ren H L,et al.Urban traffic congestion propagation and bottleneck identification[J].Science in China Series F:Information Sciences,2008,51(7).

[6]田聪.基于元胞传输模型的城市交通拥堵机理研究[D].武汉:华中科技大学,2012.

[7]高自友.城市交通拥堵传播规律与消散控制策略研究[J].上海理工大学学报,2011,33(6).

[8]谢琛,张晓东.城市交通拥堵产生与传播及其分析[A].2007第三届中国智能交通年会论文集[C].2007.

[9]Shu-bin Li,Bai-bai Fu,Jian-feng Zheng.Dynamic analysis of traffic state and congestion propagation on bidirectional grid network[J].Discrete Dynamics in Nature and Society,2013,2013.

[10]曾宇怀.基于有向图的城市交通堵塞模型[A].第六届全国网络科学论坛暨第二届全国混沌应用研讨会论文集[C].2010.

[11]袁绍欣.城市交通拥堵传播机理及其控制策略研究[D].西安:长安大学,2012.

[12]陈侃,李昌禧.故障传播有向图的故障定位研究[J].自动化仪表,2011,32(4).

[13]王伟,于达仁,赵辉,等.基于符号有向图模型的故障诊断方法[J].动力工程,2007,27(5).

[14]姜桂艳.道路交通状态判别技术与应用[M].北京:人民交通出版社,2004.

[15]毛保华,孙壮志,贾顺平,等.区域交通组织优化方法及实践研究[M].北京:人民交通出版社,2007.

[16]吴军强,梁军.基于图论的故障诊断技术及其发展[J].机电工程,2003,20(5).

收稿日期:2015-11-06

基金项目:∗国家青年科学基金项目(71403096);住房和城乡建设部项目(2013-K5-25、2013-R2-36);江苏省高校哲学社会科学研究指导项目(2012SJD630005)

中图分类号:U491.2

文献标志码:A

文章编号:1671-2668(2016)02-0047-03