2014美赛a题讲解课件

2014美赛A题建模与求解 讲解人：王永丽 2014年8月11日 提纲 问题描述 求解方案 1、问题分析与模型建立 2、模型求解与计算机仿真 模型优缺点分析与改进 问题描述 题目：除非超车否则靠右行驶的交通规则 问题：在一些汽车靠右行驶的国家（比如美国，中国等） ，多车道的高速公路常常遵循以下原则：司机必须在最右 侧驾驶，除非他们正在超车，超车时必须先移到左侧车道 ，超车然后再返回右车道。 建立数学模型来分析这条规则在低负荷和高负荷状态 下的交通路况的表现。 不妨考察一下流量和安全的权衡问题，车速过高过低的限 制，或者这个问题陈述中可能出现的其他因素。这条规则在 提升车流量方面是否有效？如果无效，提出能够提升车流量 、安全系数或其他因素的替代品（包括完全没有这种规则） 并加以分析。 在一些国家，汽车靠左行驶是常态，探讨你的解决方案是 否稍作修改即可适用，或者需要一些额外的需要。 最后，以上规则依赖于人的判断，如果相同规则的交通 运输完全在智能系统的控制下，无论是部分网络还是嵌入使 用的车辆设计，在何种程度上会修改你前面的结果？ 问题分析与模型建立 2、是否存在更好的交通规则，如果存在，如何说明其更好。 1、在交通畅通与交通拥挤情形下，“右行左超车”交通规 则的表现如何，选取什么样的评价参数来衡量。由此来确 定该规则是否需要改进以及如何改进。 3、新规则是否适合靠左行驶的国家，是否需要考虑其他因素。 4、在智能系统的控制下，上述规则表现如何，结果有何变化。 需要解决的问题 注：对该问题的研究可以归结为“右行左超车”规则下的交通 流模型的研究。 模型建立-元胞自动机模型 对于交通问题的研究中最经典的模型有跟车模型、流体 力学模型和元胞自动机模型。 跟车模型将交通流处理为分散的粒子, 以单个车辆作 为描述对象, 通过研究车辆之间的相互作用来描述交通流 的特性。由于这种研究侧重于车辆间相互作用的精细刻画 ，属于微观模型,因此往往难以进行大规模的交通系统仿 真。 流体力学模型以密度、速度和流量等宏观量来描绘车辆 的平均作用行为，可以描述“交通激波”现象, 但是该模 型建立在速度和密度平衡的条件之上, 不适用于描述本质 上处于非平衡状态的交通现象, 例如“幽灵式”交通阻塞 、交通迟滞等。 交通流元胞自动机模型(Cellular Automaton，简称 CA模型) 是一种时空离散的局部动力学模型，特别适合于 空间复杂系统的时空动态模拟研究。交通流元胞自动机的 研究主要通过计算机仿真来模拟真实交通流,可以很好地 反映交通流的宏观现象。 CA-184模型是采用一维格点链上的粒子来模拟 公路上的车辆。在CA-184模型中,一条道路可以看 作由一系列元胞组成,用元胞状态表示道路上某个 位置（有无车辆）的状态，每个元胞左右各有一个 元胞作为该元胞的邻居，根据t时刻自身和邻居的 状态决定t+1时刻该元胞的状态。通过动态仿真模 拟交通流的变化。 一维交通流元胞自动机-CA-184模型 单车道元胞自动机NS模型与FI模型 1992年,德国学者Nagel和Schreckenberg提出了单车道 的NS模型,该模型考虑了汽车的加速和随机慢化的可能性, 同时在模型中引入了高速车，即单位时步的行进格点数大 于l 。 1996年,日本学者Fukui和Ishibashi在NS模型基础上提 出了单车道FI模型,认为车辆的加速不仅限于一个格点,而 是以最高车速为加速目标,即可以直接加速到最大速度。 1998年，K.Nagel 等人在单车道NS模型的基础上提出了 双车道元胞自动机交通流NS模型，与单车道NS模型相比, 多车道NS模型主要是增加了车辆换道规则，要求在各条车 道上行驶的车辆要遵守NS规则, 在进行车道变换时还要满 足车辆换道规则。 多车道元胞自动机NS模型与FI模型 多车道FI模型则是在单车道FI模型的基础上增加了车 辆换道规则，要求在各条车道上行驶的车辆要遵守FI规 则, 在进行车道变换时遵循车辆换道规则。 用CA模型描述交通流，主要是通过对驾驶员驾车行为的 分析，建立驾驶员或车辆的行为输出规则，从而建立元胞自 动机的运行规则，然后仿真实际交通背景，模拟整体元胞群 的动态过程，从中得到解决交通问题的方法或信息。这类模 型考虑的主要问题包括：如何用微观规则的建模来描述元胞 的运动过程；如何用宏观规则的建模来描述高速公路运行车 辆的随机性，这是交通现象的重要特征。 本赛题要求评价“右行左超车”的交通规则对高速公路的通 行能力和安全性的影响。通过对CA模型建模和仿真一般方法 的理解，需要研究以下四个方面的问题：首先要选取合适的 评价指标，这些指标不仅能用于超车规则对高速公路的通行 能力和安全性的评价，而且还必须便于在元胞自动机仿真过 程中提取；其次，建立高速公路上车辆的运行状态随时间变 化的微观规则模型，特别是“右行左超车”的规则模型；第 三是运行车辆的不同运行状态改变的宏观概率分布，这是由 交通问题的随机性决定的, 而随机性是交通问题的一个特别 重要的特性；最后是设计元胞自动机的仿真对比试验，特别 是元胞群空间、初始元胞群密度、分布与状态等。 “右行左超车”交通规则下的元胞自动机模型 评价参数的确定 1）车流密度（ ）：一个车道单位长度内某一瞬时 存在的车辆数，以辆/千米表示，即 （1） 其中，L表示测试路段的长度， 代表车道数。 。 注：车流密度主要用来表征交通拥挤（Heavy Traffic）与 交通畅通（Light Traffic）的状态。车流密度越大，说明 交通越拥挤，否则就越畅通。 2）平均车速（ ）： 在固定路段内不同车道上所有车辆的平均时速的平均值， 其定义如下： 其中， 代表第j辆车在t时刻的速度。 （2） 3）交通流量（Q）：单位时间内通过某一固定点的车辆数。 根据交通流的理论,交通流量可定义为车流密度与平均车速 的乘积，即： （3） 4）车道改变率（ ）： 给定路段上，单位时间内的平均变道次数占总车辆数的比 例，等于给定路段上某个时间段内的车辆变道总数除以时间 与车辆总数的乘积，即 （4） 其中， 表示t时刻给定路段上的变道数。 5）连续刹车率（ ）： 给定路段上，单位时间内车辆连续减速改变的次数超过 两次（包含两次）的计数。 注：考虑到车道改变会增加事故发生的可能性，而连 续刹车则可以理解成为避免发生事故而采取的措施， 这些可以看作安全性隐患，故可用整个路段上的车道 改变数及连续刹车计数来衡量交通规则的安全性。 仿真参数设定 1）加速概率（ ）： 对整个模拟路段上所有满足加速规则的车辆，让其以 的概率随机加速。 2）随机慢化概率（ ） 对所有以恒速行驶的车辆将以一个很小的概率 随机减速， 该指标主要用于描述驾驶员的驾驶行为输出。 3）超车概率( ） 对所有满足超车条件的车辆，以概率赋予超车欲望值1。 4）向左变道概率（ ）与向右变道概率（ ） 对整个仿真路段上满足向左（向右）变道规则的车辆， 注：由于高速公路上大多数驾驶员都有高速行驶的欲望，因此， 而由快车道向慢车道变道的概率则较小。 让其以概率 （ ） 向左（向右）变道。 对于超车欲望值为1的车辆，其变道概率设为1。 对于超车欲望值为0的车辆由慢车道向快车道变道的概率较大 本模型中假设左车道为快车道，右车道为慢车道。 1、只讨论高速公路上“右行左超车”规则的作用与影响。 基本假设 2、假设没有任何停止信号或交叉打断当前的交通流， 没有其他的入口与出口，没有急转弯，且路上仅有一种 类型的车辆，但车道有快慢车道之分，即在不同车道上 最低与最高限速不同。不考虑车辆在运行道路上停车的 情况。 3、在仿真实验中，假设每个元胞只被1辆车占据。车辆 的换道不考虑车辆加减速的中间过程，当车辆满足变道 条件时，将直接调整到合适的车道。 4、考虑到不同驾驶员的驾驶行为有所差异，车辆状态 的改变具有一定的随机性，因此，假设在行车过程中， 所有车辆状态的改变都按一定的概率发生。 5、在仿真过程中，通过在一个预先设定的区域，用定量 的汽车采用循环的方式来模拟整个高速交通情况。仿真路 段内汽车数量即车辆密度是常数，但是将对不同的密度进 行仿真。 元胞自动机的微观规则设计 首先研究高速路一个方向两车道的超车问题。假设每一 车道分为1000个元胞，则2条车道划分为 的元胞矩阵 定义每个元胞长度为5.5米，则模拟的实际道路长度为5.5km。 仿真的时间步设为1秒。一个元胞的全部状态用一个5元组 表示： （ ） ） 5个状态参数分别为：第i辆车在t时刻的速度，所处元胞 的位置，超车欲望值，所处车道及其与前车的间距。 ， 其中， ， ， 分别表示道路的最小与最大限速。 车速离散化为元胞长度的整数倍。 在两车道的情形下， 用 表示第i辆车与前车的安全间距，根据两秒法则， 注：在上述定义下，在慢车道行驶的车辆最大速度为每秒可 通过5个格子（5元胞/秒），最小速度为每秒可通 3元胞/秒）。 过3个格子（ 在快车道行驶的车辆最大速度为每秒可通过6个格子 （6元胞/秒）， 最小速度为每秒可通过4个格子 4元胞/秒）。 （1元胞/秒=19.8公里/小时。 车辆前行规则设计 在假设车辆按照周期循环的方式来模拟的条件下，向前行驶 的车辆在每一个离散的t到t+1时间步，每一车道上的车辆状 态按下列规则同步更新： 1） 加速规则 如果当前车辆与同一车道上前车间距大于安全 距离且车速没有达到最大速度，则以概率 加速。即 2）减速规则 如果当前车辆与前车的间距小于安全间距， 但大于等于当前道路最大限速与最小限速的差，则速度减1 或减速至最小速度，若当前车辆与前车的间距小于最大限速 与最小限速的差，则减速至最小速度。即 其中，第2种情形的减速是为了避免撞车的可能性。 3）随机慢化规则 若，则 。 。 该规则用于描述驾驶员的驾驶行为，其减速行为不一定 满足减速条件，但所有车辆都有随机减速的可能。 4）位置更新规则： 车辆换道规则设计 “右行左超车”下的双车道换道规则 由于高速路上车速相对较高，因此，考虑到安全性的 因素，借鉴文献【1】中的换道规则，提出如下双车道 换道规则： 1）车辆由右向左变道规则。如果当前在右车道行驶的车辆 与前车的间距较小使得当前车辆的前行受阻，而其与相邻左 车道上的前车间距较大，同时与左车道上后方车辆的间距 大于安全距离，则车辆以概率 由右向左变道，即 其中， 分别表示第i辆车与相邻左车道前方车辆 以及相邻左车道后方车辆的间距。 表示右车道的最大限速， 表示左车道的最大限速。 其中，表示右车道的安全换道间距。 2）车辆由左向右变道规则。如果在左车道行驶的车辆与相邻 右车道前方与后方车辆的间距都大于安全距离，则以概率 由左向右变道，即 超车规则设计 1）超车欲望参数 在两车道模型中，只有位于右车道的车辆会产生超车欲望 ，且其超车欲望的产生与同车道前方车辆的状态有关，故 其超车欲望值的定义如下： 其中， 表示与第i辆车同车道的前方车辆前方的空闲 元胞数，表示与第i辆车同车道的前方车辆的车速。 表示第i辆车的车速大于其前车的车速， 表示与第i辆同车道的前方车辆的前方 车间距大于安全距离与最大车速的和。 2）“右行左超车”下的超车规则 在两车道模型中，考虑到实际驾驶中喜欢跟车的小概率驾 驶行为，满足超车条件的车辆不一定选择超车，因此，其超 车规则设计如下： 对满足超车条件的车辆以一定的概率 赋予其超车欲望值1， 而以概率1-赋予其超车欲望值0。对于超车欲望值为1的车辆， 判断其是否满足向左变道条件, 若满足，则向左变道，进入左道 行驶，超越，并在满足向右变道条件时,以概率1返回右道， 完成超车过程。 当超车的车辆返回右道后，其超车欲望值 , 然后再判断是否满足超车条件，确定 的值， 重复此过程直至超车欲望值不再取1为止。 对于超车欲望值为1的车辆若不满足向左变道条件， 则仍在当前车道行驶，超车欲望值赋0，下一时刻再判 断其是否满足超车条件。 两车道元胞自动机仿真步骤 步1.（初始化参数）输入车道数、一维元胞数（此处为1000）， 元胞长度 ， 车流密度（车辆所占元胞数与元胞总数之比） 加速概率 ， 随机慢化概率 ， 向左变道概率 ， 向右变道概率 ， 超车概率 初始左车道超车欲望赋值概率 ， 仿真时长T， 快车道的最高限速 ， 最低限速 ， 慢车道的车辆最高限速 令t=1。 最低限速 ， 步2.（元胞状态初始化）根据输入的车流密度产生车流随机分配 到每个元胞中，每辆车的初始状态值包括车辆编号i， 车速 ， 所在车道 ， 所在胞的位置 ，对于位于左车道的车辆, 随机赋予初始超车欲望值。 步3.（状态值计算） 对于每辆车，计算与前车的间距 ， 与前车的安全间距 ， 与相邻车道前方车辆间距 与相邻车道后方车辆的间距 。 。 步4. 对位于右车道的车辆，计算当前车辆前方车辆前方的 空闲元胞数 ， 计算其超车欲望值 。 对的车辆以概率随机赋值1，以概率赋值0。 步5. (随机慢化）对所有超车欲望值为0的车辆， 以概率 减速, 否则，按当前状态行驶。 步6. (加速、减速判别) 对每辆车进行如下判断: 若满足加速条件, 则以概率加速； 否则,判断其是否满足 减速规则，若满足减速规则,则减速；否则,保持车速不变。 同时对在相邻的时间段内连续减速两次以上的车辆进行计数。 步7. (由右向左换道判别) 对位于右车道的车辆（）， 由换道公式计算其下一时刻 的车道值 。若 ，则当换道条件满足时, 车辆由 )； 右道换到左道( 否则, 车辆仍在右车道行驶,同时 超车欲望值赋值0。 若，则当换道条件满足( )时, 车辆以概率向左变道； 否则, 车辆仍在右车道行驶。 步8. (由左向右换道判别) 步9. (位置更新) 令 步10.(循环计数) 若车辆驶出仿真路段（ ）， 对位于左车道的车辆( ),由换道公式计算其下一时刻 的车道值 。若 ，则当换道条件满足时, 车辆由 )； 左道换到右道( 并置其超车欲望值 ； 否则,车辆仍在左车道行驶。 若，则当换道条件满足 )时， (车辆以概率向右变道， 否则，车辆仍在 左道行驶。 ）， 则自动计数驶出系统的汽车数，然后以当前状态重新放入开放 车道的相应元胞内，重复上述过程直至 仿真过程说明 1）流量产生规则 在进行仿真实验时，初始车流的产生采用随机性的原则， 即在仿真路段的不同车道上按一定车辆密度随机撒入具有不 同速度的车辆。此处，车辆密度是指车辆数占总元胞数的比 例。 2）汽车循环规则 自动计数驶出系统的汽车数，然后重新放入开放车道的 相应元胞内，如果没有开放车道则等下一步有开放车道再 放入。 3）连续刹车计数规则 如果某辆车在某一固定的连续时间段内车速减速改变 的次数超过两次（包含两次），则记其为一次连续刹车。 4）超车成功计数规则 如果一辆车的超车欲望值由1变为0，则记超车成功1次。 超车成功率即为在整个仿真时段内超车欲望值由1变为0的车 辆数占所有超车欲望值为1的车辆数的比率。 5）统计性原则 对每组参数，通过随机重复n次然后取平均的方式得到 最后的实验结果。 仿真结果与分析 对两车道模型，分别对“右行左超车”规则与无规则的 交通流进行仿真。这里所指的无规则是指车辆的超车与换道 只是按一定的概率进行,超车完成后也只是以一定的概率返 回右道,与超车欲望值无关。在“右行左超车”规则情形下 ，超车欲望值为1的车辆超车完成后必须返回右道行驶。 在考虑快慢车道的情形下，通过选取不同的参数，进行 大量的仿真试验，最终确定仿真参数如下： 加速概率= 0.95， 最低限速=3格/秒。 超车概率 = 0.9， 随机慢化概率 = 0.05， 向右换道概率=0.4，向左换道概率 = 0.8， 仿真时长T=1200秒，随机重复次数=20， 左道初始超车欲望值概率=0.5， 快车道的最高限速=6格/秒， 最低限速=4格/秒， 慢车道的最高限速=5格/秒， 1）相同概率设置下有规则与无规则的对照 2）最大限速提高的对照 加速概率= 1， 超车概率 = 1， 随机慢化概率 = 0， 向右换道概率=1。 向左换道概率 = 1， 左道初始超车欲望值概率=0.5， 在智能系统的控制下有规则与无规则的对照 在智能系统的控制下，即不考虑人为的因素与驾驶员的驾驶 行为，只要满足相关条件，就自动按规则行驶。此时，除了 概率值，其他参数都不变，而相关概率值的设置如下： 不分快慢车道情形下，有规则与无规则的对照 加速概率= 0.95， 最低限速=3格/秒。 随机慢化概率 = 0.05， 向右换道概率=0.5， 左道初始超车欲望值概率=0.5， 两车道的最高限速=6格/秒， 超车概率 = 0.9， 向左换道概率 = 0.5， 时空图分析 在第一组参数下，分别截取车流密度分别为0.1 与0.8 时，两个车道在“右行左超车”规则与无规则情形下的时空 斑，如下图所示： 结论：对两车道模型，当车流密度较低，交通畅通的情 况下，无论是道路的通行能力还是安全性，无规则都要 比有规则要好，而当车流密度较大，使得交通比较拥挤 时，有规则的安全性要好一些。从道