第六届全国网络科学论坛 第二届全国混沌应用研讨会 中国高等科学技术中心 2010.07.26-31 基于有向图的城市交通堵塞模型 曾宇怀 中科院 广州地理研究所 Email: yuwaizeng@gdas.ac.cn Tel: 13533553784

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]. a: 无向图 b: 有向图 c: 含权无向图 [2].S. Boccaletti et al. Physics Reports 424 (2006) 175 –308

4.3有向图（Directed graph） 一个有向图G是指节点对象组成的非空有限集V与不同节点间的有序对集合E共同组成的集合。

4.3.1 图的流量 在有向图模型中，我们定义“节点”为道路交叉口。任意两个节点（x、y）定义为一条单向街道。如果任意节点间有一条边，意味着它们之间相连或相通。相互连接的分布式节点组成一个交通网络。 流量f定义为以边edge为变量。即f(x、y)的值为边（x、y）的流量。当流量从s（sourece）开始，到t(terminal)结束时，满足科基霍夫流量定律：所有中间节点（不含s）的流量应等于流出量。即如有x∈V，有： Ґ+(x)={y∈V: xy∈E} (1) Ґ¯(x)={y∈V: yx∈E} （2） S->t 满足下列： ∑f(x,y) = ∑f(z,x) (3) y∈Ґ+ (x) z∈Ґ¯ (x)

4.3.2最大流量与最小流量定理 我们用v（f）标记为f的值为s至t间的流量值： c（x,y）是一个正整数值，称为“边容量”，即每条道路交通容量的函数。 已知X,Y为V的两个子集，记为E（X、Y）为有向边XY的集合，有： E（X、Y）={xy∈E : x∈X y∈Y} （4） 这就是Ford和Fulkerson的最大流与最小割定理。 v(f) ≦ ∑c(x,y) (5) xy∈E v(f) = ∑c(x,y) = c(S,Ŝ) (6) x∈S, 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，表明交通发生堵塞。

广州市荔湾区某街区道路交通网络图

广州市荔湾区某街区道路交通流量参数 Edge(Id) Vetex(x,y) Flow(x,y) Capacity (x,y) Degree(x,y) 1 2 3 …… 29

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．结 论 本文提出了一种动态的有向含权网络网络模型，以及如何更新和采集的主要过程和解决算法； 交通堵塞的复杂性优待深入研究； 5．结 论 本文提出了一种动态的有向含权网络网络模型，以及如何更新和采集的主要过程和解决算法； 交通堵塞的复杂性优待深入研究； 该模型不需要全局、同步采集数据，只需监控少量节点、枢纽数据。 提出一种复杂流量算法与模拟函数之间的扩展方方法。

Thanks a lot !

参考文献 [1]. [2]. B.Bollobás,1998.Modern Graph Theory. Springer-Verlag New York,pp.68-72. [3]M.H.Alsuwaiyel,1999. Algorithms Techniques and Analysis .World Scientific Publishing Co,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]陆锋, 申排伟, 张明波,2004, Feature-based Object Oriented Geographical Network Modeling，地理信息科学，Vol.6,No.3, pp.72-78 [12] 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.