单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第六章,元胞自动机,交通流模型,本章主要内容,1 元胞自动机理论,2 元胞自动机交通流模型,详见：,贾斌，高自友，基于元胞自动机的交通系统建模与模拟，科学出版社，2007-10,相关文献：,Nagel and Schreckenberg.A Cellular automaton model for freeway traffieJournal of Physics(France)，1992,郑英力等交通流元胞自动机模型综述大路交通科技2023,23(1):110115,孙跃等基于元胞自动机原理的微观交通仿真模型重庆大学学报(自然科学版)2023,熊桂林,黄悦元胞自动机在混合交通仿真中的应用系统工程2023,狄宣基于元胞自动机的快速路仿真建模与交通流优化分析同济大学硕士学位论文2023.3,S Maerivoet,B De Moor，Cellular automata models of road trafficPhysics Reports 419(2023)1 64,教学目的：了解初等元胞自动机的根本概念，把握元胞自动机交通流模型的建立方法，把握NS交通流模型的特点、适用条件及其仿真。,重点：NS交通流模型,难点：NS交通流模型的仿真,1 元胞自动机理论,一、什么是元胞自动机,元胞自动机Cellular Automata，CA是一种时空离散的局部动力学模型，是争论简单系统的一种典型方法，特殊适合用于空间简单系统的时空动态模拟争论。,元胞自动机不是由严格定义的物理方程或函数确定，而是用一系列模型构造的规章构成。但凡满足这些规章的模型都可以算作是元胞自动机模型。因此，元胞自动机是一类模型的总称，或者说是一个方法框架。,在CA模型中，散布在规章格网(Lattice Grid)中的每一元胞(Cell)取有限的离散状态，遵循同样的作用规章，依据确定的局部规章作同步更新。大量元胞通过简洁的相互作用而构成动态系统的演化。,CA模型的特点：时间、空间、状态都离散，每个变量只取有限多个状态，且其状态转变的规章在时间和空间上都是局部的。,二、初等元胞自动机,初等元胞自动机是状态集S只有两个元素s1，s2，即状态个数k=2，邻居半径r=1的一维元胞自动机。由于在S中具体承受什么符号并不重要，它可取 0，1，-1，1，静止，运动 等等，重要的是S所含的符号个数，通常我们将其记为 0，1。此时，邻居集N的个数2r=2，局部映射f：S3S可记为:,二、初等元胞自动机,初等元胞自动机是状态集S只有两个元素s1，s2，即状态个数k=2，邻居半径r=1的一维元胞自动机。由于在S中具体承受什么符号并不重要，它可取 0，1，-1，1，静止，运动 等等，重要的是S所含的符号个数，通常我们将其记为 0，1。此时，邻居集N的个数2r=2，局部映射f：S3S可记为:,由于只有0、1两种状态，,所以函数,f,共有2,8,=256种状态。,t,111,110,101,100,001,010,001,000,t+1,0,1,0,0,1,1,0,0,S.Wolfram的初等元胞自动机,256种初等CA规章,对给定初值及规章 f，可通过计算机得到N步以后的演化结果,t,111,110,101,100,011,010,001,000,t,+1,0,0,0,0,1,1,1,0,0,0,0,0,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,0,1,1,0,1,1,0,0,1,1,1,0,1,0,0,0,1,rule 1,rule 2,rule 3,rule 4,rule 184,rule 255,rule 256,Three 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 kind 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 Science,Free online access:,:/,三个世纪以前，人们觉察建立在数学方程根底上的规律能够用于对自然界的描述，伴随着这种新观念，科学发生了变革。在此书中我的目的是应用简洁的计算机程序来表达更为一般的规律，并在此种规律的根底上建立一种新的科学，从而启动另一场科学变革。,详见：,A New Kind of Science,Free online access:,:/,90号规章：分形构造,CA_rule_90.m,110号规章：简单构造,CA_rule_110.m,2 元胞自动机交通流模型,一、第184号规章,特殊留意：第184号规章,特殊留意：第184号规章,车辆行驶规章为：黑色元胞表示被一辆车占据，白色表示无车，假设前方格子有车，则停顿。假设前方为空，则前进一格。,t,111,110,101,100,011,010,001,000,t+1,1,0,1,1,1,0,0,0,1992年，德国学者Nagel和Schreckenberg在第184号规章的根底,上提出了一维交通流CA模型，即，NS 模型或NaSch模型,二、NS 模型,在第184号规章的根底上，1992年，德国学者Nagel和Schreckenberg提出了一维交通流CA模型，即，NS 模型或NaSch模型,Nagel and Schreckenberg.A Cellular automaton model for freeway traffieJournal of Physics(France)，1992,CA模型最根本的组成包括四个局部:元胞(cell)、元胞空间(lattice)、邻域(neighbor)及更新规章(rule)。,NS模型是一个随机CA交通流模型，每辆车的状态都由它的速度和位置所表示，其状态依据以下演化规章并行更新：,a加速过程：,b安全刹车过程：,c随机慢化过程：,以随机慢化概率p,d位置更新：,其中：,L,-车辆长度7.5m,NS模型的演化规章：,1加速:司机总是期望以最大的速度行驶,2安全刹车:为避开与前车碰撞,3随机慢化以随机慢化概率p:由于不确定因素,a)过度刹车,b)道路条件变化,c)心理因素,d)延迟加速,4位置更新:车辆前进,a加速过程,b安全刹车过程,c随机慢化过程以随机慢化概率p,d位置更新,例：设,在NS 模型的根底上，又间续地提出了一系列一维CA交通模型，如TT、BJH、VDR、FI等模型；,双车道CA交通模型：STNS模型,机非混合CA模型：CCA模型,城市路网CA二维模型：BML、CTM模型,Los Alamos National Laboratory：,TRANSIMS(TRansportation ANalysis SIMulation System),近年国际上消失的一门新的穿插学科,交通物理学,Springer 2023,“幽灵式交通堵塞”“phantom”or“ghost”traffic jams的现象早在1975年就由Treiterer 和 Myers 通过航拍图像觉察。,直到1992年由德国学者Nagel 和 Schreckenberg 用元胞自动机CA交通流模型才加以成功再现和模拟解释。,Nagel and Schreckenberg.A Cellular automaton model for freeway traffieJournal of Physics(France)，1992,高速大路自发形成的堵塞幽灵堵塞ghost jam、时走时停stop-and-go wave,航拍图，,J.Treiterer，,1975年,条件：,随机慢化概率p；,密度=13.3veh/km/lan0.1,=20veh/km/lan0.15,=33veh/km/lan0.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；,随机慢化概率p=0.2；密度=13.3veh/km/lan0.1；,第5秒,第10秒,第20秒,第40秒,7.5m,随机慢化概率p=0.2；密度=20veh/km/lan0.15；,初始随机,7.5m,随机慢化概率p=0.2；密度=27veh/km/lan0.2；,初始均匀分布,7.5m,随机慢化概率p=0.2；密度=33veh/km/lan0.25；,7.5m,交通流CA模型的主要优点：,1模型简洁，特殊易于在计算机上实现。,2能够再现各种简单的交通现象，反映交通流特性。在模拟过程中人们通过考察元胞状态的变化，不仅可以得到每一辆车在任意时刻的速度、位移以及车头时距等参数描述交通流的微观特性，还可以得到平均速度、密度、流量等参数，呈现交通流的宏观特性。,3能够再现单车道、多车道以及路网的交通流建模；机动车和非机动车交通流的建模,三、多车道CA模型,与单车道模型相比，多车道模型增加了换车道规章。,Nagel 等在单车道NS模型的根底上，又提出了多车道模型。在该模型中，在各条车道上行驶的车辆要遵守NS规章，在进展车道变换时还要满足车道变换规章(lane-changing rules)。,该模型的车道变换规章如下:,(1)假设vmaxgap,且gapleftgap，则从右车道变换至左车道。,(2)假设 vmaxgap-voffset,且 vmaxgapright-voffset，则从左车道变换至右车道。,(3)假设vbackgapleft，则vright=gapleft(制止右车道的车辆超过左车道车辆)。,四、网络CA模型,1992年，Biham,Middleton和Levine等利用元胞自动机设计了一种简洁的二维元胞自动机模型(BML模型)来模拟城市网络的交通流现象，争论交通堵塞问题。模拟结果说明当车辆密度大于某一临界值时，将会发生堵塞。,BML模型简洁直观：有一个NxN的方形点阵，N是点阵的边长，每个格点可以有一辆由南向北行驶的车辆，或者有一辆由东向西行驶的车辆，或者没有车辆占据。在每一奇数时间步，南北向的车辆可以向前行驶一个格点；在每一偶数时间步，东西向的车辆可以前进一个格点；假设车辆前方的格点已有其他车辆占据，那么这辆车只能在原地等候，不能向前行驶。这样，每个格点都相当于信号掌握穿插口。,BML模型的改进,Chowdhury和Schadschneider将BML模型与NS模型相结合，提出了城市交通网络模型(CS模型)。该模型在每两个连接的穿插口中设置假设干个元胞表示路段，这些路段用NS模型建模；每个穿插口为信号掌握穿插口，信号周期为T。,