元胞自動(dòng)機(jī)交通流模型

1、第六章元胞自動(dòng)機(jī)元胞自動(dòng)機(jī)交通流模型交通流模型n本章主要內(nèi)容本章主要內(nèi)容1 元胞自動(dòng)機(jī)理論元胞自動(dòng)機(jī)理論2 元胞自動(dòng)機(jī)交通流模型元胞自動(dòng)機(jī)交通流模型詳見：詳見：賈斌，高自友，基于元胞自動(dòng)賈斌，高自友，基于元胞自動(dòng)機(jī)的交通系統(tǒng)建模與模擬，科機(jī)的交通系統(tǒng)建模與模擬，科學(xué)出版社，學(xué)出版社，2007-10 相關(guān)文獻(xiàn)：相關(guān)文獻(xiàn)：nNagel and Schreckenberg. A Cellular automaton model for freeway traffieJournal of Physics(France)，1992n鄭英力等交通流元胞自動(dòng)機(jī)模型綜述公路交通科鄭英力等交通流元胞自動(dòng)機(jī)模型綜

2、述公路交通科技技2006,23(1): 110115n孫躍等基于元胞自動(dòng)機(jī)原理的微觀交通仿真模型重慶孫躍等基于元胞自動(dòng)機(jī)原理的微觀交通仿真模型重慶大學(xué)學(xué)報(bào)大學(xué)學(xué)報(bào)(自然科學(xué)版自然科學(xué)版)2005 n熊桂林熊桂林, 黃悅元胞自動(dòng)機(jī)在混合交通仿真中的應(yīng)用系黃悅元胞自動(dòng)機(jī)在混合交通仿真中的應(yīng)用系統(tǒng)工程統(tǒng)工程2006 n狄宣基于元胞自動(dòng)機(jī)的快速路仿真建模與交通流優(yōu)化分狄宣基于元胞自動(dòng)機(jī)的快速路仿真建模與交通流優(yōu)化分析同濟(jì)大學(xué)碩士學(xué)位論文析同濟(jì)大學(xué)碩士學(xué)位論文2008.3 nS Maerivoet, B De Moor，Cellular automata models of road trafficPh

3、ysics Reports 419 (2005) 1 64n教學(xué)目的：了解初等元胞自動(dòng)機(jī)的基本概念，元胞自動(dòng)機(jī)的基本概念，掌握元胞自動(dòng)機(jī)交通流模型的建立元胞自動(dòng)機(jī)交通流模型的建立方法，掌握NS交交通流模型通流模型的特點(diǎn)、適用條件及其仿真。 n重點(diǎn)： NS交通流模型交通流模型n難點(diǎn)： NS交通流模型的交通流模型的仿真1 元胞自動(dòng)機(jī)理論元胞自動(dòng)機(jī)理論n一、什么是元胞自動(dòng)機(jī)一、什么是元胞自動(dòng)機(jī)n元胞自動(dòng)機(jī)（元胞自動(dòng)機(jī)（Cellular Automata，CA）是一種時(shí)空離散）是一種時(shí)空離散的局部動(dòng)力學(xué)模型，是研究復(fù)雜系統(tǒng)的一種典型方法，特的局部動(dòng)力學(xué)模型，是研究復(fù)雜系統(tǒng)的一種典型方法，特別適合用于空

4、間復(fù)雜系統(tǒng)的時(shí)空動(dòng)態(tài)模擬研究。別適合用于空間復(fù)雜系統(tǒng)的時(shí)空動(dòng)態(tài)模擬研究。n元胞自動(dòng)機(jī)不是由嚴(yán)格定義的物理方程或函數(shù)確定，而是元胞自動(dòng)機(jī)不是由嚴(yán)格定義的物理方程或函數(shù)確定，而是用一系列模型構(gòu)造的用一系列模型構(gòu)造的規(guī)則規(guī)則構(gòu)成。凡是滿足這些規(guī)則的模型構(gòu)成。凡是滿足這些規(guī)則的模型都可以算作是元胞自動(dòng)機(jī)模型。因此，元胞自動(dòng)機(jī)是一類都可以算作是元胞自動(dòng)機(jī)模型。因此，元胞自動(dòng)機(jī)是一類模型的總稱，或者說是一個(gè)方法框架。模型的總稱，或者說是一個(gè)方法框架。n在在CA模型中，散布在規(guī)則格網(wǎng)模型中，散布在規(guī)則格網(wǎng) (Lattice Grid)中中的每一元胞的每一元胞(Cell)取有限的離散狀態(tài)，遵循同樣的取有限的離

