交通群體運(yùn)動(dòng)-中國(guó)高等科學(xué)技術(shù)中心

1、基于有向圖的城市交通堵塞模型,Email: yuwaizeng@gdas.ac.cn Tel: 13533553784,中科院 廣州地理研究所,曾宇懷,第六屆全國(guó)網(wǎng)絡(luò)科學(xué)論壇 第二屆全國(guó)混沌應(yīng)用研討會(huì)中國(guó)高等科學(xué)技術(shù)中心 2010.07.26-31,0.前言：交通問(wèn)題----經(jīng)濟(jì)全球化、城市化、工業(yè)化的普遍問(wèn)題,城市化：自組織、耗散結(jié)構(gòu)經(jīng)濟(jì)物流化：資金流動(dòng)->人員流->物流->經(jīng)濟(jì)流動(dòng)；交通擴(kuò)展：貿(mào)易擴(kuò)

2、展：,1.城市交通問(wèn)題進(jìn)展,交通網(wǎng)絡(luò)復(fù)雜性吸引了來(lái)自物理、數(shù)學(xué)、地理、工程、城市規(guī)劃、經(jīng)濟(jì)等不同領(lǐng)域的學(xué)者對(duì)其分析方法的研究。常用的6種方法進(jìn)行了詳細(xì)的比較分析： 地理信息系統(tǒng)（Geographic information system） 、圖論（Graph theory） 、復(fù)雜網(wǎng)絡(luò)（Complex networks）、 數(shù)學(xué)規(guī)劃（Mathematical programming） 、模擬仿真（Simulatio

3、n） 、基于智能體模型（Agent-based modeling）[1]. 元胞自動(dòng)機(jī)（Cellular Automata）,[1]. Kuby M, Tierney S, Roberts T, et al. A comparison of geographic information systems, complex networks,and other models for analyzing transportati

4、on network topologies NASA/CR-2005-213522, 2005.,2.交通堵塞的因子,2.1 交通流組成：交通工具流、人流、物流2.2 交通路網(wǎng)：技術(shù)網(wǎng)、實(shí)體網(wǎng)、空間地理網(wǎng)；2.3 擾動(dòng)因子：行為、車況、車流混合度、洪澇災(zāi)害；2.4 交通控制：奧運(yùn)、亞運(yùn)單雙日限行、單行線、繞行線；,2.1交通流的主體運(yùn)動(dòng)（群集動(dòng)力學(xué)基本模型）,獨(dú)立個(gè)體間有相互作用：自驅(qū)動(dòng)（self-driven） 有限信息：有

5、限感知、有限智力自組織（self-organization）的復(fù)雜集體行為： 同步（synchronization ）、結(jié)構(gòu)性（structure） 、 集體智慧（group intelligence)有交通指揮者（Controller）具有一定的運(yùn)動(dòng)周期：周、月、年周期。,2.2 交通網(wǎng)絡(luò)特征：,技術(shù)網(wǎng)techntical networks：近代科技的產(chǎn)物：交通、通訊、制造業(yè)發(fā)展；實(shí)體網(wǎng)real networks：城

6、市交通網(wǎng)、鐵路、航空網(wǎng)；地理空間網(wǎng)spatial ~:歐幾里得空間、非歐空間（航空網(wǎng)）；,2.3 擾動(dòng)因素,行為：個(gè)人駕駛技術(shù)、經(jīng)驗(yàn)；車況：保養(yǎng)、保險(xiǎn)車流混合度: BRT快速公交-公交優(yōu)先，行人最后考慮；內(nèi)澇與養(yǎng)護(hù)：地下管網(wǎng)對(duì)交通網(wǎng)絡(luò)的侵襲、擾動(dòng)---最后導(dǎo)致大部分地面交通網(wǎng)絡(luò)的癱瘓。,3. 城市交通網(wǎng)的復(fù)雜網(wǎng)絡(luò)特征,無(wú)向圖：隨機(jī)圖網(wǎng)、小世界網(wǎng)、無(wú)標(biāo)度網(wǎng)有向圖：含權(quán)網(wǎng)空間網(wǎng)：數(shù)值統(tǒng)計(jì)、地面物理參數(shù)模型；

7、 工程模型。,平 面 網(wǎng)Planar networks,,4.有向圖-含權(quán)網(wǎng)模型,,,克尼斯堡七橋模型,4.1 廣州市城市交通,反-柯尼斯堡圖:,,,,4.2復(fù)雜網(wǎng)絡(luò)的種類-按圖類型來(lái)分[2].,[2].S. Boccaletti et al. Physics Reports 424 (2006) 175 –308,,a: 無(wú)向圖 b: 有向圖

8、 c: 含權(quán)無(wú)向圖,4.3有向圖（Directed graph）,一個(gè)有向圖G是指節(jié)點(diǎn)對(duì)象組成的非空有限集V與不同節(jié)點(diǎn)間的有序?qū)螮共同組成的集合。,4.3.1 圖的流量,在有向圖模型中，我們定義“節(jié)點(diǎn)”為道路交叉口。任意兩個(gè)節(jié)點(diǎn)（x、y）定義為一條單向街道。如果任意節(jié)點(diǎn)間有一條邊，意味著它們之間相連或相通。相互連接的分布式節(jié)點(diǎn)組成一個(gè)交通網(wǎng)絡(luò)。流量f定義為以邊edge為變量。即f(x、y)的值為邊（x、y）的

