2014美赛A题讲解.ppt

《2014美赛A题讲解.ppt》由会员分享，可在线阅读，更多相关《2014美赛A题讲解.ppt（58页珍藏版）》请在三一办公上搜索。

1、2014美赛A题建模与求解,讲解人：王永丽,2014年8月11日,提纲,问题描述,求解方案,1、问题分析与模型建立,2、模型求解与计算机仿真,模型优缺点分析与改进,问题描述,题目：除非超车否则靠右行驶的交通规则,问题：在一些汽车靠右行驶的国家（比如美国，中国等），多车道的高速公路常常遵循以下原则：司机必须在最右侧驾驶，除非他们正在超车，超车时必须先移到左侧车道，超车然后再返回右车道。建立数学模型来分析这条规则在低负荷和高负荷状态下的交通路况的表现。,不妨考察一下流量和安全的权衡问题，车速过高过低的限制，或者这个问题陈述中可能出现的其他因素。这条规则在提升车流量方面是否有效？如果无效，提出能够提

2、升车流量、安全系数或其他因素的替代品（包括完全没有这种规则）并加以分析。在一些国家，汽车靠左行驶是常态，探讨你的解决方案是否稍作修改即可适用，或者需要一些额外的需要。最后，以上规则依赖于人的判断，如果相同规则的交通运输完全在智能系统的控制下，无论是部分网络还是嵌入使用的车辆设计，在何种程度上会修改你前面的结果？,问题分析与模型建立,2、是否存在更好的交通规则，如果存在，如何说明其更好。,1、在交通畅通与交通拥挤情形下，“右行左超车”交通规则的表现如何，选取什么样的评价参数来衡量。由此来确定该规则是否需要改进以及如何改进。,3、新规则是否适合靠左行驶的国家，是否需要考虑其他因素。,4、在智能系统

3、的控制下，上述规则表现如何，结果有何变化。,需要解决的问题,注：对该问题的研究可以归结为“右行左超车”规则下的交通 流模型的研究。,模型建立-元胞自动机模型,对于交通问题的研究中最经典的模型有跟车模型、流体力学模型和元胞自动机模型。,跟车模型将交通流处理为分散的粒子,以单个车辆作为描述对象,通过研究车辆之间的相互作用来描述交通流的特性。由于这种研究侧重于车辆间相互作用的精细刻画，属于微观模型,因此往往难以进行大规模的交通系统仿真。,流体力学模型以密度、速度和流量等宏观量来描绘车辆的平均作用行为，可以描述“交通激波”现象,但是该模型建立在速度和密度平衡的条件之上,不适用于描述本质上处于非平衡状态

4、的交通现象,例如“幽灵式”交通阻塞、交通迟滞等。,交通流元胞自动机模型(Cellular Automaton，简称 CA模型)是一种时空离散的局部动力学模型，特别适合于空间复杂系统的时空动态模拟研究。交通流元胞自动机的研究主要通过计算机仿真来模拟真实交通流,可以很好地反映交通流的宏观现象。,CA-184模型是采用一维格点链上的粒子来模拟公路上的车辆。在CA-184模型中,一条道路可以看作由一系列元胞组成,用元胞状态表示道路上某个位置（有无车辆）的状态，每个元胞左右各有一个元胞作为该元胞的邻居，根据t时刻自身和邻居的状态决定t+1时刻该元胞的状态。通过动态仿真模拟交通流的变化。,一维交通流元胞自

5、动机-CA-184模型,单车道元胞自动机NS模型与FI模型,1992年,德国学者Nagel和Schreckenberg提出了单车道的NS模型,该模型考虑了汽车的加速和随机慢化的可能性,同时在模型中引入了高速车，即单位时步的行进格点数大于l。,1996年,日本学者Fukui和Ishibashi在NS模型基础上提出了单车道FI模型,认为车辆的加速不仅限于一个格点,而是以最高车速为加速目标,即可以直接加速到最大速度。,1998年，K.Nagel 等人在单车道NS模型的基础上提出了双车道元胞自动机交通流NS模型，与单车道NS模型相比,多车道NS模型主要是增加了车辆换道规则，要求在各条车道上行驶的车辆要

