基于一维交通流元胞自动机计算机编程模拟.pdf

《基于一维交通流元胞自动机计算机编程模拟.pdf》由会员分享，可在线阅读，更多相关《基于一维交通流元胞自动机计算机编程模拟.pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1/10 基于一维交通流元胞自动机计算机编程模拟 【摘 要】主要介绍了元胞自动机的特点及定义,元胞自动机在道路交通流模拟中的应用,设计了交通元胞自动机的结构,建立了运用元胞自动机的交通流模拟模型,运用 C 语言编程实现模拟,并利用 Matlab 得到流率与交通密度的关系;探讨了元胞自动机在道路交通流模拟中应用前景。【关键词】一维交通流；元胞自动机;C 语言编程;模拟 一、引言 1992 年,Nagel-Schreckenberg 采用元胞自动机模拟公路交通流,从此以后,相继有许多研究机构开始了交通元胞自动机的研究,并已有许多研究成果及相关模拟软件产生。元胞自动机(Cellular Automa

2、ta,简称CA)是一种时间和空间都离散的动力系统模型。散布在栅格(Lattice Grid)中的每一元胞(Cell)取有限的离散状态,遵循同样的作用规则,依据确定的局部规则作同步更新,大量元胞通过简单的相互作用而构成动态系统的演化。不同于一般的动力学模型,元胞自动机不是由严格定义的物理方程或函数确定,而是用一系列模型构造的规则构成。凡是满足这些规则的模型都可以算作是元胞自动机。因此,元胞自动机是一类模型的总称,或者说是一个方法框架。其特点是时间、空间、状态都离散,每个变量只取有限多个状态,且其状态改变的规则在时间和空间上都是局部的。二、元胞自动机介绍、元胞自动机 在元胞自动机的发展过程中,许多

3、学者构造了不同的模型。本文主要介绍交通流模拟常用的初等元胞自动机,又称 Wolfram 元胞自动机。初等元胞自动机(Elementary Cellular Automata,简称 E-CA)是状态集 S只有两个元素s1,s2,即状态个数 k=2,邻居半径 r=1 的一维元胞自动机。2、元胞自动机的构成 元胞自动机最基本的组成是元胞、元胞空间、邻居及规则四部分。即元胞2/10 自动机是由一个元胞空间和定义于该空间的变换函数所组成的。（）元胞 元胞又可称为单元或基元,是元胞自动机的最基本的组成部分。元胞分布在离散的一维或二维欧几里德空间的晶格点上。（）状态 状态可以是0,1的二进制形式。或是s0,

4、s1,sk整数形式的离散集。对于一维元胞自动机,定义元胞的两个状态,即0,1。（）元胞空间 元胞分布的空间网点集合就是所谓的元胞空间。l 元胞空间的几何划分:理论上,它可以是任意维数的欧几里德空间规则划分。目前研究多集中在一维和二维元胞自动机上。对于一维元胞自动机,元胞空间的划分只有一种。2边界条件:在理论上,元胞空间在各维上是无限的。但是在实际应用过程中,无法在计算机上实现这一理想条件,因此,需要定义不同的边界条件。3构形:构形是指某个时刻,元胞空间上所有元胞状态的空间分布组合。通常,在数学上,它可以表示为一个多维的整数矩阵。（）邻居 以上的元胞及元胞空间只表示了系统的静态成分,为将动态引入

5、系统,必须加入演化规则。在元胞自动机中,这些规则是定义在局部空间范围内的,即一个元胞下一时刻的状态取决于其本身状态和它的邻居元胞的状态。因而,在指定规则之前,必须定义一定的邻居规则,明确哪些元胞属于该元胞的邻居。在一维元胞自动机中,通常以半径来确定邻居,距离一个元胞内的所有元胞均被认为是该元胞的邻居。3、规则 根据元胞当前状态及其邻居状况确定下一时刻该元胞状态的动力学函数,即一个状态转移函数。将一个元胞的所有可能状态连同负责该元胞的状态变换的规则一起称为一个变换函数。这个函数构造了一种简单的、离散的空间/时间的局部物理成分。3/10、时间 元胞自动机是一个动态系统,它在时间维上的变化是离散的,

6、即时间 t 是一个整数值,而且连续等间距。假设时间间距 dt=1,若 t=0 为初始时刻,t=1 为其下一时刻。在上述转换函数中,一个元胞在 t+1 时刻的状态只决定于 t 时刻的该元胞及其邻居元胞的状态。三、一维交通元胞自动机的设计、元胞空间的离散 一维交通元胞自动机适宜于单车道交通流的模拟,为此以车辆行驶时所占道路长度(包括安全间距)l 为单位,将长度为 L 的道路均匀划分成连续的栅格,构成元胞空间,形成一列元胞。、模拟时间的离散 假定模拟总时间为T,在该时间空间上,以时间间距dt推进模拟时间,当dt=1时,从 t=0 初始时间开始,依次顺序加 1,推进模拟时间,直至模拟结束。3、状态 定

