元胞自动机交通流模型.复习进程.ppt

《元胞自动机交通流模型.复习进程.ppt》由会员分享，可在线阅读，更多相关《元胞自动机交通流模型.复习进程.ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章元胞自动机元胞自动机交通流模型交通流模型(mxng)(mxng)第一页，共33页。n本章主要本章主要(zhyo)内容内容n1 元胞自动机理论元胞自动机理论n2 元胞自动机交通流模型元胞自动机交通流模型详见：详见：贾斌，高自友，基于元胞自动贾斌，高自友，基于元胞自动机的交通系统建模与模拟，机的交通系统建模与模拟，科科学出版社，学出版社，2007-10 第二页，共33页。相关相关(xinggun)文献：文献：nNagel and Schreckenberg.A Cellular automaton model for freeway traffieJournal of Physics(Fra

2、nce)，1992n郑英力等交通流元胞自动机模型综述公路交通科技郑英力等交通流元胞自动机模型综述公路交通科技(kj)2006,23(1):110115n孙跃等基于元胞自动机原理的微观交通仿真模型重庆大学孙跃等基于元胞自动机原理的微观交通仿真模型重庆大学学报学报(自然科学版自然科学版)2005 n熊桂林熊桂林,黄悦元胞自动机在混合交通仿真中的应用系统工黄悦元胞自动机在混合交通仿真中的应用系统工程程2006 n狄宣基于元胞自动机的快速路仿真建模与交通流优化分析狄宣基于元胞自动机的快速路仿真建模与交通流优化分析同济大学硕士学位论文同济大学硕士学位论文2008.3 nS Maerivoet,B De

3、Moor，Cellular automata models of road trafficPhysics Reports 419(2005)1 64第三页，共33页。n教学目的：了解初等元胞自动机的基本概念，掌握元胞自动机交通流模型的建立方法，掌握NS交通流模型的特点、适用条件及其仿真(fn zhn)。n重点：NS交通流模型n难点：NS交通流模型的仿真(fn zhn)第四页，共33页。1 元胞自动机理论元胞自动机理论(lln)n一、什么是元胞自动机一、什么是元胞自动机n元胞自动机（元胞自动机（Cellular Automata，CA）是一种时空离散的局部动力学模）是一种时空离散的局部动力学模型

4、，是研究复杂系统的一种典型方法，型，是研究复杂系统的一种典型方法，特别适合用于空间复杂系统的时空动特别适合用于空间复杂系统的时空动态模拟研究。态模拟研究。n元胞自动机不是由严格定义的物理方元胞自动机不是由严格定义的物理方程或函数确定，而是用一系列模型构程或函数确定，而是用一系列模型构造的规则构成。凡是满足这些规则的造的规则构成。凡是满足这些规则的模型都可以算作是元胞自动机模型。模型都可以算作是元胞自动机模型。因此，元胞自动机是一类模型的总称，因此，元胞自动机是一类模型的总称，或者说是一个或者说是一个(y)方法框架。方法框架。第五页，共33页。n在在CA模型中，散布在规则格网模型中，散布在规则格

5、网(Lattice Grid)中的每中的每一元胞一元胞(Cell)取有限的离散状态，遵循同样取有限的离散状态，遵循同样(tngyng)的作用规则，依据确定的局部规则作同步更新。大量元的作用规则，依据确定的局部规则作同步更新。大量元胞通过简单的相互作用而构成动态系统的演化。胞通过简单的相互作用而构成动态系统的演化。nCA模型的特点：时间、空间、状态都离散，每个变量模型的特点：时间、空间、状态都离散，每个变量只取有限多个状态，且其状态改变的规则在时间和空间只取有限多个状态，且其状态改变的规则在时间和空间上都是局部的。上都是局部的。第六页，共33页。二、初等(chdng)元胞自动机n初等元胞自动机是

6、状态集S只有两个元素s1，s2，即状态个数k=2，邻居半径r=1的一维元胞自动机。由于在S中具体采用什么符号并不重要，它可取 0，1，-1，1，静止，运动(yndng)等等，重要的是S所含的符号个数，通常我们将其记为 0，1。此时，邻居集N的个数2r=2，局部映射f：S3S可记为:第七页，共33页。二、初等(chdng)元胞自动机n初等元胞自动机是状态集S只有两个元素s1，s2，即状态个数k=2，邻居半径(bnjng)r=1的一维元胞自动机。由于在S中具体采用什么符号并不重要，它可取 0，1，-1，1，静止，运动 等等，重要的是S所含的符号个数，通常我们将其记为 0，1。此时，邻居集N的个数2

7、r=2，局部映射f：S3S可记为:第八页，共33页。由于只有(zhyu)0、1两种状态，所以函数f共有28=256种状态。t111110101100001010001000t+101001100S.Wolfram的初等的初等(chdng)元胞自动机元胞自动机 第九页，共33页。256种初等(chdng)CA规则对给定初值及规则对给定初值及规则 f，可通过，可通过(tnggu)计算机得到计算机得到N步以后的演化步以后的演化结果结果 t111110101100011010001000t+10000111000001100001110000111000011100010110110011101000

