交通流理论与方法排队论ppt课件.ppt

第六章排队理论及应用 组员 曹光辉 1 6 1概述6 2排队论的基本概念6 3排队过程分析6 4交叉口延误模型6 5道路的排队模型 2 6 1概述 排队论也称随机服务系统 是研究 服务 系统因 需求 拥挤而产生等待行列即排队现象以及合理协调 需求 与 服务 关系的一种数学理论 亦称 随机服务系统理论 它将交叉口看成一个服务台 将车流看成是受服务的对象 车辆服从先到先服务原则 3 6 2排队理论的基本概念 6 2 1 排队 与 排队系统 排队 单指等待服务的顾客 车辆或行人 不包括正在被服务的顾客 而 排队系统 既包括了等待服务的顾客 又包括了正在被服务的顾客 6 2 2排队系统的组成部分1 输入过程就是指各种类型的顾客按怎样的规律到来 常见的有如下几种服务过程 1 定长输入 顾客等时距到达 2 泊松输入 顾客到达符合泊松分布或顾客到达时距符合负指数分布过程 这种分布最容易处理 因而应用最广泛 3 爱尔朗输入 顾客到达时距符合爱尔朗分布 4 2 排队规则指到达的顾客按怎样的次序接受服务 常见的有以下几种排队规则 1 损失制 顾客到达时 若所有服务台均被占 该顾客就自动消失 永不再来 2 等待制 顾客到达时 若所有服务台均被占 它们就排成队伍 等待服务 服务次序有先到先服务 这是最通常的情形 和优先服务 如急救车 消防车等 等多种规则 3 混合制 顾客到达时 若队长小于某一定值L 就排入队伍等候 若队长等于L 顾客就离去 永不再来 5 3 服务方式指同一时刻有多少服务台可接纳顾客 为每一顾客服务了多少时间 每次服务可以接待单个顾客 也可以成批接待 例如公共汽车一次就装载大批乘客服务时间的分布主要有以下几种 1 定长分布服务 每一顾客的服务时间都相等 2 负指数分布服务 各顾客的服务时间相互独立 服从相同的负指数分布 3 爱尔朗分布服务 各顾客的服务时间相互独立 服从相同的爱尔朗分布 引入下列记号 令M代表泊松输入或负指数分布服务 D代表定长输入或定长服务 代表爱尔朗输入或服务 G代表任意服务时间 于是 泊松输入 负指数分布服务 N个服务台的排队系统可以定成M M N 如果不附其说明 则这种记号一般都指先到先服务 独个顾客服务的等待制系统 6 6 2 3排队系统的主要数量指标排队系统最重要的数量指标有三个 分别为等待时间 忙期和队长 1 等待时间从顾客到达时起至开始接受服务时为止的这段时间 2 忙期服务台连续繁忙的时期 这关系到服务台助工作强度 3 队长有排队顾客数与排队系统中顾客数之分 这是排队系统提供的服务水平的一种衡量 7 6 3排队过程分析 6 3 1M M 1系统M M 1系统为服从泊松输入 负指数分布服务 单个服务台的排队系统 由于M M 1系统排队等待接受服务的通道只有单独一条 也叫 单通道服务 系统 见图6 1 图6 1单通道服务系统示意图 8 设顾客平均达到率为 则到达的平均时距为1 排队从单通道接受服务后通过的平均服务率为 则平均服务时间为1 比率叫做服务强度或交通强度或利用系数 可确定各种状态的性质 所谓状态 指的是排队系统的顾客数 如果 1 并且时间充分 每个状态都按一定的非零概率反复出现 1时 任何状态都是不稳定的 而排队的长度将会变得越来越长 因此 要保持稳定状态即确保单通道排队能够消散的条件是 1 1 在系统中没有顾客的概率 6 1 2 在系统中有M个顾客的概率 6 2 3 系统中的平均顾客数 6 3 4 系统中顾客数的方差 6 4 9 5 平均排队长度 6 5 6 非零平均排队长度 6 6 7 排队系统中的平均消耗时间 6 7 8 排队中的平均等待时间 6 8 例题P117 10 6 3 2M M N系统在M M N排队系统中 服务通道有N条 所以也叫 多通道服务 系统 设为进人多通道服务系统顾客的平均到达率 排队行列从每个服务台接受服务后的平均输出率为 则每个服务的平均服务时间为1 仍记 N则称为M M N系统的服务强度或交通强度或利用系数 亦可称为饱和度 和M M 1相仿 当 N 1时 系统是稳定的 N1时 系统的任何状态都是不稳定的 排队长度将趋向于无穷大 11 M M N系统根据顾客排队方式的不同 又可分为 1 单路排队多通道服务 指排成一个队等待数条通道服务的情况 排队中头一顾客可视哪个通道有空就到那里去接服务 系统中没有顾客的概率为 6 9 系统中有k个顾客的概率为 6 10 12 系统中的平均顾客数为 6 11 平均排队长度有 6 12 系统中平均消耗的时间为 6 13 排队中的平均等待时间为 6 14 13 2 多路排队多通道服务每个通道各排一个队 只为其相应的一队顾客服务 顾客不能随意换队 这种情况相当于有N个M M 1系统组成的系统 其计算公式亦由M M 1系统的计算公式确定 由P120的例题 可以看出M M N系统比N个M M I有优越性 因为M M N系统较为灵活 排在第一位的车辆可视哪个服务台有空就到哪个服务台 避免了各服务台忙闲不均的情形 充分发挥了他们的服务能力 因而显得优越 14 6 3 3一般服务时间的M G 1排队模型1 M G 1 排队系统假设服务时间 的期望E 和D 存在 服务强度 E 1 可以用布拉切克 辛钦 P K 公式及里特公式求出系统运行指标 6 15 6 16 6 17 6 18 其中 Ls的计算公式称做P K公式 只要知道服务时间 的期望和方差 不管 是服从什么分布 都可以求出系统的运行指标 15 2 M D 1排队系统M D 1系统是M G 1系统的一种特殊情形 表示泊松输入 定长服务时间以及系统容量和顾客源均无限制的单服务台排队系统 这里的服务时间 E D 0 由P K公式可得若记E 1 则有均为标准的M M 1系统相应运行指标的一半 可见系统内部越有规律越省时间 16 3 M Ek 1排队系统本系统的服务时间 服从k阶爱尔郎分布 其实际背景是服务机构由k个串联的服务台组成 顾客为接受服务必须经过全部k个服务台 每个服务台的服务时间 i均服从参数为k 的负指数分布 则总共服务时间便服从爱尔朗分布 且 由P K公式有 17 6 3 4服务率可变的单通道车辆排队模型以上情况都是假设服务机构服务率是固定的 在现实中服务机构的服务率也可能随着车辆的排队长度而变化 可以使动态的 排队车辆较多时服务率也就适当提高 下面将介绍这累服务率可变的单通道车辆排队模型 假定有单通道的随机服务模型 到达系统的车辆流是参数为 的泊松流 服务时间服从负指数分布 而服务率随系统的队长K变化 记作 k k可按实际取不同的值 设系统在时刻t有n辆车 我们就称系统的状态为n 同时记系统在时刻t状态为n的概率为Pn t 它决定了系统运行的特征 18 1 系统中参数指标 排队系统的平均服务强度 由于服务率是变化的所以1 k也是可变的 先求平均服务时间于是 系统中车辆的平均数 6 20 系统中排队等待的车辆数 6 21 车辆在系统中平均停滞的时间 6 22 车辆在系统中排队等待的时间 6 23 6 19 19 2 一种特殊的可变服务率车辆排队系统这个排队系统的特殊在于当排队长度超过某个数 n 时 用快速服务率 2 反之用普通服务率 1 这种系统的参数指标如下 系统中车辆的数Ls 系统中排队等待的车辆数 6 25 车辆在系统中停滞时间 6 26 车辆在系统中排队时间 6 27 P127对例题计算的表中的比较可以看出 该理论与M M 1系统相比 系统中的排队车辆数 车辆平均等待时间都降低了 大大提高了收费站的服务水平 6 24 20 交叉口的问题处理分两个组成部分 管制形式 停车标志 让路标志 定时信号或动车信号 控制成分 车辆或行人 6 4交叉口的延误模型 21 6 4 1信号交叉口延滞模型 在估计交叉口的延滞时 交通量均可看成是由当量的若干小客车所组成 阿尔索普 Allsop R E 提出应用下列符号 c 周期时间 s g 有效绿灯时间 s r 有效红灯时 s q 入口通道上车辆平均到达率 小客车 s I 在一个信号周期内以当量小客车单位计的到达数方差 在一个信号周期以内以当量小客车单位计的到达数的平均值s 入口通道上饱和交通流量 当量小客车 veh s d 入口通道上当量小客车平均延滞 s 溢流交通量 pcu s g c 即有效绿灯占周期的百分比 y q s 即 平均到达串和饱和交通量之比 x qc gs 即 每周期平均到达数与每周期最大离去数之比 这样和 比值x称为入口饱和度和y称为入口流率 22 有效绿灯时间 周期中等候在入口的车辆 假定以当量小客车为单位 以恒速通过信号的时间 格林希尔兹等人 在研究一队n辆停着的汽车 通过交通信号的总时间 提出如下计算公式 当n 5 总时间 14 2 2 1 n 5 秒要是所有车辆在饱和率s 1 2 1 时离去 前五辆汽车须要有10 5秒 即有效绿灯时间是绿灯信号时间减去3 7秒 虽然有效绿灯时间可以调整适应于车辆具体运行条件 但是在大多数研究中均假设排队等候的车辆可以利用黄灯的净时隙 在入口上 一辆小客车到达时间和离去时间的意义 可以参考图6 6来说明 图中画了四辆汽车每辆的距离一时间曲线 AB表示车辆通过没有延滞 PQ线表示停车线 有排队时第一辆车停在那里等候 CDEF表示第一辆车由于信号延滞的的轨迹 图6 6假设的到达和离去时间定义说明图 直线部分CD和EF平行于AB两线延长分别与PQ相交于X和Y 所以长度XY就是第一辆汽车的延滞 同样和分别为后面两辆汽车的延滞 X和分别为到达车辆的车头时距 23 1 定时信号的连续型模型梅 May 提出了一个连续型模型的表达式 列于图6 7 垂直轴表示到达的累积车辆qt 水平轴表示时间t 情况 表示绿灯间隔内的通行能力超出绿灯 红灯时间到达数的情况 情况 是关于在绿灯期内驶出的车辆等于绿灯加红灯期内到达车辆的情况 在图6 5中垂直距离ca 表示自从信号进入红灯相位后积累的车辆数目 水平距离ab表示任何指定的车辆从到达到离去的总时间 对于以上两种情况的公式可以从简单的几何关系推导出 1 显然对于任何给定周期 在绿灯开始时间后 到达车辆等于离去车辆 6 44 令y q s 6 45 2 周期和排队之比 等于排队时间 周期长度 6 46 3 停止车辆的百分数等于停歇的车辆 每个周期的总车辆数 6 47 24 4 通过现察可见排队的最大车辆数是红灯开始后 单位处三角形的高 6 48 5 在整个周期长度 c 内排队车辆的平均数 由此得出 6 49 6 总的延滞车辆小时是根据三角形面积得出 6 50 7 个别延滞的平均值是根据总的延消除以车辆数目 6 51 8 个别车辆延滞的最大值可以根据图6 7得出 6 52 6 7在有信号灯的交叉口的排队现象 不适用于离去车辆sc小于到达车辆qc 25 2 定时信号的概率模型温斯顿和其同事们应用二项分布模型分析定时交通信号处的车辆延滞 如果对于某些固定的和 p 在时间n内到达l辆当量小客车 和p 在时间n内没有当量小客车到达 l 每个n值在任何情况下都是独立的 并且在其它时间无到达车辆 则到达入口的车辆有二项到达频率 平均到达率为 如果在一包括n的N瞬间时期内 为小客车的当量单位数 则服从二项分布 对于这种分布 方差与平均数的比率 I 等于1 小于1 不过对于城市道路观测的I值 根据米勒所指出的通常大于1 纽厄尔使用了到达的车间时距采用移位指数分布的模型 这种模型假设最小车间时距1 s 当量小客车从队列离开的模型 较到达模型简单 要是存在队列时 大多数模型采用等时间间隔1 s离开 头一辆车离开是在绿灯生效时开始 对于时间间断的设想 取等于1 s人 第一辆小客车在绿灯有效时间n开始时离开 并连续的在每个内一辆小客车离开 直到队列散完或绿灯时间结束为止 26 温斯顿等人论证了具有二项到达频率的交通信号处 对于一当量小客车通过入口时的平均延滞为 6 53 温斯顿等人未能导出溢流 在一个给定周期内未能清除交叉口的汽车 概率分布 纽厄尔提出了溢流平均值的估算 当 即比值接近于1 可近似地取为 6 54 根据用计算机模拟交叉口运行所得数据 韦伯所用于延滞的一个比较著名的公式 6 55 因为c 1 r和x y 第一项与假设为连续型车流 方程6 51 所得出的相同 阿尔索普指出第二项是假设在信号与到达车辆之间 插入一恒定服务1 s的排队求得的 插入车队的平均等待时间为 第三项是校正项 代表总的平均延滞5 15 从模拟信号特性所产生的数据 经回归分析提出的 阿尔索普建议平均延滞可取为 6 56 米勒假定在入口处的队列是统计上平衡的 并互在逐次的红 绿灯时间内到达车辆为独立分布 根据这个假定他得出了一个近似的溢流平均数为 27 当泊松到达频率应用于延滞模型时 得出 米勒也提出了延滞公式 该公式中他放弃了泊松到达的假定而采用一般到达模型与提出式6 57时采用的模型一样 当 x 1 2时所得到的延滞方程为 6 59 当 x 1 2小时 括号里面的中间项为零 米勒发现当I接近于1时 他的方程与韦伯斯特的 方程6 55 方程得出相似的结果 当I明显地大于1时 式 6 59 可得出较好的结果 纽厄尔考虑了连续型模型和溢流所引起的额外附加延滞 他的研究获得了下列延滞表达式 式中H 是入口备用通行能力的函数 6 57 6 60 6 61 6 58 28 6 62 韦伯斯特平均延滞曲线 方程6 55 对饱和度x和周期有效绿灯的比率分别表示于图6 8和图6 9 参数I 方差 平均值 对于几种延滞表达式的影响表示于图6 10中 6 8函数H 的值 6 9按韦氏完全表达式的平均延滞作流率 赫特钦生引入变量I修正阿尔索普平均延滞 29 赫特钦生还计算了平均延滞全表达式作为流率y的函数所得延滞之间的百分比差 赫特钦生对于s c和k的不同组合得出了同样的结果 几乎包络其它曲线的成对扭曲线是百分比差的极限值 结果是y时 0 和y时 本节只考虑了定时信号 以上的讨论 只考虑了孤立的交叉口的情况 该处到达车辆不受相邻的交通控制装置的影响 考虑一组交叉口时 无论是在一条干道上连续的交叉口或闹市区街道网上的一联串交叉口 孤立的交叉口的假设不再有效 图6 10参数I根据各种表达式估计的平均延滞影响图 30 6 4 2无交通信号交叉口 1 行人延滞讨论延滞 设想被迫延滞的人所处地位 面对进入或穿越交通流而不再延滞等候 是接受还是舍弃一间隙 成群行人等候进入人行横道就是这种情况的例子 如果假定主要衔道上交通流量为q 辆 秒 和主要街道上连续的车辆到达之间行人安全过街所需要的间隔为 临界间隙以秒计 则几个延滞关系式就可以推导出来 由前面的公式知 行人通过没有延滞的概率为 行人被迫延滞的概率为 6 63 6 64 31 主要街道上交通流量以每个最小可插车间隙所通过的车辆数来表示 阻塞 非阻塞 间隙和非间隙的平均延续时间以及行人为了寻找通过道路的适当的间隙所必须等候的时间 阻塞时间 道路事件被认为与所经过的时间t内车辆的通过有关 在t期间的事件数就是积累的交通虽qt 此外 平均车间时距 1 q 定义为T 每个时间间隔 h 是一个非阻塞的开始 因此也标志着一个阻塞的结束 所以在所经历的时间t中时间间隔数为 h 时 非阻塞数目 阻塞数目 间隙数目 6 65 在非阻塞中所消耗的时间为 6 66 在阻塞中所消耗的时间为 6 67 在间隙中总的时间消耗 图6 11 是非阻塞时间 非阻塞数目 的总和 6 68 32 而在间隙中消耗的时间比率为 6 69 该式就是亚当斯在1936年对行人交通延误的研究首先提出的 所有间隙的平均持续时间 秒 总的延误时间 间隙数 这就是亚当斯的方程III 所有间隔的平均延续时间 h 非间隙的平均长度 非间隙的总时间 h 的间隔数 这就是亚当斯的方程 图6 11行人延滞的概率图 6 71 6 70 33 阻塞的平均延续时间是 总的阻塞时间 阻塞的数目 而非阻塞的平均持续时间 最后这个方程可以用表达间隙长度的式 6 70 进行比较 表示间隙和非阻塞之间的关系式 6 72 34 在考虑延滞问题时 一个间隙的开始可定义为由于横向街道车辆或行人到达 以及在主要街道车辆的通道通过于以说明 一个行人的到达可能有两种状况 a 当事件恰遇间隙 没有延滞 或b 处于非间隙的间隔期间 后一种情况 到达车辆在可能穿过车流之前 必须等待间隙内的其余车辆 各间隙发生之间的平均车辆数 阻滞的车辆或行人所必须等待的 比方程6 73所给出的车辆数目少一个 即 6 74 由此表明预期的延滞E t 是等待的平均数 方程6 74 与间隙的平均长度 h 方程6 71 之积 即 6 73 6 75 35 将方程 6 75 绘成图6 12 其延滞以所需的最小横穿间隙来表示 所有被迫延滞的行人 其总延滞时间等于平均延滞 延滞的比率 图6 12汽车交通量与行人延滞关系图 6 76 36 最小的汽车交通量依据应用方程 6 76 来确定 该式以值为9 12 15和18秒时计算 绘在图6 13上 线AA说明在这条线下面的点延滞平缓地增加 在该线之上延滞迅增加 在每种情况下 v 是接近于6000 式中V 小时汽车交通量 3600q 为行人通过所要求的车辆之间的时间间距 秒 为了求得最小值 6 77 安德伍德提出的近似公式 式中 R 感觉时间 2秒或3秒 S 速度极限 英里 小时 W 道路宽度 英尺 v 过街速度 英尺 秒 约4英尺 秒 图6 13汽车交通量与行人延滞关系 37 最小的行人交通量采用每个非阻塞段平均一个行人 每非阻塞段平均有一个行人受到延滞时 延滞的行人数量是和行人延滞的比率为这样 一般在任何指定时间等候的行人不超过一名时 可以穿过车流的行人总数 6 78 这就是最小行人量的依据 无阻滞的车辆交通的比率是 其中P是每小时行人的交通量 g是人行横道上行人之间的时间间隔 即 行人之间有一最小的安全距离 安德伍德采用一辆汽车宽度 加上每边6英尺的净宽 为行人之间最小安全距离 对于8英尺宽的汽车来说 就要有20英尺的净空 行人之间的时间间隔根据g 20 v得出 式中v为行人过街速度 英尺 秒 所以 P 无延滞 6 79 对于60 概率 如果v 4英尺 秒 当行人的交通量超过360人 小时 设置信号是有根据的 38 安德伍德根据方程 6 77 6 78 和 6 79 绘制了一簇曲线 示于图6 14 虚曲线以左和以下的面积同每个最小的间隙有关 是行人和车辆交通量混合领域 无需处理 在同一簇曲线以右和以上 是需要步行标志的地带 当行人交通量超过360人 小时 需要设置交通控制信号 行人共同过街的平均批量为 图6 14对行人管制的依据 6 80 式中P是行人流量 q是车辆流量 图6 15表示了这个关系式 等待过衔的行人平均数为 图如6 16 6 81 39 图6 15行人共同过街的平均数图6 16等待过街的行人平均数 40 对于泊松分布的主要街道交通流 具有平均车间时距T和移位指数可插车间隙 则对于次要街道车辆的平均延滞 如同益尔曼和威斯的研究为 6 82 式中是最小的可插车间隙 q是主要街道车流 b是移位指数可插车间隙分布的参数 等于1 T 方程 6 82 可同方程 6 75 相比较 延滞具有可描车间隙恒值 在主要街道车流中 插车间隙t秒的概率F t 为 图6 18上面的曲线表示鼓尔曼与威斯的常数 3 3秒和b 2 7秒 1的关系式图解 下面的曲线表示假设有驾驶人都有3 3秒可插车间隙的结果 图6 18过街时平均延滞 6 83 41 如果行驶中的车辆需要一个间隙 和停止了的车辆需要间隙为则平均延滞为 举例 3 3设秒和 2 0秒 这些数值代入方程 6 84 使得出一条曲线 如图6 19所示 该图是次要街道车辆在让路标志处的平均延滞 把它和停车标志处情况相比较 后者需要所有次要街道驾驶人都停车 等候主要街道3 3秒的间隙 威斯进一步指出 当流量小于1600辆 小时 单独一辆车过街或在合流中的延滞 实际上同主要车流的速度分布无关 图6 19次要街道车辆的平均延滞 6 84 42 米勒提出主要街道车流间隙分布的不同方法 他设想成列车辆在一条公路上随机分布 设队列车流 成列 每单位时间为q 并规定为队列之间间距指数分布的参数 米勒令q与的关系为 式中是排队的平均长度 对于一个行人或次要街道上的车辆 米勒推导出乎均等待时间的表达式为 6 85 式中是最小的可插车间隙 和规定如前 次要街道车辆可以立即通过的概率按下式计算 6 86 图6 20给出了立即过街机会的观察值 和由两个理论模型14个组观测所预估的数值 每组收集资料1个小时 图6 20过街机会无延滞的比较 43 2 车辆延滞本节需要引入为反映第二车列就位接受或拒绝一个间隙所需要的延滞时间 伊文思 赫尔望和威斯 马狄和巴克力和阿士沃思及其他人曾讨论过 与主要街道上车辆合流或穿越之前 在次要街道或进口匝道上等候的队列车辆的情况 考虑在次要街道上一列无限长的车辆队列 处于下列条件 当主要街道车间时小于 不能有车辆进入 当主要街道车间时距在 和2 之间可能有一辆车进入 当主要街道车间时距在2 和3 之间 则可能有两辆汽车进入等等 马狄和巴克力提出有可能从次要街道进入的车辆数目N 求得如下表 每单位时间内进入或穿越主要街道车流的车辆数 通行能力 为 44 表6 1车间距数目量值表由此得 6 87 比较现实的假定是使跟随车辆的车头之间间距为 所以两辆汽车需要的车间时距为 三辆汽车需要的车间时距为 2等等 假定方程6 87变为 6 88 45 如假设每个非阻塞段只有一辆汽车进入 则次要街道的通行能力等于q辆 单位时间 阿士沃思修正了马秋和巴克力所使用的方法 假定驾驶人的临界间隙为秒 而第二名驾驶人为秒 进一步假定向前运行的时间等于常数秒 在这个时间内随着队列前头车的离去 第二辆汽车进入前面位置 但是没有可能利用任何适当的间隙 作者对于那些实际受到阻滞的车辆 提出排头车等候的乎均延滞时间 式中 对于所有车辆等候的平均延滞 如果 为 6 89 6 90 46 布鲁门费尔德和威斯论述了加速车道对于合流问题的影响 在他们的模型里 长度为L的加速车道上的车辆是假定以恒速v行驶 而在主要车道上的车辆以恒速V行驶 V v 该模型进一步假定合流的驾驶人继续沿着加速道以适度v前进 直到他找到一个合适的间隙或继续前进到加速道的末端 至此车速剧降为零 令表示车辆到达加速道末端的时间 L v 假设汇合发生在某一时间t 如果这段时间内驾驶人没有合流 则其行驶距离为Vt 以代替实际行驶的vt 其延滞可以确定为 式中 如果汇合的时间大于 设t 式中 o 则延滞确定为 47 图6 21到达加速道末端为合流的图6 22预期的延误与加概率与加速道长度的关系图速道长度的关系图 48 6 5 1瓶颈处的排队特性 1 符号Q 瓶颈上游车辆的平均到达率 辆 分 s 饱和车流或连续车流的通行能力 辆 分 Sr 堵