7、义元胞状态为0,1,其中 1 表示该元胞为有车状态,0 表示该元胞为无车状态。且车辆的运行方向是相同的。4、邻居 对于单车道交通流的模拟,可假设元胞 t+1 的状态仅受到其最近的邻居元胞的状态及该元胞 t 时刻状态的影响。因此其邻居半径取为 r=1。5、动态进化规则 一维交通元胞自动机状态更新规则实际上是 Wolfram 规则的扩展,统称为规则 184。(1)Wolfram 规则 根据实际的交通流变化,对于实际的单车道交通流模拟而言,可设计初等元胞自动机的一个规则如右表所示(黑色方块代表 1,白色方块代表 0)。这样,对于任何一个一维的 0,1 序列,应用以上规则,可以产生下一时刻的相4/10

8、 应的序列。以下序列就是应用以上规则产生的:t:1011100010 t+1:11101000 选择邻居半径r=1,由此确定状态转移函数f为:0,0,00;0,0,10;0,1,01;1,0,00;0,1,11;1,0,10;1,1,00;1,1,10。显然规则表达了车辆运动状态的变化,称为运动规则。由于交通模拟不仅要考虑车辆的运动状态的变化,而且需考虑其速度状态的转化,由此以上的运动规则可以表达为半径为1 的速度规则:110,101 符号表示元胞处于有车或无车状态。(2)一维交通元胞自动机状态更新规则 在规则 184 的基础上,假定车辆有几种可能的速度,u=0,1,2,umax,设 ui为车

9、 i 的速度,di为车 i 与车 i+1 间的间距。按速度规则,系统更新步骤为:步骤 1 可能的加速:如果 uidi,则 uidi-1;步骤 3 随机变速:如果 ui0,服从于概率 pi,使 uiui=ui-1;步骤 4 车辆向前移动 ui个元胞。对于一维交通元胞自动机 umax可取 1,从而通过模拟确定交通量、速度、密度三者之间的关系。上述的交通元胞自动机可以应用到交通系统的研究中。如采用交通元胞自动机,更直观地考察不同交通密度的交通流特性,便于分析和理解。四、单车道交通流元胞自动机模拟模型 建立交通模型的根本目的就是要以足够的精确度来再现客观的交通现象,在进行交通微观模拟的过程中,以元胞自

10、动机理论为主要的理论基础,全面构造车辆的到达,在路段上的自由行驶、跟驶和紧急减速等各种运行状态的运行规则。这里的交通模型主要包括两个部分:一是车辆产生模型;二是车辆行驶模型。车辆产生模型实际上就是将交通流的输入部分,作用于被模拟路段的起始断面,它依靠随机数技术产生符合已给定概率分布的车辆的状态属性以及交通5/10 流参数以此向系统提供初值。车辆行驶模型即是反映车辆在路段上行驶时状态 变化过程的模型,即元胞自动机模型。、模拟基本参数 道路长度:L=7500m;元胞长度:l=7.5m;元胞数目:n=1000 个;最大车速:Vmax=5 元胞长度/s=57.5 m/s=135 km/h;模拟总时间:

11、T=10000 s(总运行步长);时间步长:dt=1s;定义随机减速概率:p=0.5。、车辆的随机产生 本文的随机车辆产生是依据泊松分布原理的断面发车模型。通过对相关资料提供的车流数据的分析与实地观察数据,在城区、市郊、高速公路等车辆通行较为频繁的地方,车流到达情况接近均匀的波峰分布。在此选用常用、简单的概率分布泊松分布来表示交通流的分布情况。由于泊松分布的变异系数为 D(x)/E(x)=I,则根据变异系数定义,该分布的概率曲线集中度比较均匀,能体现均匀分布。如公式:Pt*(n)=2/n!e-(1)其中:n 为车辆数;为参数 根据实验采集数据方式得:式(1)中的参数有相应的物理意义,表示在采样

12、时间 t*内的车辆数。令=at*,则 a 表示车辆平均到达率(veh/s),则泊松分布公式(1)转化为:Pn(t*)=(at*)n/n!e-at*(2)式(2)表示的物理意义是:在时间区段 t*内有 n 辆车进入模拟路段的可能性为 Pn(t*)。通过在实际的车道上找一断面,然后固定采样时间测量通过此断面的车辆数。由实际测量的数据分析得出车辆产生率的期望。在本文中随机取一个经验值：a=0.5。6/10 在基于泊松分布原理而建立断面发车模型时,重要的是利用概率统计原理,确定出发车模型的相关参数,从而建立具体的发车模型。如图 1 所示。图 1 服从泊松分布的车辆产生 3、车速的随机分布产生 入口发车

