基于有向图的城市交通堵塞模型.ppt
基于有向图的城市交通堵塞模型,Email:,中科院 广州地理研究所,曾宇怀,第六届全国网络科学论坛 第二届全国混沌应用研讨会中国高等科学技术中心,0.前言：交通问题-经济全球化、城市化、工业化的普遍问题,城市化：自组织、耗散结构经济物流化：资金流动-人员流-物流-经济流动；交通扩展：贸易扩展：,1.城市交通问题进展,交通网络复杂性吸引了来自物理、数学、地理、工程、城市规划、经济等不同领域的学者对其分析方法的研究。常用的6种方法进行了详细的比较分析：地理信息系统（Geographic information system）、图论（Graph theory）、复杂网络（Complex networks）、数学规划（Mathematical programming）、模拟仿真（Simulation）、基于智能体模型（Agent-based modeling）1.元胞自动机（Cellular Automata）,1.Kuby M,Tierney S,Roberts T,et al.A comparison of geographic information systems,complex networks,and other models for analyzing transportation network topologies NASA/CR-2005-213522,2005.,2.交通堵塞的因子,2.1 交通流组成：交通工具流、人流、物流2.2 交通路网：技术网、实体网、空间地理网；2.3 扰动因子：行为、车况、车流混合度、洪涝灾害；2.4 交通控制：奥运、亚运单双日限行、单行线、绕行线；,2.1交通流的主体运动（群集动力学基本模型）,独立个体间有相互作用：自驱动（self-driven）有限信息：有限感知、有限智力自组织（self-organization）的复杂集体行为：同步（synchronization）、结构性（structure）、集体智慧（group intelligence)有交通指挥者（Controller）具有一定的运动周期：周、月、年周期。,2.2 交通网络特征：,技术网techntical networks：近代科技的产物：交通、通讯、制造业发展；实体网real networks：城市交通网、铁路、航空网；地理空间网spatial:欧几里得空间、非欧空间（航空网）；,2.3 扰动因素,行为：个人驾驶技术、经验；车况：保养、保险车流混合度:BRT快速公交-公交优先，行人最后考虑；内涝与养护：地下管网对交通网络的侵袭、扰动-最后导致大部分地面交通网络的瘫痪。,3.城市交通网的复杂网络特征,无向图：随机图网、小世界网、无标度网有向图：含权网空间网：数值统计、地面物理参数模型；工程模型。,平 面 网Planar networks,4.有向图-含权网模型,克尼斯堡七桥模型,4.1 广州市城市交通,反-柯尼斯堡图:,4.2复杂网络的种类-按图类型来分2.,2.S.Boccaletti et al.Physics Reports 424(2006)175 308,a:无向图 b:有向图 c:含权无向图,4.3有向图（Directed graph）,一个有向图G是指节点对象组成的非空有限集V与不同节点间的有序对集合E共同组成的集合。,4.3.1 图的流量,在有向图模型中，我们定义“节点”为道路交叉口。任意两个节点（x、y）定义为一条单向街道。如果任意节点间有一条边，意味着它们之间相连或相通。相互连接的分布式节点组成一个交通网络。流量f定义为以边edge为变量。即f(x、y)的值为边（x、y）的流量。当流量从s（sourece）开始，到t(terminal)结束时，满足科基霍夫流量定律：所有中间节点（不含s）的流量应等于流出量。即如有xV，有：+(x)=yV:xyE(1)(x)=yV:yxE（2）S-t 满足下列：f(x,y)=f(z,x)(3)y+(x)z(x),最大流量与最小流量定理,我们用v（f）标记为f的值为s至t间的流量值：c（x,y）是一个正整数值，称为“边容量”，即每条道路交通容量的函数。已知X,Y为V的两个子集，记为E（X、Y）为有向边XY的集合，有：E（X、Y）=xyE:xX yY（4）这就是Ford和Fulkerson的最大流与最小割定理。v(f)c(x,y)(5)xyE v(f)=c(x,y)=c(S,)(6)xS,y 利用（5）（6）式，Edmond和Karp设计了一个寻找最大流的增广算法，可以标记和找到G中的一个最大流量，为O(m)时间。,4.3.3.流量变化,我们考虑城市道路由于多种复杂因子发生阻塞，因此，如果整个网络运行正常，我们可以视为C1为C（x，y）的最大值，为一常数值，根据美国公路容量手册（U.S.Highway Capacity Manual(HCM 2000),一旦某个路段发生阻塞至中断，把阻塞路段的交通容量值c（xi,yj）视为函数变量，即为时间t的根指数函数:,（7）,4.4 结果:,由（6）和（7），有：（v(f)）b=C(x,y)+f(t)=C1+f(t)以及（v(f)）b=f(t).(8)其中：C(x,y)=C(x,y)-C(xi,yj)C1,b为常系数,t为时间变量。,4.5.实证分析,图1：纵坐标左边为交通效率E，右边为全程停留时间D(即t)；横坐标为流量值-V；C为交通容量.当流量V小于350时，V与E成正比例；大于350时，呈反比例。当V远大于C值，t 趋于正无穷，E趋于0，表明交通发生堵塞。,广州市荔湾区某街区道路交通网络图,广州市荔湾区某街区道路交通流量参数,4.5.1 结果分析,如图1所示，我们假设边E(14,15)发生阻塞，此时流量v(f)在时间窗内按负指数规律由大变小，最后趋为0。下面做一简单分析：因为由（1），（2），（3）式流量守恒定律有：f(3,14)+f(10,14)=f(14,15)+f(14,21)当f(14,15)0 时，f(13,14),f(10,14)将快速下降，获得f;而f(14,21)快速增加，获得一个v(f)（v(f)0）.根据以上变化规律，此时利用深先算法花费O(m)时间（m为节点数）可以找到E(14,15)路段，然后，经过对路面拓扑关系和状态的判别，再把最终路面变化的信息转换到空间数据库中记录。,5结 论,本文提出了一种动态的有向含权网络网络模型，以及如何更新和采集的主要过程和解决算法；交通堵塞的复杂性优待深入研究；该模型不需要全局、同步采集数据，只需监控少量节点、枢纽数据。提出一种复杂流量算法与模拟函数之间的扩展方方法。,参考文献,1.Dowling,R.(2006),Urban Arterial Speed-Flow Equations For Travel Demand Models.Proceedings of Transportation Research Board Conference,Texas,May 21-23 2006.2.B.Bollobs,1998.Modern Graph Theory.Springer-Verlag New York,pp.68-72.3M.H.Alsuwaiyel,1999.Algorithms Techniques and Analysis.World Scientific PublishingCo,pp.260-269.4 Catherine Dibble,Philip G.Feldman,2003.The GeoGraph 3D Computational Laboratory.The 8th International Command and Control Research and Technology Symposium.5 Mark T.Elmore Thomas E.Potok and Frederick T.Sheldon,2003.Dynamic Data Fusion Using An Ontology-Based Software Agent System.Proceedings of the IIIS Agent Based Computing,Orlando.6 Jiang B.,C.Claramunt,2004.Topological Analysis of Urban Street Networks,Envirenment and Planning B,pp.151-161.7 I.Budak Arpinar,et.al,2004.Geospatial Ontology Development and Semantic Analytics.Handbook of Geographic Information Science.Eds:J.P.Wilson and A.S.Fotheringham,Blackwell Publishing.8 A.Hosseini Naveh,et.al.,2006.Studying the effect of traffic elements by GIS.Map World Forum,Hyderabad,India.9 Zhang Linguang,2006.Implement and Optimization Research of GIS Network Analysis Algorithms for Large Amounts of Data,Graudate Dissertation,Graduate University of Chinese Academy of Sciences,Beijing.10 W.Aiello,F.Chung,L.Lu,2000.Random graph model for massive graphs,Proceedings of the Thirty-Second Annual ACM symposium on Theory of Computing,pp.171-180.11 Frauke Heinzle,Karl-Heinrich Anders,and Monika Sester,2006.M.Pattern Recognition in Road Networks on the Example of Circular Road Detection.Raubal et al.(Eds.):GIScience,LNCS 4197,Springer-Verlag Berlin Heidelberg,pp.153 167.,Thanks a lot!,