6、遵守NS规则,在进行车道变换时还要满足车辆换道规则。,多车道元胞自动机NS模型与FI模型,多车道FI模型则是在单车道FI模型的基础上增加了车辆换道规则，要求在各条车道上行驶的车辆要遵守FI规则,在进行车道变换时遵循车辆换道规则。,用CA模型描述交通流，主要是通过对驾驶员驾车行为的分析，建立驾驶员或车辆的行为输出规则，从而建立元胞自动机的运行规则，然后仿真实际交通背景，模拟整体元胞群的动态过程，从中得到解决交通问题的方法或信息。这类模型考虑的主要问题包括：如何用微观规则的建模来描述元胞的运动过程；如何用宏观规则的建模来描述高速公路运行车辆的随机性，这是交通现象的重要特征。,本赛题要求评价“右行左

7、超车”的交通规则对高速公路的通行能力和安全性的影响。通过对CA模型建模和仿真一般方法的理解，需要研究以下四个方面的问题：首先要选取合适的评价指标，这些指标不仅能用于超车规则对高速公路的通行能力和安全性的评价，而且还必须便于在元胞自动机仿真过程中提取；其次，建立高速公路上车辆的运行状态随时间变化的微观规则模型，特别是“右行左超车”的规则模型；第三是运行车辆的不同运行状态改变的宏观概率分布，这是由交通问题的随机性决定的,而随机性是交通问题的一个特别重要的特性；最后是设计元胞自动机的仿真对比试验，特别是元胞群空间、初始元胞群密度、分布与状态等。,“右行左超车”交通规则下的元胞自动机模型,评价参数的确

8、定,1）车流密度（）：一个车道单位长度内某一瞬时存在的车辆数，以辆/千米表示，即（1）,注：车流密度主要用来表征交通拥挤（Heavy Traffic）与交通畅通（Light Traffic）的状态。车流密度越大，说明交通越拥挤，否则就越畅通。,2）平均车速（）：,在固定路段内不同车道上所有车辆的平均时速的平均值，其定义如下：,（2）,3）交通流量（Q）：单位时间内通过某一固定点的车辆数。根据交通流的理论,交通流量可定义为车流密度与平均车速的乘积，即：,（3）,4）车道改变率（）：,给定路段上，单位时间内的平均变道次数占总车辆数的比例，等于给定路段上某个时间段内的车辆变道总数除以时间与车辆总数的

