基于有向圖的城市交通堵塞模型PPT課件

1、基于有向圖的城市交通堵塞模型基于有向圖的城市交通堵塞模型 Email: Tel:科院 廣州地理研究所 曾宇懷第六屆全國網(wǎng)絡(luò)科學(xué)論壇第六屆全國網(wǎng)絡(luò)科學(xué)論壇 第二屆全國混沌應(yīng)用研討會(huì)第二屆全國混沌應(yīng)用研討會(huì)中國高等科學(xué)技術(shù)中心中國高等科學(xué)技術(shù)中心 2010.07.26-312010.07.26-310.前言：交通問題-經(jīng)濟(jì)全球化、城市化、工業(yè)化的普遍問題v城市化：自組織、耗散結(jié)構(gòu)v經(jīng)濟(jì)物流化：資金流動(dòng)-人員流-物流-經(jīng)濟(jì)流動(dòng)；v交通擴(kuò)展：v貿(mào)易擴(kuò)展：1.城市交通問題進(jìn)展v交通網(wǎng)絡(luò)復(fù)雜性吸引了來自物理、數(shù)學(xué)、地理、工程、城v市規(guī)劃、經(jīng)濟(jì)等不同領(lǐng)域的學(xué)者對(duì)其分析方法的研究。v

2、常用的6種方法進(jìn)行了詳細(xì)的比較分析： 地理信息系統(tǒng)（Geographic information system） 、圖論（Graph theory） 、復(fù)雜網(wǎng)絡(luò)（Complex networks）、 數(shù)學(xué)規(guī)劃（Mathematical programming） 、模擬仿真（Simulation） 、基于智能體模型（Agent-based modeling）1. 元胞自動(dòng)機(jī)（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 交通路網(wǎng)：技術(shù)網(wǎng)、實(shí)體網(wǎng)、空間地理網(wǎng)；v2.3 擾動(dòng)因子：行為、車況、車流混合度、洪澇災(zāi)害；v2.4 交通控制：奧運(yùn)、亞運(yùn)單雙日限行、單行線、繞行線；2.1交通流的主體運(yùn)動(dòng)（群集動(dòng)力學(xué)基本模型）v 獨(dú)立個(gè)體間有相互作用：自驅(qū)動(dòng)（self-driven）v 有限信息：有限感知、有限智力v自組織（self-organizati

4、on）的復(fù)雜集體行為：v 同步（synchronization ）、結(jié)構(gòu)性（structure） 、 集體智慧（group intelligence)v有交通指揮者（Controller）v具有一定的運(yùn)動(dòng)周期：周、月、年周期。2.2 交通網(wǎng)絡(luò)特征：v技術(shù)網(wǎng)techntical networks：近代科技的產(chǎn)物：交通、通訊、制造業(yè)發(fā)展；v實(shí)體網(wǎng)real networks：城市交通網(wǎng)、鐵路、航空網(wǎng)；v地理空間網(wǎng)spatial :歐幾里得空間、非歐空間（航空網(wǎng)）；2.3 擾動(dòng)因素v行為：個(gè)人駕駛技術(shù)、經(jīng)驗(yàn)；v車況：保養(yǎng)、保險(xiǎn)v車流混合度: BRT快速公交-公交優(yōu)先，行人最后考慮；v內(nèi)澇與養(yǎng)護(hù)：地下管

5、網(wǎng)對(duì)交通網(wǎng)絡(luò)的侵襲、擾動(dòng)-最后導(dǎo)致大部分地面交通網(wǎng)絡(luò)的癱瘓。3. 城市交通網(wǎng)的復(fù)雜網(wǎng)絡(luò)特征v無向圖：隨機(jī)圖網(wǎng)、小世界網(wǎng)、無標(biāo)度網(wǎng)v有向圖：含權(quán)網(wǎng)v空間網(wǎng)：數(shù)值統(tǒng)計(jì)、地面物理參數(shù)模型； 工程模型。平 面 網(wǎng)Planar networks4.有向圖-含權(quán)網(wǎng)模型克尼斯堡七橋模型4.1 廣州市城市交通v反-柯尼斯堡圖:4.2復(fù)雜網(wǎng)絡(luò)的種類-按圖類型來分2.2.S. Boccaletti et al. Physics Reports 424 (2006) 175 308a: 無向圖無向圖 b: 有向圖有向圖 c: 含權(quán)無向圖含權(quán)無向圖4.3有向圖（有向圖（Directed graph）v一個(gè)有向圖G是指

