基于有向图的城市交通堵塞模型PPT课件

1、基于有向图的城市交通堵塞模型基于有向图的城市交通堵塞模型 Email: Tel:科院 广州地理研究所 曾宇怀第六届全国网络科学论坛第六届全国网络科学论坛 第二届全国混沌应用研讨会第二届全国混沌应用研讨会中国高等科学技术中心中国高等科学技术中心 2010.07.26-312010.07.26-310.前言：交通问题-经济全球化、城市化、工业化的普遍问题v城市化：自组织、耗散结构v经济物流化：资金流动-人员流-物流-经济流动；v交通扩展：v贸易扩展：1.城市交通问题进展v交通网络复杂性吸引了来自物理、数学、地理、工程、城v市规划、经济等不同领域的学者对其分析方法的研究。v

2、常用的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, comple

3、x networks,and other models for analyzing transportation network topologies NASA/CR-2005-213522, 2005.2.交通堵塞的因子v2.1 交通流组成：交通工具流、人流、物流v2.2 交通路网：技术网、实体网、空间地理网；v2.3 扰动因子：行为、车况、车流混合度、洪涝灾害；v2.4 交通控制：奥运、亚运单双日限行、单行线、绕行线；2.1交通流的主体运动（群集动力学基本模型）v 独立个体间有相互作用：自驱动（self-driven）v 有限信息：有限感知、有限智力v自组织（self-organizati

4、on）的复杂集体行为：v 同步（synchronization ）、结构性（structure） 、 集体智慧（group intelligence)v有交通指挥者（Controller）v具有一定的运动周期：周、月、年周期。2.2 交通网络特征：v技术网techntical networks：近代科技的产物：交通、通讯、制造业发展；v实体网real networks：城市交通网、铁路、航空网；v地理空间网spatial :欧几里得空间、非欧空间（航空网）；2.3 扰动因素v行为：个人驾驶技术、经验；v车况：保养、保险v车流混合度: BRT快速公交-公交优先，行人最后考虑；v内涝与养护：地下管

5、网对交通网络的侵袭、扰动-最后导致大部分地面交通网络的瘫痪。3. 城市交通网的复杂网络特征v无向图：随机图网、小世界网、无标度网v有向图：含权网v空间网：数值统计、地面物理参数模型； 工程模型。平 面 网Planar networks4.有向图-含权网模型克尼斯堡七桥模型4.1 广州市城市交通v反-柯尼斯堡图:4.2复杂网络的种类-按图类型来分2.2.S. Boccaletti et al. Physics Reports 424 (2006) 175 308a: 无向图无向图 b: 有向图有向图 c: 含权无向图含权无向图4.3有向图（有向图（Directed graph）v一个有向图G是指

6、节点对象组成的非空有限集V与不同节点间的有序对集合E共同组成的集合。 4.3.1 图的流量图的流量v在有向图模型中，我们定义“节点”为道路交叉口。任意两个节点（x、y）定义为一条单向街道。如果任意节点间有一条边，意味着它们之间相连或相通。相互连接的分布式节点组成一个交通网络。v流量f定义为以边edge为变量。即f(x、y)的值为边（x、y）的流量。当流量从s（sourece）开始，到t(terminal)结束时，满足科基霍夫流量定律：所有中间节点（不含s）的流量应等于流出量。即如有xV，有：v +(x)=yV: xyE (1)v (x)=yV: yxE （2）v S-t 满足下列： v f(x

7、,y) = f(z,x) (3)v y+ (x) z (x)4.3.2最大流量与最小流量定理最大流量与最小流量定理v我们用我们用v v（f f）标记为）标记为f f的值为的值为s s至至t t间的流量值：间的流量值：v c c（x,yx,y）是一个正整数值，称为）是一个正整数值，称为“边容量边容量”，即每条道路交通容量的，即每条道路交通容量的函数。函数。v已知已知X,YX,Y为为V V的两个子集，记为的两个子集，记为E E（X X、Y Y）为有向边）为有向边XYXY的集合，有：的集合，有：v E E（X X、Y Y）=xyE : xX yY=xyE : xX yY （4 4）v这就是这就是Fo