9、乘积，即,（4）,5）连续刹车率（）：,给定路段上，单位时间内车辆连续减速改变的次数超过,两次（包含两次）的计数。,注：考虑到车道改变会增加事故发生的可能性，而连续刹车则可以理解成为避免发生事故而采取的措施，这些可以看作安全性隐患，故可用整个路段上的车道改变数及连续刹车计数来衡量交通规则的安全性。,仿真参数设定,1）加速概率（）：,对整个模拟路段上所有满足加速规则的车辆，让其以,的概率随机加速。,2）随机慢化概率（）,对所有以恒速行驶的车辆将以一个很小的概率 随机减速，,该指标主要用于描述驾驶员的驾驶行为输出。,3）超车概率(）,对整个仿真路段上满足向左（向右）变道规则的车辆，,注：由于高速公

10、路上大多数驾驶员都有高速行驶的欲望，因此，,而由快车道向慢车道变道的概率则较小。,对于超车欲望值为1的车辆，其变道概率设为1。,本模型中假设左车道为快车道，右车道为慢车道。,1、只讨论高速公路上“右行左超车”规则的作用与影响。,基本假设,2、假设没有任何停止信号或交叉打断当前的交通流，没有其他的入口与出口，没有急转弯，且路上仅有一种类型的车辆，但车道有快慢车道之分，即在不同车道上最低与最高限速不同。不考虑车辆在运行道路上停车的情况。,3、在仿真实验中，假设每个元胞只被1辆车占据。车辆的换道不考虑车辆加减速的中间过程，当车辆满足变道条件时，将直接调整到合适的车道。,4、考虑到不同驾驶员的驾驶行为

11、有所差异，车辆状态的改变具有一定的随机性，因此，假设在行车过程中，所有车辆状态的改变都按一定的概率发生。,5、在仿真过程中，通过在一个预先设定的区域，用定量的汽车采用循环的方式来模拟整个高速交通情况。仿真路段内汽车数量即车辆密度是常数，但是将对不同的密度进行仿真。,元胞自动机的微观规则设计,首先研究高速路一个方向两车道的超车问题。假设每一车道分为1000个元胞，则2条车道划分为 的元胞矩阵,定义每个元胞长度为5.5米，则模拟的实际道路长度为5.5km。,仿真的时间步设为1秒。一个元胞的全部状态用一个5元组表示：（）,）,5个状态参数分别为：第i辆车在t时刻的速度，所处元胞的位置，超车欲望值，所

12、处车道及其与前车的间距。,，,车速离散化为元胞长度的整数倍。,1元胞/秒=19.8公里/小时。,车辆前行规则设计,在假设车辆按照周期循环的方式来模拟的条件下，向前行驶的车辆在每一个离散的t到t+1时间步，每一车道上的车辆状态按下列规则同步更新：,1）加速规则 如果当前车辆与同一车道上前车间距大于安全距离且车速没有达到最大速度，则以概率 加速。即,2）减速规则 如果当前车辆与前车的间距小于安全间距，但大于等于当前道路最大限速与最小限速的差，则速度减1或减速至最小速度，若当前车辆与前车的间距小于最大限速与最小限速的差，则减速至最小速度。即,其中，第2种情形的减速是为了避免撞车的可能性。,。,该规则

13、用于描述驾驶员的驾驶行为，其减速行为不一定满足减速条件，但所有车辆都有随机减速的可能。,4）位置更新规则：,车辆换道规则设计,“右行左超车”下的双车道换道规则,由于高速路上车速相对较高，因此，考虑到安全性的因素，借鉴文献【1】中的换道规则，提出如下双车道换道规则：,1）车辆由右向左变道规则。如果当前在右车道行驶的车辆与前车的间距较小使得当前车辆的前行受阻，而其与相邻左车道上的前车间距较大，同时与左车道上后方车辆的间距大于安全距离，则车辆以概率 由右向左变道，即,表示右车道的最大限速，,表示左车道的最大限速。,2）车辆由左向右变道规则。如果在左车道行驶的车辆与相邻右车道前方与后方车辆的间距都大于

14、安全距离，则以概率由左向右变道，即,超车规则设计,1）超车欲望参数,在两车道模型中，只有位于右车道的车辆会产生超车欲望，且其超车欲望的产生与同车道前方车辆的状态有关，故其超车欲望值的定义如下：,表示第i辆车的车速大于其前车的车速，,2）“右行左超车”下的超车规则,在两车道模型中，考虑到实际驾驶中喜欢跟车的小概率驾驶行为，满足超车条件的车辆不一定选择超车，因此，其超车规则设计如下：,当超车的车辆返回右道后，其超车欲望值,然后再判断是否满足超车条件，确定 的值，,重复此过程直至超车欲望值不再取1为止。,对于超车欲望值为1的车辆若不满足向左变道条件，则仍在当前车道行驶，超车欲望值赋0，下一时刻再判断

15、其是否满足超车条件。,两车道元胞自动机仿真步骤,步1.（初始化参数）输入车道数,步3.（状态值计算）对于每辆车，计算与前车的间距，,与前车的安全间距，,与相邻车道前方车辆间距,步6.(加速、减速判别)对每辆车进行如下判断:,步7.(由右向左换道判别),否则,车辆仍在右车道行驶,同时,步8.(由左向右换道判别),步9.(位置更新)令,则自动计数驶出系统的汽车数，然后以当前状态重新放入开放车道的相应元胞内，重复上述过程直至,仿真过程说明,1）流量产生规则,在进行仿真实验时，初始车流的产生采用随机性的原则，即在仿真路段的不同车道上按一定车辆密度随机撒入具有不同速度的车辆。此处，车辆密度是指车辆数占总

16、元胞数的比例。,2）汽车循环规则,自动计数驶出系统的汽车数，然后重新放入开放车道的相应元胞内，如果没有开放车道则等下一步有开放车道再放入。,3）连续刹车计数规则,如果某辆车在某一固定的连续时间段内车速减速改变的次数超过两次（包含两次），则记其为一次连续刹车。,4）超车成功计数规则,如果一辆车的超车欲望值由1变为0，则记超车成功1次。超车成功率即为在整个仿真时段内超车欲望值由1变为0的车辆数占所有超车欲望值为1的车辆数的比率。,5）统计性原则,对每组参数，通过随机重复n次然后取平均的方式得到最后的实验结果。,仿真结果与分析,对两车道模型，分别对“右行左超车”规则与无规则的交通流进行仿真。这里所指

17、的无规则是指车辆的超车与换道只是按一定的概率进行,超车完成后也只是以一定的概率返回右道,与超车欲望值无关。在“右行左超车”规则情形下，超车欲望值为1的车辆超车完成后必须返回右道行驶。,在考虑快慢车道的情形下，通过选取不同的参数，进行大量的仿真试验，最终确定仿真参数如下：,仿真时长T=1200秒，随机重复次数=20，,1）相同概率设置下有规则与无规则的对照,2）最大限速提高的对照,在智能系统的控制下有规则与无规则的对照,在智能系统的控制下，即不考虑人为的因素与驾驶员的驾驶行为，只要满足相关条件，就自动按规则行驶。此时，除了概率值，其他参数都不变，而相关概率值的设置如下：,不分快慢车道情形下，有规

18、则与无规则的对照,时空图分析,在第一组参数下，分别截取车流密度分别为0.1 与0.8时，两个车道在“右行左超车”规则与无规则情形下的时空斑，如下图所示：,结论：对两车道模型，当车流密度较低，交通畅通的情况下，无论是道路的通行能力还是安全性，无规则都要比有规则要好，而当车流密度较大，使得交通比较拥挤时，有规则的安全性要好一些。从道路的利用率上讲，有规则要好于无规则。无规则情形下两个车道的利用率均匀，右道利用率相对较低。此外，无论是交通畅通还是交通拥挤，提高车道的最大与最小限速都将不仅提升道路的通行能力，而且也可以提高行车的安全性。但此时，当车流密度较大时，无规则要比有规则的安全性高。,1）提出了

19、超车欲望值的概念，对“右行左超车”规则进行刻画，并以此对超车行为进行量化描述。,模型的优缺点分析与改进,模型的优点：,2）提出了状态改变率的概念，对高速公路上车辆行驶状态的 变化进行描述，并通过多次仿真实验确定相应的参数，实验结果与实际较为相符。,3）仿真实验的结果是基于多次随机重复的平均值得到的统计 结果，符合一定的统计规律。,4）提出了连续刹车率的概念，用以对安全隐患进行定量描述，具有一定的借鉴价值与指导意义。,5）借鉴已有的两车道换道规则，提出了针对“右行左超车”的两车道换道规则与超车规则，并给出了相应的算法步骤，算法具有较强的可实现性。,模型的局限性：,1）仅考虑了道路上只有一种类型车

20、辆且每辆车只占一个元胞 的情形，且每辆车的状态改变都是瞬时完成的，没有考虑 加减速的过程与驾驶员的反应时间以及转向灯的作用，这 与实际有一定的差距。,2）受运行时间的限制，在仿真时长的设计及随机循环次数的 确定上与实际的统计规律还有一定差距，缺少对模型的 误差分析。,模型的改进,可以借鉴两车道模型的研究思路，增加车辆类型，同时考虑状态改变的中间过程，引入连续模型，对三车道模型进行讨论，并以提升道路通行能力与车辆行驶的安全性为目标，建立相应的优化模型，寻求多车道情形下最优的高速公路交通规则。,思考与练习,1）三车道模型的“右行左超车”换道与超车规则应如何 定义？,2）如何设计三车道的对照试验？相应的概率值如何设定？,3）三车道的仿真试验步骤与实验结果如何？,谢谢大家！,