《改进点格自动机交通网络模型及交通系统自组织现象的研究.pdf》由会员分享，可在线阅读，更多相关《改进点格自动机交通网络模型及交通系统自组织现象的研究.pdf（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、改进点格自动机交通网络模型及交通系统自组织现象的研究黄必亮杨家本(清华大学自动化系系统工程研究室,北京100084)摘要基于点格自动机的原理,提出一种比较切合实际的改进点格自动机交通网络模型。该模型把交通网络分为“道路”和“路口”。用队列来模拟“车流”,车辆密度分为三档。在此模型基础上,研究了不同情况下交通系统中的自组织现象。理论上分析了自组织形成的动态过程。并进行计算机仿真。关键词交通系统点格自动机自组织M odified Cellular A utomata T raffic N etwork M odeland Study on the Self2organizationof the T
2、 raffic System sHuang BiliangYang Jiaben(Dept.of A utomation,T singhua U niversity,Beijing 100084)AbstractBased on the principles of the cellular automata,a new i mproved cellular au2tomata traffic network modelwhich ismore near the realistic traffic patterns is present2ed in this paper.In the model
3、,the traffic network is divided into sections of roadsand intersections.The traffic flow s are si mulatedw ith team s and the vehicle densityis divided into three levels.W ith thismodel,we study the self2organization phenomenaof the traffic system under different situations and analyze the dynam ic
4、process of theformation of the self2organization patterns.Computer si mulation is also presented.Keywordstraffic system s;cellular automata;self2organization1引言采用点格自动机方法模拟交通网络系统始于BML模型1。以后,在此基础上,不少人对交通系统的自组织2、组织进行了研究。但是,BML模型与实际的差距相当大。第一,BML模型为了避免如图1的四方向“死锁”问题,把交通系统网络简化为两个方向的车流与实际相差较大;第二,BML模型中整个系统是
5、均匀的,没有“道路”与“路口”的区别,这与实际系统不甚符合;第三,BML模型中当车辆密度大于某个临界值时,则系统的所有车辆将全部阻塞,网络车流整体速度为零。而实际的交通系统不会出现网络车流整体速度为零的现象。为了解决BML模型的以上不足,并保留采用点格自动机方法并行计算、建模方法简单的优点等,我们提出了一种改进点格自动机交通网络模型,并在此基础上研究交通系统的自组织现象。1998年3月系统工程理论与实践第3期本文于1996年6月6日收到国家自然科学基金资助项目图12改进点格自动机交通系统模型确定型点格自动机模型由如下要素所组成:由点格构成的空间X;系统状态用函数f(x,t),xX,描述,f是布
6、尔化的,时间t是离散化的;系统演化规则f(x,t+1)完全由f(x1,t),f(x2,t),f(xn,t)所确定,其中x1,x2,xn表示x的n个邻位格点的状态;给定初态f(x,0);边界条件。确定型点格自动机实质上是一种布尔化的离散动力系统。随机型点格自动机只是对系统状态的描述又引入概率。我们仍然以KJ的网格来表示交通系统,如图2所示。其中十字路口,用“+”表示,它起的作用是交通灯的控制功能,车辆只能经过它,而不能在其上停留;道路,图中以“-”表示,每条路上有行驶方向相反的两条车道,以队列表示,车辆在其上可以行驶或停留。在模型中,我们把交通灯的状态分为四种,如图3所示。在交通灯的状态示意图中
7、,带箭头的弧线表示允许的行驶路线,状图2态的名称也各自表示了该状态中允许的行驶路线。每个状态名称由8个字母组成,这8个字母每两个构成一组,表示一条允许的行驶路线,每组中前一个字母表示起始方向,后一个字母表示终了方向。如状态EEWWESWN。EE表示向东的车辆可以继续向东行驶。WW表示向西的车辆可以继续向西行驶,ES表示向东的车辆可以转为向南行驶,WN表示向西的车辆可以转为向北行驶。每个状态均有四条允许的行驶路线。交通灯分成这四种控制状态是出于以下考虑:不允许有两个或两个以上的车辆同时可能到达同一个车道位置;同时允许的行车路线不能交叉;在满足上述要求前提下尽可能多的提供允许车辆行驶路线;而且交通
8、灯状态尽量少。模型中的“道路”实际上存在两种情况,即:有“东西向”与“南北图3向”之分。东西向的道路与南北向的道路之间以路口联接。每条道路以两个队列表示两个行驶方向相反的车道,例如,东西向的道路如图4所示。南北向的道路与此类似。队列的长度同为M。队列的每个元素代表一个“位置”,当一个车辆进入某车道,它就排在队尾,在每一个单位时间内,若其前一个“位置”为空,则可前移一个“位置”。每个位置最多允许停留两个车,也可以停留一个车或为空。即每个位置的车辆密度有0,1,2三档,这么做的原因是出于如下考虑:车辆的速度与车辆密度有关。较大的速度对应于较大的车辆间距,即较小的车辆密度。在这个模型中,车辆的速度只
9、有两种,或“停”(V=0),或“行”(V=1)。我们认为有必要在密度上2系统工程理论与实践1998年3月图4也表示出这种区别。路口出现红灯时形成的“等待队列”应该比通行时的“行进队列”具有更大的密度,如图5所示4。为此我们规定:车道队列中的每一个“位置”,若车辆在其上排队等待,则最多可允许两个车同时占据该位置,若车辆处于行驶状态,则每个位置只能容纳一个车。因此,每个车道,即队列,最多容纳的车辆数为2M(全部排队等候)。在这个模型中,每个车是有自己的即定目标方向,即“东、南、西、北”四者之一。在行驶过程中各自图5的目标方向不会改变,以不同的字母和颜色标志不同目标方向的车辆。车辆在行驶过程当中,由
10、于阻塞的原因,会拐到与自身既定行驶目标方向相垂直的车道上,但在此过程中既定目标方向不变,例如,向东行驶的车辆。由于前方阻塞,而南北向的道路上有空位,则以一个概率P t拐到南北向的道路上,暂时向南或向北行驶(但不会暂时向西行驶),等待适当的时机再回到向东行驶的车道上。我们称P t为“转向概率”。它指的是当一个车在与自身目标方向相同的车道队列上行驶到队首时,由于交通灯不允许其向前行驶或虽然交通灯允许但其前方队尾没有空位,不能向前行驶,而允许其转到与其既定目标方向垂直的车道上,则该车以概率P t转到相应车道上。当车辆的目标方向与其使用的车道相同时,我们称“车与车道匹配”。当一个车在与其不匹配的车道上
11、行驶到队首时,由于交通灯或目标车道的原因不能回到与其匹配的车道,却允许其在不匹配车道上继续行驶,则该车以保持概率P r继续在不匹配车道上行驶。P t,P r使交通系统产生自组织起着很大的作用,我们将在稍后讨论,并讨论它们的取值。该模型中的交通灯控制,目前,我们采用全网络同步的方式,即全网络的所有交通灯在同一时刻的状态是相同的。对于网络畅通程度的评价,我们采用“网络平均车速”为指标。=146ii=E,W,S,N(1)其中是网络在i方向上的平均车速,i有东、西、南、北四个取值,分别以E,W,S,N表示。=NiV2M DiKJ=12NiVM DiKJi=E,W,S,N(2)V=0(车辆停止时)或 V
12、=1(车辆行进时)其中,网络规模KJ,KJ是网络中i方向的车道数。Ni是以i方向为目标,并在与其匹配的车道上移动一个位置的车辆数。若一个车在与其不匹配的车道上移动,则不计入速度。Di是以i为目标方向的车辆密度,即:Di=niKJ2M,i=E,W,S,N(3)ni是以i为目标方向的车辆数。网络总的车辆密度D=146iDi。(4)本文中考虑的四个方向Di相等,所以有:D=Di(5)3第3期改进点格自动机交通网络模型及交通系统自组织现象的研究模型的初始状态采用随机赋值。在规定的各个方向的车辆密度Di下,i=E,W,S,N,计算出以i为目标方向的车辆总数ni。把这ni个车随机分配到i方向的KJ个车道上
13、。为了研究某些特殊问题,也可以采用非随机方式来获得初始状态,如后文将讨论的网络对于局部拥挤疏散能力的研究中,我们即采用确定性赋值。对于边界的处理,本文采用周期边界的方法,即右侧的边界等同于左侧边界,上方边界等同于下方边界。例如,一个以方向i为目标方向的车辆从右侧某一位置行驶到网络以外,则在网络左侧边界的对应位置有一个以方向i为目标方向的车辆进入网络。采用此方法把网络边界扩展为无限,并使网络内各个目标方向的车辆数ni在所研究的时段内保持守恒。对于所提出基于点格自动机原理的交通系统模型必须强调的是,这种在网格点连线上赋予车流状态值,而且为了表达双向车流赋予两个状态值,仅仅是为了直观,使其更接近实际
14、交通系统网络。其点格自动机本质并未改变,这是因为所建立改进点格自动机交通系统模型与交通灯控制点格自动机和两个单向车流点格自动机相叠加的结果是等价的。3交通系统中自组织现象当各路口的交通灯以图3中顺序 轮转时,我们取M=8,P t=0.1,P r=0.9时,网络的稳定速度s与车辆密度D的关系如图6中曲线A所示。网络初态的车辆分布是随机的。稳定速度s是指网络经过一段时间的演化后,平均车速为稳定时的车速。图6交通灯的轮换周期长度记为L,以上所述的交通灯轮换长度L=4。在网络车辆密度D较小的情况下s能够达到110,这时对应的模式为畅通模式。畅通模式中每一个车都与车道匹配,并且当某个车到达车道队列的队首
15、时对应交通灯的状态应是恰好让它前行的状态并且前方车道队尾为空。畅通模式中,每辆车的行驶过程中都不会停滞,这是理想模式。在这种模式中,车与交通灯之间密切配合,在D较小时,网络满足一定要求时,系统可以自组织达到种模式。对网络进行更为细致的分析可以得出:若网络中各路口交通灯控制状态同步,只有在满足:M=mLm为正整数(6)网络才有可能自组织进入畅通模式。满足上式,我们称之为交通灯与车道匹配。为显示这一匹配的重要性,我们 作 了 一 个 不 满 足 这 一 匹 配 的 例 子,如 图6中 的 曲 线C,M=6,L=4,交 通 灯 轮 换 为 P t=0.1,P r=0.9。由于网络不满足式(6)的要求
16、,无论车辆密度D如何取值,都不能达到畅通模式。实验中发现P t应该较小,若P t太大则会导致过多的车与车道不匹配从而影响;而P r应该较大,若P r太小则一个与车道不匹配的车达到队首时,它就不容易继续行进从而阻塞了整个车道。本文中一律取019。P t,P r对于s-D曲线的影响,由于篇幅关系不作详细讨论。对于有直接贡献的交通灯状态是、,而、可以认为是、之间转换的过渡状态。特别是在畅通模式中,、是不起作用的,因此为提高,我们考虑应提高、状态占交通灯轮换的比例,即“绿信比”。故此,我们把交通灯轮换改为:k k 则 L=2k+2k为正整数(7)状态、占的时间比例(绿信比)为:kk+1(8)4系统工程
17、理论与实践1998年3月为满足车道与交通灯的匹配关系,应有:M=mL=m(2k+2)(9)图6中曲线B是对应于k=3,m=1,L=8,M=8的s-D曲线,可以看到在相同的D时,s比曲线A有提高。图6中的曲线比较,涉及到一个问题,即网络能达到畅通模式的最大车辆密度Dm是多少。假设车辆密度为Dm时,网络已经达到畅通模式,则必然是每个车道上的车辆数相等设为ns,且每个车都与车道配合,因此有:Di=ns2M=Dm,i=E,W,S,N(10)由于每个车道速度恒为1,因此在一个交通灯轮换周期中,每个车前移L=2k+2步。而在一个周期内,这个车道上可以不停滞地向前行驶通过对应路口的车辆数最多是k。在车道与交
18、通灯匹配时,一个车从某一车道队尾到队首需经历m个周期。ns=mk(11)Dm=nx2M=mk2mL=mk2m(2k+2)=k4(k+1)(12)因此图6中曲线A的k=1,则Dm=14(1+1)=18,曲线B的k=3,则Dm=34(3+1)=316。从曲线上可以看出。假设车辆密度Dns,则过多的车由于转移概率P t,及保持概率P r的作用转移到有空余的车道上,最终达到畅通状态。特别让我们感兴趣的是,假设网络初始状态的车辆分布是极端不均匀的,即某一小块区域的车辆密度D=1,而该区域以外的车辆密度D=0,网络有没有能力通过自组织把局部拥挤的车辆,均匀疏散到整个网络而进入畅通模式。答案是肯定的。图8中
19、的三条曲线是在M=8,k=3的情况下,网络对于不同整体车辆密度下进行局部拥挤区域疏散,进而到达畅通模式的演化曲线。最可喜的是在D=Dm的临界情况,网络仍有能力进入畅通模式,说明网络的自组织功能很强。图中横坐标表示计算机模拟的步数,纵坐标表示整个网络的平均车速。以下各图同。从图中可以看出,整个车辆密度D越小越容易进入畅通模式,这与常理相符合,因为D小的情况畅通模式。只要满足每个车道车辆数小于Ds,而不要求整个网络车密度均匀。而在D=Dm时,要进入畅通模式则要求每个车道车辆数相等,均为Ds=m k,显然要困难得多。在进行拥挤区域疏散过程中,P t起着很重要的作用。图9中的五条曲线显示不同的P t值
20、时,网络从局5第3期改进点格自动机交通网络模型及交通系统自组织现象的研究各曲线转向概率P t=0.15,保持概率P r=0.90,队列长度M=8,交通灯轮换周期L=8,k=3曲线A:车辆密度D=0.12;曲线B;车辆密度D=0.16;曲线C;车辆密度D=3?16 0.19。图8各曲线:车辆密度D=3?16 0.19,保持概率P r=0.90,队列长度M=8,交通灯轮换周期L=8,k=3;转移概率不同;曲线A:P t=0.40;曲线B;P t=0.30;曲线C:P t=0.20,曲线D:P t=0.15,曲线E:P t=0.10。图9部极端拥挤状态进入畅通模式的动态过程。可以看到P t越大,疏散
21、得越快,但要进入畅通模式时,过大的6系统工程理论与实践1998年3月曲线A:转移概率是变化的。V 0.85,P t=0.50;0.85 V 0.95,P t=0.10;曲线B:转移概率P t=0.50;曲线C:转移概率P t=0115;各曲线:D=3?16 0.19;P r=0.90;图10P t都是不利的。当P t很大时,例如图10中的曲线B,P t=0.5,它使网络很难进入畅通模式。转移概率Pt对于自组织动态过程的影响让我们想到如果根据网络中车辆分布的不同情况来改Pt,可能可以得到较快的对局部拥挤的疏散,并较快的进入畅通模式。图10中的曲线A,Pt根据网络平均速度而改变,得到了相当好的自组
22、织动态过程。计算机模拟,通常是从随机分布的初态开始的。网络中车辆的分布相对要均匀得多,此种情况下网络进入畅通模式的速度比从局部极端拥挤的初态要快得多。值得一提的是,模型中含有随机因素(随机的初态分布,概率Pt及Pr),因此每次的实验结果只能是相近的,而不可能完全相同。对于交通系统自组织动态过程的研究,体现了改进点格自动机交通系统网络模型的优点,也对交通网络实现满意控制策略提供了有益的启发。5结论本文基于点格自动机原理,提出了改进点格自动机交通系统模型,它能够并行同步处理网络上的每一个车辆。通过计算机模拟,观察到交通系统的自组织现象。这个模型有应用前景,在此基础上可作网络层次上交通系统控制策略的
23、研究。参 考 文 献1Biham O,M iddleton A A,L evineD.Self2organization and a Dynam ical T ransition in T raffic2flow M od2els.Physical Review A,1992,15(下转第30页)7第3期改进点格自动机交通网络模型及交通系统自组织现象的研究5一个例子为便于对比,我们仍采用文4中的例子。考虑第二个方案的排序位置与其在各个目标下的各个属性值的变化范围的对应关系。根据定理1和定理2,有关计算结果如表1:表1a21a22a23第二位(356.518,425.05)(34.996,48.
24、696)(6.711,7.954)(8.046,9.289)第一位(425.05,500)(30,34.996)(7.954,8.046)第三位(350,3561518)(48.696,60)(9.289,10)(6,6.711)参 考 文 献1刘树林,邱菀华 1 多属性决策的广义双基点排序法 1 系统工程理论与实践,1998,18(2):23-25,652左军 1 多目标决策中灵敏度分析的方法探讨 1 系统工程理论与实践,1987,7(3),1-113Hai mes Y Y.M ultiple2Criteria Decision M aking:Respective A nalysis.IE
25、EE T rans.on System s,M anand Cybernetics,1985,SM C215(3):313-3154穆东 1 综合排序的双基点法的改进及灵敏度分析 1 系统工程理论与实践,1993,13(5):33-375郭耀煌,贾建民 1 综合评价与排序 1 系统工程理论与实践,1990,10(2):66-67,526刘树林,邱菀华 1 多属性决策的TOPSIS夹角度量评价法 1 系统工程理论与实践,1996:16(7):12-167V argas,L G.A nalysis of Sensitivity of ReciprocalM atrice.Applied M ath
26、ematics and Computation,1983,12(4):201-320(上接第7页)2N agatani T.Self2organization in 2D T raffic Flow M odelw ith Jam2A voidingD rive.Journalof the Physi2cal Society of Japan,April,19953Junguk L,Ki m,Jyh2Charn S,L iu.Prabaharan I.Swarnam,ThomasU rbanik.The A reaw ide Real2ti meT raffic Control(ARTC)Sy
27、stem:A N ew T raffic Control Concept,IEEE T ransactions on V ehicularTechnology,1993,42(2)4H Haken著 1 杨炳奕译 1 协同学:理论与应用 1 中国科技出版社,19905杨家本 1 有人参与复杂系统自组织?组织合作原理 1 复杂巨系统:理论、方法、应用1 科学技术文献出版社,19946StephenWolfram著 1Theory and Application of Cellular A utomata.World Scientific,Singapore,198603系统工程理论与实践1998年3月