8、1rule1rule2rule3rule4rule184rule255rule256第十页，共33页。nThree centuries ago science was transformed by the dramatic 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 ki

9、nd of science that is based on the much more general types of rules that can be embodied in simple computer programs.详见：详见：A New Kind of ScienceFree online access:http:/ New Kind of ScienceFree online access:http:/ 元胞自动机交通流模型元胞自动机交通流模型(mxng)n一、第一、第184号规则号规则(guz)n特别注意：第特别注意：第184号规则号规则(guz)第十四页，共33页。特

10、别注意：第特别注意：第184号规则号规则车辆行驶车辆行驶(xngsh)规则为：黑色元胞表示被一辆规则为：黑色元胞表示被一辆车占据，白色表示无车，若前方格子有车，则停车占据，白色表示无车，若前方格子有车，则停止。若前方为空，则前进一格。止。若前方为空，则前进一格。t111110101100011010001000t+1101110001992年，德国学者Nagel和Schreckenberg在第184号规则的基础(jch)上提出了一维交通流CA模型，即，NS 模型（或NaSch模型）第十五页，共33页。二、二、NS 模型模型在第在第184号规则的基础上，号规则的基础上，1992年，德国学者年，德

11、国学者(xuzh)Nagel和和Schreckenberg提出了一提出了一维交通流维交通流CA模型，即，模型，即，NS 模型（或模型（或NaSch模型）模型）Nagel and Schreckenberg.A Cellular automaton model for freeway traffieJournal of Physics(France)，1992 CA模型最基本的组成包括四个部分模型最基本的组成包括四个部分:元胞元胞(cell)、元胞空间、元胞空间(lattice)、邻域、邻域(neighbor)及更新规则及更新规则(rule)。第十六页，共33页。nNS模型是一个随机模型是一个随

12、机CA交通流模型，每辆车的状态都交通流模型，每辆车的状态都由它的速度和位置所表示，其状态按照由它的速度和位置所表示，其状态按照(nzho)以下以下演化规则并行更新演化规则并行更新：na）加速过程：）加速过程：nb）安全刹车过程：）安全刹车过程：nc）随机慢化过程：）随机慢化过程：n （以随机慢化概率（以随机慢化概率p）nd）位置更新：）位置更新：其中(qzhng)：L-车辆长度7.5m第十七页，共33页。NS模型(mxng)的演化规则：1）加速:司机总是期望以最大的速度(sd)行驶2）安全刹车:为避免与前车碰撞3）随机慢化（以随机慢化概率p）:由于不确定因素 a)过度刹车 b)道路条件变化 c

13、)心理因素 d)延迟加速4）位置更新:车辆前进第十八页，共33页。a）加速过程 b）安全刹车过程 c）随机慢化过程（以随机慢化概率p）d）位置(wi zhi)更新例：设第十九页，共33页。n在在NS 模型的基础上，又陆续模型的基础上，又陆续(lx)地提出了一系列地提出了一系列一维一维CA交通模型，如交通模型，如TT、BJH、VDR、FI等模型；等模型；n双车道双车道CA交通模型：交通模型：STNS模型模型n机非混合机非混合CA模型：模型：CCA模型模型n城市路网城市路网CA二维模型：二维模型：BML、CTM模型模型Los Alamos National Laboratory：TRANSIMS(

14、TRansportation ANalysis SIMulation System)第二十页，共33页。近年国际上出现近年国际上出现(chxin)的一门新的的一门新的交叉学科交叉学科 交通物理学交通物理学B.S.Kerner,Springer 2004 第二十一页，共33页。n“幽灵式交通堵塞幽灵式交通堵塞”（“phantom”or“ghost”traffic jams）的现象早在）的现象早在1975年就由年就由Treiterer 和和 Myers 通过航拍图像发现。通过航拍图像发现。n直到直到1992年由德国学者年由德国学者(xuzh)Nagel 和和 Schreckenberg 用元胞自动

15、机（用元胞自动机（CA）交通流模）交通流模型才加以成功再现和模拟解释。型才加以成功再现和模拟解释。n Nagel and Schreckenberg.A Cellular automaton model for freeway traffieJournal of Physics(France)，1992第二十二页，共33页。高速公路高速公路(o s n l)自发形自发形成的堵塞成的堵塞幽灵堵塞幽灵堵塞（ghost jam）、）、时走时停（时走时停（stop-and-go wave）航拍(hn pi)图，J.Treiterer，1975年第二十三页，共33页。条件：随机慢化(mn hu)概率p；

16、密度=13.3veh/km/lan（0.1）=20veh/km/lan（0.15）=33veh/km/lan（0.25）车辆长度7.5m；道路长度L=7.5m120=900m速度：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；第二十四页，共33页。随机(su j)慢化概率p=0.2；密度=13.3veh/km/lan（0.1）；第5秒第10秒第20秒第40秒7.5m第二十五页，共33页。随机(su j)慢化概率p=0.2；密度=20veh/km/lan（0.15）；初始