5、散狀態(tài)，遵循同樣的作用規(guī)則，依據(jù)確定的局部規(guī)則作同步更新。大作用規(guī)則，依據(jù)確定的局部規(guī)則作同步更新。大量元胞通過簡(jiǎn)單的相互作用而構(gòu)成動(dòng)態(tài)系統(tǒng)的量元胞通過簡(jiǎn)單的相互作用而構(gòu)成動(dòng)態(tài)系統(tǒng)的演演化化。nCA模型的特點(diǎn)：時(shí)間、空間、狀態(tài)都離散，每個(gè)模型的特點(diǎn)：時(shí)間、空間、狀態(tài)都離散，每個(gè)變量只取有限多個(gè)狀態(tài)，且其狀態(tài)改變的規(guī)則在變量只取有限多個(gè)狀態(tài)，且其狀態(tài)改變的規(guī)則在時(shí)間和空間上都是局部的。時(shí)間和空間上都是局部的。 二、初等元胞自動(dòng)機(jī)n初等元胞自動(dòng)機(jī)是狀態(tài)集S只有兩個(gè)元素s1，s2，即狀態(tài)個(gè)數(shù)k=2，鄰居半徑r=1的一維元胞自動(dòng)機(jī)。由于在S中具體采用什么符號(hào)并不重要，它可取 0，1，-1，1，靜止，運(yùn)

6、動(dòng) 等等，重要的是S所含的符號(hào)個(gè)數(shù)，通常我們將其記為 0，1。此時(shí)，鄰居集N的個(gè)數(shù)2r=2，局部映射f：S3S可記為:111(,)ttttiiiiSf SS S二、初等元胞自動(dòng)機(jī)n初等元胞自動(dòng)機(jī)是狀態(tài)集S只有兩個(gè)元素s1，s2，即狀態(tài)個(gè)數(shù)k=2，鄰居半徑r=1的一維元胞自動(dòng)機(jī)。由于在S中具體采用什么符號(hào)并不重要，它可取 0，1，-1，1，靜止，運(yùn)動(dòng) 等等，重要的是S所含的符號(hào)個(gè)數(shù)，通常我們將其記為 0，1。此時(shí)，鄰居集N的個(gè)數(shù)2r=2，局部映射f：S3S可記為:111(,)ttttiiiiSf SS S由于只有0、1兩種狀態(tài)，所以函數(shù)f共有28=256種狀態(tài)。t1111101011000010

7、10001000t+101001 100S. Wolfram的初等元胞自動(dòng)機(jī)的初等元胞自動(dòng)機(jī) 256種初等初等CA規(guī)則對(duì)給定初值及規(guī)則對(duì)給定初值及規(guī)則 f，可通過計(jì)算機(jī)得到，可通過計(jì)算機(jī)得到N步以后的演化結(jié)果步以后的演化結(jié)果 t111110101100011010001000 t+100001110000011000011100001110000111000101101100111010001rule 1rule 2rule 3rule 4rule 184rule 255rule 256nThree centuries ago science was transformed by the dr

8、amatic new idea that rules based on mathematical equations could be used to describe the natural world. My purpose in this book is to initiate another such transformation, and to introduce a new kind of science that is based on the much more general types of rules that can be embodied in simple comp

9、uter programs. 詳見：詳見：A New Kind of ScienceFree online access:http:/ 詳見：詳見：A New Kind of ScienceFree online access:http:/ 元胞自動(dòng)機(jī)交通流模型元胞自動(dòng)機(jī)交通流模型n一、第一、第184號(hào)規(guī)則號(hào)規(guī)則n特別注意：特別注意：第第184號(hào)規(guī)則號(hào)規(guī)則01020304050607080901000102030405060708090100特別注意：特別注意：第第184號(hào)規(guī)則號(hào)規(guī)則車輛行駛規(guī)則為：黑色元胞表示被一輛車占據(jù)，白色表示無車，若前方格子有車，則停止。若前方為空，則前進(jìn)一格。t111