6、節(jié)點(diǎn)對(duì)象組成的非空有限集V與不同節(jié)點(diǎn)間的有序?qū)螮共同組成的集合。 4.3.1 圖的流量圖的流量v在有向圖模型中，我們定義“節(jié)點(diǎn)”為道路交叉口。任意兩個(gè)節(jié)點(diǎn)（x、y）定義為一條單向街道。如果任意節(jié)點(diǎn)間有一條邊，意味著它們之間相連或相通。相互連接的分布式節(jié)點(diǎn)組成一個(gè)交通網(wǎng)絡(luò)。v流量f定義為以邊edge為變量。即f(x、y)的值為邊（x、y）的流量。當(dāng)流量從s（sourece）開始，到t(terminal)結(jié)束時(shí)，滿足科基霍夫流量定律：所有中間節(jié)點(diǎn)（不含s）的流量應(yīng)等于流出量。即如有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）標(biāo)記為）標(biāo)記為f f的值為的值為s s至至t t間的流量值：間的流量值：v c c（x,yx,y）是一個(gè)正整數(shù)值，稱為）是一個(gè)正整數(shù)值，稱為“邊容量邊容量”，即每條道路交通容量的，即每條道路交通容量的函數(shù)。函數(shù)。v已知已知X,YX,Y為為V V的兩個(gè)子集，記為的兩個(gè)子集，記為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設(shè)計(jì)了一個(gè)尋找最大流的設(shè)計(jì)了一個(gè)尋找最大流的增廣算法增廣算法，可以標(biāo)記和找到可以標(biāo)記和找到G G中的一個(gè)最大流量，為中的一個(gè)最大流量，為O(m)O(m)時(shí)間。時(shí)間。4.3.3. 流量變化流量變化v我們考

9、慮城市道路由于多種復(fù)雜因子發(fā)生阻塞，因此，如果整個(gè)網(wǎng)絡(luò)運(yùn)行正常，我們可以視為C1為C（x，y）的最大值，為一常數(shù)值，v根據(jù)美國公路容量手冊(cè)（U.S. Highway Capacity Manual (HCM 2000),一旦某個(gè)路段發(fā)生阻塞至中斷，把阻塞路段的交通容量值c（xi,yj）視為函數(shù)變量，即為時(shí)間t的根指數(shù)函數(shù): v （7）4.4 結(jié)果: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為常系數(shù), t為時(shí)間變量。

10、4.5. 實(shí)證分析v圖1：縱坐標(biāo)左邊為交通效率E，右邊為全程停留時(shí)間D(即t)；橫坐標(biāo)為流量值-V；C為交通容量. 當(dāng)流量V小于350時(shí)，V與E成正比例；大于350時(shí)，呈反比例。當(dāng)V遠(yuǎn)大于C值，t 趨于正無窮，E趨于0，表明交通發(fā)生堵塞。廣州市荔灣區(qū)某街區(qū)道路交通網(wǎng)絡(luò)圖廣州市荔灣區(qū)某街區(qū)道路交通流量參數(shù) 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 結(jié)果分析v 如圖1所示，我們假設(shè)邊E(14,15)發(fā)生阻塞，此時(shí)流量v(f) 在時(shí)間窗內(nèi)按負(fù)指數(shù)規(guī)律由大變小，最后趨為0。下面做一簡單分析：v因?yàn)橛桑?），（2），（3）式流量守恒定律有：v f(3,14)+f(10,14)=f(14,15)+f(14,21)v當(dāng)f(14,15)0 時(shí)，f(13,14),f(10,14)將快速下降，獲得f; 而f(14,21)快速增加，獲得一個(gè)v(f) （ v(f) 0）.v 根據(jù)以上變化規(guī)律，此時(shí)利用深先算法花費(fèi)O(m)時(shí)間（m為節(jié)點(diǎn)數(shù)）可以找到E(14,15)路段，然后，經(jīng)過對(duì)路面拓?fù)潢P(guān)系和狀態(tài)的判別，再把最終路面

12、變化的信息轉(zhuǎn)換到空間數(shù)據(jù)庫中記錄。5結(jié)結(jié) 論論v本文提出了一種動(dòng)態(tài)的有向含權(quán)網(wǎng)絡(luò)網(wǎng)絡(luò)模型，以及如何更新和采集的主要過程和解決算法；v交通堵塞的復(fù)雜性優(yōu)待深入研究；v該模型不需要全局、同步采集數(shù)據(jù)，只需監(jiān)控少量節(jié)點(diǎn)、樞紐數(shù)據(jù)。v提出一種復(fù)雜流量算法與模擬函數(shù)之間的擴(kuò)展方方法。參考文獻(xiàn)參考文獻(xiàn) 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