9、流量。當(dāng)流量從s（sourece）開(kāi)始，到t(terminal)結(jié)束時(shí)，滿足科基霍夫流量定律：所有中間節(jié)點(diǎn)（不含s）的流量應(yīng)等于流出量。即如有x∈V，有： ?+(x)={y∈V: xy∈E} (1) ?¯(x)={y∈V: yx∈E} （2）

10、 S->t 滿足下列： ∑f(x,y) = ∑f(z,x) (3) y∈?+ (x) z∈?¯ (x),4.3.2最大流量與最小流量定理,我們用v（f）標(biāo)記為f的值為s至t間的流量值： c（x,y）是一個(gè)正整數(shù)值，稱為“邊容量”，即每條道路交通容量的函數(shù)。

11、已知X,Y為V的兩個(gè)子集，記為E（X、Y）為有向邊XY的集合，有： E（X、Y）={xy∈E : x∈X y∈Y} （4）這就是Ford和Fulkerson的最大流與最小割定理。 v(f) ≦ ∑c(x,y) (5) xy∈E

12、 v(f) = ∑c(x,y) = c(S,?) (6) x∈S, y∈? 利用（5）（6）式，Edmond和Karp設(shè)計(jì)了一個(gè)尋找最大流的增廣算法，可以標(biāo)記和找到G中的一個(gè)最大流量，為O(m³)時(shí)間。,4.3.3. 流量變化,我們考慮城市道路由于多種復(fù)雜因子發(fā)生阻塞，因此，如果整個(gè)網(wǎng)絡(luò)運(yùn)行正常，我們可以視為C1為C

13、（x，y）的最大值，為一常數(shù)值，根據(jù)美國(guó)公路容量手冊(cè)（U.S. Highway Capacity Manual (HCM 2000),一旦某個(gè)路段發(fā)生阻塞至中斷，把阻塞路段的交通容量值c（xi,yj）視為函數(shù)變量，即為時(shí)間t的根指數(shù)函數(shù):,（7）,4.4 結(jié)果:,由（6）和（7），有： （v(f)） b = C’(x,y) + f(t) = C1 + f(t ) 以及 （⊿v(f)）b =

14、f(⊿ t) …. (8) 其中：C’(x,y)=C(x,y)-C(xi,yj) C1, b為常系數(shù), t為時(shí)間變量。,4.5. 實(shí)證分析,圖1：縱坐標(biāo)左邊為交通效率E，右邊為全程停留時(shí)間D(

15、即t)；橫坐標(biāo)為流量值-V；C為交通容量. 當(dāng)流量V小于350時(shí)，V與E成正比例；大于350時(shí)，呈反比例。當(dāng)V遠(yuǎn)大于C值，t 趨于正無(wú)窮，E趨于0，表明交通發(fā)生堵塞。,廣州市荔灣區(qū)某街區(qū)道路交通網(wǎng)絡(luò)圖,廣州市荔灣區(qū)某街區(qū)道路交通流量參數(shù),4.5.1 結(jié)果分析,如圖1所示，我們假設(shè)邊E(14,15)發(fā)生阻塞，此時(shí)流量⊿v(f) 在時(shí)間窗內(nèi)按負(fù)指數(shù)規(guī)律由大變小，最后趨為0。下面做一簡(jiǎn)單分析：因?yàn)橛桑?），（2），（3）式流量守恒定律有：

16、 f(3,14)+f(10,14)=f(14,15)+f(14,21)當(dāng)f(14,15)?0 時(shí)，f(13,14),f(10,14)將快速下降，獲得－⊿f; 而f(14,21)快速增加，獲得一個(gè)⊿v(f) （ ⊿v(f) >0）. 根據(jù)以上變化規(guī)律，此時(shí)利用深先算法花費(fèi)O(m)時(shí)間（m為節(jié)點(diǎn)數(shù)）可以找到E(14,15)路段，然后，經(jīng)過(guò)對(duì)路面拓?fù)潢P(guān)系和狀態(tài)的判別，再把最終路面變化的信息轉(zhuǎn)換到空間數(shù)據(jù)庫(kù)中記錄。,5．結(jié)

17、 論,本文提出了一種動(dòng)態(tài)的有向含權(quán)網(wǎng)絡(luò)網(wǎng)絡(luò)模型，以及如何更新和采集的主要過(guò)程和解決算法；交通堵塞的復(fù)雜性優(yōu)待深入研究；該模型不需要全局、同步采集數(shù)據(jù)，只需監(jiān)控少量節(jié)點(diǎn)、樞紐數(shù)據(jù)。提出一種復(fù)雜流量算法與模擬函數(shù)之間的擴(kuò)展方方法。,,Thanks a lot !,參考文獻(xiàn),[1]. [2]. B.Bollobás,1998.Modern Graph Theory. Springer-Verlag New York,pp

18、.68-72.[3]M.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

19、 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 B

20、ased 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 Sema

21、ntic 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,Hy

22、derabad, 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, Beijin

23、g.[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 Geog

24、raphical Network Modeling，地理信息科學(xué)，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. (E