8、rdFord和和FulkersonFulkerson的最大流与最小割定理。的最大流与最小割定理。v v(f) c(x,yv(f) c(x,y) (5) (5)v xyE xyEv v(f) = c(x,y) = c(S, v(f) = c(x,y) = c(S,) (6) (6)v xS, y xS, y v利用（利用（5 5）（）（6 6）式，）式，EdmondEdmond和和KarpKarp设计了一个寻找最大流的设计了一个寻找最大流的增广算法增广算法，可以标记和找到可以标记和找到G G中的一个最大流量，为中的一个最大流量，为O(m)O(m)时间。时间。4.3.3. 流量变化流量变化v我们考

9、虑城市道路由于多种复杂因子发生阻塞，因此，如果整个网络运行正常，我们可以视为C1为C（x，y）的最大值，为一常数值，v根据美国公路容量手册（U.S. Highway Capacity Manual (HCM 2000),一旦某个路段发生阻塞至中断，把阻塞路段的交通容量值c（xi,yj）视为函数变量，即为时间t的根指数函数: v （7）4.4 结果:v 由（6）和（7），有： v（v(f)） b = C(x,y) + f(t) = C1 + f(t ) v 以及 （v(f)）b = f( t) . (8) 其中：C(x,y)=C(x,y)-C(xi,yj)v C1, b为常系数, t为时间变量。

10、4.5. 实证分析v图1：纵坐标左边为交通效率E，右边为全程停留时间D(即t)；横坐标为流量值-V；C为交通容量. 当流量V小于350时，V与E成正比例；大于350时，呈反比例。当V远大于C值，t 趋于正无穷，E趋于0，表明交通发生堵塞。广州市荔湾区某街区道路交通网络图广州市荔湾区某街区道路交通流量参数 Edge(IdEdge(Id) ) Vetex(x,yVetex(x,y) ) Flow(x,yFlow(x,y) ) Capacity Capacity (x,y(x,y) )Degree(x,yDegree(x,y) )0 00 0 1 12 21 11 13 32 22 21 12 23

11、 329291 13 32 24.5.1 结果分析v 如图1所示，我们假设边E(14,15)发生阻塞，此时流量v(f) 在时间窗内按负指数规律由大变小，最后趋为0。下面做一简单分析：v因为由（1），（2），（3）式流量守恒定律有：v f(3,14)+f(10,14)=f(14,15)+f(14,21)v当f(14,15)0 时，f(13,14),f(10,14)将快速下降，获得f; 而f(14,21)快速增加，获得一个v(f) （ v(f) 0）.v 根据以上变化规律，此时利用深先算法花费O(m)时间（m为节点数）可以找到E(14,15)路段，然后，经过对路面拓扑关系和状态的判别，再把最终路面

12、变化的信息转换到空间数据库中记录。5结结 论论v本文提出了一种动态的有向含权网络网络模型，以及如何更新和采集的主要过程和解决算法；v交通堵塞的复杂性优待深入研究；v该模型不需要全局、同步采集数据，只需监控少量节点、枢纽数据。v提出一种复杂流量算法与模拟函数之间的扩展方方法。参考文献参考文献 v1. Dowling, R. (2006), Urban Arterial Speed-Flow Equations For Travel Demand Models. Proceedings of Transportation Research Board Conference, Texas, May

13、21 - 23 2006.v2. B.Bollobs,1998.Modern Graph Theory. Springer-Verlag New York,pp.68-72.v3M.H.Alsuwaiyel,1999. Algorithms Techniques and Analysis .World Scientific PublishingvCo,pp.260-269.v4 Catherine Dibble, Philip G. Feldman, 2003.The GeoGraph 3D Computational Laboratory. The 8th International Com

14、mand and Control Research and Technology Symposium.v5 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 vComputing, Orlando.v6 Jiang B., C. Claramunt, 2004.Topological Analysis of Urban

15、 Street Networks, Envirenment and Planning B, pp.151-161.v7 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.v8 A.Hosseini Naveh,et.al.,2006.Studying the effec

16、t of traffic elements by GIS. Map World Forum,Hyderabad, India.v9 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.v10 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-1