13、时不仅要产生发车时刻,也要对发车的速度赋初值,理论研究证明车速一般服从正态分布或对数正态分布。这里主要介绍了服从正态分布的随机车速的产生。正态分布的分布函数 F(x)为:F(x)=P(X x)=12exp12(tu)2dt (3)由于上式无法积分得到显式,故不能进行逆变,而采用函数变换法。当 XN(0,1)时,Y=X+N(,2)因此先考虑生成标准正态分布 N(0,1)的随机变量。采用 Box-Muller 的函数变换法,只要产生两个均匀分布的随机数 u1和 u2即可产生两个服从标准正态分布的随机变量 w1和 w2,即:w1=2ln(u2)sin(2u1)(4)W2=2ln(u2)cos(2u1

14、)(5)其产生正态分布随机变量的程序流程图见图 2。、模型基本规则 产生阶段:以按发车概率在起始空格点产生不同速度的车辆,相当于不同速度的车辆进入车道占 7/10 据不同的空格子;加速规则:如果当前车辆速度 V(t)Vmax,则车辆加速:V(t+1)=min(Vmax,V+1);减速规则:如果一辆车到它前面最近邻的另一辆车的距离 gapV,则车辆减速为 V(t+1)=gap;随机慢化规则:在概率 p 下,在加速和减速规则下得到的速度减 1,即:V(t+1)=max(V(t+1)-1,0)运动阶段:各车辆以自己的速度向前运动:X(t+1)=X(t)+V(t+1)转出阶段:如果车辆运动到终点格子处

15、时,它代表车辆的转出。加速规则反映了司机有追求最大速度的愿望,减速规则即避免碰撞是为了避免与前车发生碰撞,随机慢化规则考虑了不同驾驶者的个体行为,随机化参数p 同驾驶行为的三种特性有关:最大速度时的速度波动;制动时减速的过度反应;加速时的延迟。以上演化步骤作为一个周期反复进行下去,它实际上描述了较为接近实际的高速公路上车辆的运动状况。五、计算机编程模拟、单车道交通流模拟模型流程图 基于上述的一维单车道交通元胞自动机,按照元胞自动机规则确定的路段上的所有车辆运动状态的程序如图 3 所示。图 2 服从正态分布变量的程序流程图 8/10 图 3 单车道交通流元胞自动机模拟模型流程图、程序设计）随机数

16、发生器 double schrage(int a,int m,int b)/随机数发生器,直接返回随机数0,1 int q,r;double z;q=m/a;r=m%a;I=a*(I%q)-r*(I/q);if(I0)I=I+m;z=(double)I/m;return z;2)随机车辆产生子程序 int car()int flag;if(schrage(16807,2147483647,0)0.5)flag=1;else flag=0;return(flag);3)速度更新规则 for(i=0;in;i+)if(vigapi&vi=gapi)vi=gapi;/随机减速 for(i=0;in;

17、i+)if(schrage(16807,2147483647,0)0.5)/随机慢化概率:p=0.5 vi=vi-1;/车速随机慢化规则 4)车辆位置更新 for(i=0;in;i+)ai=ai+vi;3、模拟结果和讨论 根据以上模型模拟,运用 C 语言编程实现模拟,并利用 matlab,可以得到流量与交通密度之间的关系如图 4。分析图中的曲线陡变原因,主要是因为随着车辆数的增加,在道路上车辆的密度增大,车辆之间的间距变小,车辆之间的相互影响加剧,模型中的规则全部产生作用。在车辆密度较小时,车辆是自由运动,随时间的增加,车辆向前行驶位置与时间是线性关系,即车辆匀速行驶。当车辆密度增大时,车辆自

18、由运动的程度减小,随时间的增加,出现了车辆聚集的阻塞相,位置与时间变为了非线性关系,车辆位置分布是非均匀的,有的区域车辆密集,有的区域没有车辆,车流的运动相与阻塞相交替出现,非常类似于波的波峰和波谷的传播。10/10 图 4 交通密度的关系 六、交通元胞自动机的发展 计算机技术的不断发展,使得元胞自动机在交通宏观及微观模拟方面的研究和应用会越来越广泛,前景十分广阔。交通系统即是一个时间、空间离散的、复杂的大系统,系统的特性受到人车路等多方面因素的影响,有时传统的研究方法难以研究和解析某些交通现象,难以揭示其中的规律,显然可以利用元胞自动机研究交通流特性。结合道路交通的特点,研究元胞自动机在交通

19、模拟仿真方面的应用,有助于交通系统的分析、预测及评价。参考文献 1、道路交通的元胞自动机模型及其分析 李捷 物流技术 2010 年第 12 期 2、基于元胞自动机的交通流模型研究 邹杰 博士论文 2007 3、元胞自动机方法及其在交通通畅性中的研究 马道远 硕士论文 2002 4、基于元胞自动机的交通流计算机模拟 宇仁德 计算机仿真 2008 年第 8 期 5、基于元胞自动机原理的微观交通仿真研究 莫智锋 硕士论文 2004 6、基于元胞自动机模型的交通事故研究 刘学兵 硕士论文 2008 7、城市交通瓶颈的交通流元胞自动机模拟研究 肖世发 硕士论文 2004 8、高速公路元胞自动机混合交通流模型研究 张海顺 硕士论文 2008