17、(ch sh)随机7.5m第二十六页，共33页。随机慢化概率(gil)p=0.2；密度=27veh/km/lan（0.2）；初始(ch sh)均匀分布7.5m第二十七页，共33页。随机慢化概率(gil)p=0.2；密度=33veh/km/lan（0.25）；7.5m第二十八页，共33页。n交通流交通流CA模型的主要优点：模型的主要优点：n（1）模型简单，特别）模型简单，特别(tbi)易于在计算机上实现。易于在计算机上实现。n（2）能够再现各种复杂的交通现象，反映交通流特性。）能够再现各种复杂的交通现象，反映交通流特性。在模拟过程中人们通过考察元胞状态的变化，不仅可以在模拟过程中人们通过考察元胞

18、状态的变化，不仅可以得到每一辆车在任意时刻的速度、位移以及车头时距等得到每一辆车在任意时刻的速度、位移以及车头时距等参数描述交通流的微观特性，还可以得到平均速度、密参数描述交通流的微观特性，还可以得到平均速度、密度、流量等参数，呈现交通流的宏观特性。度、流量等参数，呈现交通流的宏观特性。n（3）能够再现单车道、多车道以及路网的交通流建模；）能够再现单车道、多车道以及路网的交通流建模；机动车和非机动车交通流的建模机动车和非机动车交通流的建模第二十九页，共33页。三、多车道三、多车道(chdo)CA模型模型与单车道与单车道(chdo)模型相比，多车道模型相比，多车道(chdo)模型增加了换车道模型

19、增加了换车道(chdo)规则。规则。Nagel 等在单车道等在单车道(chdo)NS模型的基础上，模型的基础上，又提出了多车道又提出了多车道(chdo)模型。在该模型中，模型。在该模型中，在各条车道在各条车道(chdo)上行驶的车辆要遵守上行驶的车辆要遵守NS规则，在进行车道规则，在进行车道(chdo)变换时还要满足变换时还要满足车道车道(chdo)变换规则变换规则(lane-changing rules)。第三十页，共33页。该模型的车道变换该模型的车道变换(binhun)规则如下规则如下:(1)如果如果vmaxgap,且且gapleftgap，则从右车，则从右车道变换道变换(binhun)

20、至左车道。至左车道。(2)如果如果 vmaxgap-voffset,且且 vmaxgapright-voffset，则从左车道变换，则从左车道变换(binhun)至右车道。至右车道。(3)如果如果vbackgapleft，则，则vright=gapleft(禁止右禁止右车道的车辆超过左车道车辆车道的车辆超过左车道车辆)。第三十一页，共33页。n四、网络四、网络CA模型模型n1992年，年，Biham,Middleton和和Levine等利用元胞自等利用元胞自动机设计动机设计(shj)了一种简单的二维元胞自动机模了一种简单的二维元胞自动机模型型(BML模型模型)来模拟城市网络的交通流现象，研究来

21、模拟城市网络的交通流现象，研究交通阻塞问题。模拟结果表明当车辆密度大于某一交通阻塞问题。模拟结果表明当车辆密度大于某一临界值时，将会发生阻塞。临界值时，将会发生阻塞。nBML模型简单直观：有一个模型简单直观：有一个NxN的方形点阵，的方形点阵，N是是点阵的边长，每个格点可以有一辆由南向北行驶的点阵的边长，每个格点可以有一辆由南向北行驶的车辆，或者有一辆由东向西行驶的车辆，或者没有车辆，或者有一辆由东向西行驶的车辆，或者没有车辆占据。在每一奇数时间步，南北向的车辆可以车辆占据。在每一奇数时间步，南北向的车辆可以向前行驶一个格点；在每一偶数时间步，东西向的向前行驶一个格点；在每一偶数时间步，东西向

22、的车辆可以前进一个格点；如果车辆前方的格点已有车辆可以前进一个格点；如果车辆前方的格点已有其他车辆占据，那么这辆车只能在原地等候，不能其他车辆占据，那么这辆车只能在原地等候，不能向前行驶。这样，每个格点都相当于信号控制交叉向前行驶。这样，每个格点都相当于信号控制交叉口。口。第三十二页，共33页。nBML模型的改进模型的改进nChowdhury和和Schadschneider将将BML模型模型与与NS模型相结合，提出模型相结合，提出(t ch)了城市交通网了城市交通网络模型络模型(CS模型模型)。该模型在每两个连接的交叉。该模型在每两个连接的交叉口中设置若干个元胞表示路段，这些路段用口中设置若干个元胞表示路段，这些路段用NS模型建模；每个交叉口为信号控制交叉口，模型建模；每个交叉口为信号控制交叉口，信号周期为信号周期为T。第三十三页，共33页。