10、110101100011010001000t+1101110001992年，德國學(xué)者Nagel和Schreckenberg在第184號(hào)規(guī)則的基礎(chǔ)上提出了一維交通流CA模型，即，NS 模型（或NaSch模型） 二、二、NS 模型模型n在第在第184號(hào)規(guī)則的基礎(chǔ)上，號(hào)規(guī)則的基礎(chǔ)上，1992年，德國學(xué)者年，德國學(xué)者Nagel和和Schreckenberg提出了一維交通流提出了一維交通流CA模型，模型，即，即，NS 模型（或模型（或NaSch模型）模型）nNagel and Schreckenberg. A Cellular automaton model for freeway traffieJou

11、rnal of Physics(France)，1992 nCA模型最基本的組成包括四個(gè)部分模型最基本的組成包括四個(gè)部分:元胞元胞(cell )、元胞空間元胞空間(lattice)、鄰域、鄰域(neighbor)及更新規(guī)則及更新規(guī)則(rule)。nNS模型是一個(gè)隨機(jī)模型是一個(gè)隨機(jī)CA交通流模型，每輛車的狀態(tài)都交通流模型，每輛車的狀態(tài)都由它的速度和位置所表示，其狀態(tài)按照以下演化規(guī)則由它的速度和位置所表示，其狀態(tài)按照以下演化規(guī)則并行更新并行更新 ： na）加速過程： nb）安全剎車過程： nc）隨機(jī)慢化過程： （以隨機(jī)慢化概率p） nd）位置更新：nnnxxvm ax(1, 0)nnvvmin(,

12、1)nnnvvdmaxmin(1,)nnvvv其中：L-車輛長度7.5m1nnndxxLNS模型的演化規(guī)則：1）加速: 司機(jī)總是期望以最大的速度行駛2）安全剎車: 為避免與前車碰撞3）隨機(jī)慢化（以隨機(jī)慢化概率p）:由于不確定因素n a) 過度剎車n b) 道路條件變化n c) 心理因素n d) 延遲加速4）位置更新:車輛前進(jìn)a）加速過程）加速過程 b）安全剎車過程）安全剎車過程 c）隨機(jī)慢化過程）隨機(jī)慢化過程（以隨機(jī)慢化概率（以隨機(jī)慢化概率p）d）位置更新）位置更新max2v例：設(shè)n在在NS 模型的基礎(chǔ)上，又陸續(xù)地提出了一系列一維模型的基礎(chǔ)上，又陸續(xù)地提出了一系列一維CA交通模型，如交通模型，

13、如TT、BJH、VDR、FI等等模型；模型；n雙車道雙車道CA交通模型：交通模型：STNS模型模型n機(jī)非混合機(jī)非混合CA模型：模型： CCA模型模型n城市路網(wǎng)城市路網(wǎng)CA二維二維模型：模型： BML、CTM模型模型Los Alamos National Laboratory： TRANSIMS (TRansportation ANalysis SIMulation System) 近年國際上出現(xiàn)的一門近年國際上出現(xiàn)的一門新的交叉學(xué)科新的交叉學(xué)科 交通物理學(xué)交通物理學(xué)B.S.Kerner, Springer 2004 n“幽靈式交通堵塞幽靈式交通堵塞” （“phantom” or “ghost”

14、 traffic jams）的現(xiàn)象早在）的現(xiàn)象早在1975年就由年就由Treiterer 和和 Myers 通過航拍圖像發(fā)現(xiàn)。通過航拍圖像發(fā)現(xiàn)。n直到直到1992年由德國學(xué)者年由德國學(xué)者Nagel 和和 Schreckenberg 用元胞自動(dòng)機(jī)（用元胞自動(dòng)機(jī)（CA）交通流模型才加以成功再現(xiàn)）交通流模型才加以成功再現(xiàn)和模擬解釋。和模擬解釋。n Nagel and Schreckenberg. A Cellular automaton model for freeway traffieJournal of Physics(France)，1992高速公路自發(fā)形高速公路自發(fā)形成的堵塞成的堵塞幽靈堵塞

15、幽靈堵塞（ghost jam）、）、時(shí)走時(shí)停（時(shí)走時(shí)停（stop-and-go wave）航拍圖，J.Treiterer，1975年條件：n隨機(jī)慢化概率p；n密度=13.3veh/km/lan（0.1） =20veh/km/lan（0.15） =33veh/km/lan（0.25）n車輛長度7.5m；道路長度L=7.5m120=900mn速度：1 7.5m/s=27km/h； 2 27.5m/s=54km/h； 3 37.5m/s=81km/h； 4 47.5m/s=108km/h； 5 57.5m/s=135km/h；隨機(jī)慢化概率p=0.2；密度=13.3veh/km/lan（0.1）； 第

16、5秒第10秒第20秒第40秒7.5m隨機(jī)慢化概率p=0.2；密度=20veh/km/lan（0.15）；初始隨機(jī)7.5m隨機(jī)慢化概率p=0.2；密度=27veh/km/lan（0.2）； 初始均勻分布7.5m隨機(jī)慢化概率p=0.2；密度=33veh/km/lan（0.25）； 7.5mn交通流交通流CA模型的主要優(yōu)點(diǎn)：模型的主要優(yōu)點(diǎn)：n（1）模型簡(jiǎn)單，特別易于在計(jì)算機(jī)上實(shí)現(xiàn)。）模型簡(jiǎn)單，特別易于在計(jì)算機(jī)上實(shí)現(xiàn)。n（2）能夠再現(xiàn)各種復(fù)雜的交通現(xiàn)象，反映交通）能夠再現(xiàn)各種復(fù)雜的交通現(xiàn)象，反映交通流特性。在模擬過程中人們通過考察元胞狀態(tài)的流特性。在模擬過程中人們通過考察元胞狀態(tài)的變化，不僅可以得到每

17、一輛車在任意時(shí)刻的速度、變化，不僅可以得到每一輛車在任意時(shí)刻的速度、位移以及車頭時(shí)距等參數(shù)描述交通流的微觀特性，位移以及車頭時(shí)距等參數(shù)描述交通流的微觀特性，還可以得到平均速度、密度、流量等參數(shù)，呈現(xiàn)還可以得到平均速度、密度、流量等參數(shù)，呈現(xiàn)交通流的宏觀特性。交通流的宏觀特性。n（3）能夠再現(xiàn)單車道、多車道以及路網(wǎng)的交通）能夠再現(xiàn)單車道、多車道以及路網(wǎng)的交通流建模；機(jī)動(dòng)車和非機(jī)動(dòng)車交通流的建模流建模；機(jī)動(dòng)車和非機(jī)動(dòng)車交通流的建模 三、多車道三、多車道CA模型模型n與單車道模型相比，多車道模型增加了換車道規(guī)與單車道模型相比，多車道模型增加了換車道規(guī)則。則。nNagel 等在單車道等在單車道NS模型

18、的基礎(chǔ)上，又提出了多模型的基礎(chǔ)上，又提出了多車道模型。在該模型中，在各條車道上行駛的車車道模型。在該模型中，在各條車道上行駛的車輛要遵守輛要遵守NS規(guī)則，在進(jìn)行車道變換時(shí)還要滿足車規(guī)則，在進(jìn)行車道變換時(shí)還要滿足車道變換規(guī)則道變換規(guī)則(lane-changing rules)。 該模型的車道變換規(guī)則如下該模型的車道變換規(guī)則如下:n(1) 如果如果vmaxgap,且且gapleftgap，則從右車道變換，則從右車道變換至左車道。至左車道。n(2) 如果如果 vmaxgap-voffset,且且 vmaxgapright-voffset，則，則從左車道變換至右車道。從左車道變換至右車道。n(3) 如果如果vbackgapleft，則，則vright=gapleft(禁止右車道的車禁止右車道的車輛超過左車道車輛輛超過左車道車輛)。n四、網(wǎng)絡(luò)四、網(wǎng)絡(luò)CA模型模型n1992年，Biham,Middleton和Levine等利用元胞自動(dòng)機(jī)設(shè)計(jì)了一種簡(jiǎn)單的二維元胞自動(dòng)機(jī)模型(BML模型)來模擬城市網(wǎng)絡(luò)的交通流現(xiàn)象，研究交通阻塞問題。模擬結(jié)果表明當(dāng)車輛密度大于某一臨界值時(shí)，將會(huì)發(fā)生阻塞。nBML模型簡(jiǎn)單直觀：有一個(gè)NxN的方形點(diǎn)陣，N是點(diǎn)陣的邊長，每個(gè)格點(diǎn)可以有一輛由南向北行駛的車輛，或者有一輛由東向西行駛的車輛，或者沒有車輛占據(jù)。在每一奇數(shù)時(shí)間步，南北向的車輛可以向前