第六节-交通流理论-排队论
- 格式：ppt
- 大小：354.50 KB
- 文档页数：19
文档推荐
-
第4章 交通流理论页数:39
-
第四章交通流理论(详细版)页数:12
-
第六节-交通流理论-排队论页数:19
-
第八章 交通流理论页数:89
-
第四章 交通流理论页数:54
-
第4章 交通流理论页数:84
下载文档原格式
合集下载
第06章 排队论
-118-第六章 排队论模型排队论起源于1909年丹麦电话工程师A. K．爱尔朗的工作，他对电话通话拥挤问题进行了研究。
1917年，爱尔朗发表了他的著名的文章—“自动电话交换中的概率理论的几个问题的解决”。
排队论已广泛应用于解决军事、运输、维修、生产、服务、库存、医疗卫生、教育、水利灌溉之类的排队系统的问题，显示了强大的生命力。
排队是在日常生活中经常遇到的现象，如顾客到商店购买物品、病人到医院看病常常要排队。
此时要求服务的数量超过服务机构（服务台、服务员等）的容量。
也就是说，到达的顾客不能立即得到服务，因而出现了排队现象。
这种现象不仅在个人日常生活中出现，电话局的占线问题，车站、码头等交通枢纽的车船堵塞和疏导，故障机器的停机待修，水库的存贮调节等都是有形或无形的排队现象。
由于顾客到达和服务时间的随机性。
可以说排队现象几乎是不可避免的。
排队论（Queuing Theory）也称随机服务系统理论，就是为解决上述问题而发展的一门学科。
它研究的内容有下列三部分：（i）性态问题，即研究各种排队系统的概率规律性，主要是研究队长分布、等待时间分布和忙期分布等，包括了瞬态和稳态两种情形。
（ii）最优化问题，又分静态最优和动态最优，前者指最优设计。
后者指现有排队系统的最优运营。
（iii）排队系统的统计推断，即判断一个给定的排队系统符合于哪种模型，以便根据排队理论进行分析研究。
这里将介绍排队论的一些基本知识，分析几个常见的排队模型。
§1 基本概念1.1 排队过程的一般表示 下图是排队论的一般模型。
图1 排队模型图中虚线所包含的部分为排队系统。
各个顾客从顾客源出发，随机地来到服务机构，按一定的排队规则等待服务，直到按一定的服务规则接受完服务后离开排队系统。
凡要求服务的对象统称为顾客，为顾客服务的人或物称为服务员，由顾客和服务员组成服务系统。
对于一个服务系统来说，如果服务机构过小，以致不能满足要求服务的众多顾客的需要，那么就会产生拥挤现象而使服务质量降低。
排队论
G：一般分布。表示到达间隔时间或服务时间服从一般分布。G是General的第 一个字母。
EkE：rlkan-爱g 尔朗的分第布一。个表字示母到。达间隔时间或服务时间服从k-爱尔朗分布。E是 D: 定长分布 (常数时间)
H：超几何分布。
L：H项式分布。
Z代表的服务规程典型的有：
FCFS：先来先服务；LCFS：后来先服务；RSS：随机选择服务；
PR：优先权服务。 Ba：集体（批量）服务。 GD：一般规约服务，即通用规约服务。
排队论课件 23
3 基本排队关系
在对排队进行分析时，为了便于分析，经常做一些简化假设。对一个排队系 统，若满足以下三个条件：
（1）排队系统能够进入统计平衡状态；
（2）服务员的忙期与闲期交替出现，即系统不是总处于忙的状态；
泊松分布（Poisson）： P{X = k} = λk e-λ/ k! k=0,1,2,…， μx = σx = λ 泊松分布是最重要的离散型概率分布之一，也是表述随机
现象的一种重要形式。在实际系统模型中，一般都要假定任务 （或顾客）的到来是泊松分布的。实践也证明：这种假设有效。
如果顾客到达的人数是符合泊松分布，即在时间T内到达 有k个顾客到达的概率为：
♂
※
排队论课件
11
基本的排队模型
基本组成 概念与记号 指数分布和生灭过程
♂
排队论课件 12
典型排队系统模型
顾客到达: 在队列中排队 服务台服务 顾客离开
输入源
。。。
输入源的 特性？
到达规律 队列大小？
到达方式？
服务规律？
服务协议？
在本单元中，我们主要介绍排队系统的组成和特征，排队系统 的到达和服务，经典排队模型等内容。顾客到达规律和服务规 律都是通过概率来描述的，所以概率论是排队论的基础。
排队论ppt课件
N(t)，只与区间长度t有关而与时间起点t0无关。
数N(t)，与t0以前到达的顾客数独立。 或两个以上顾客的概率极小，可以忽略不计，即 ∞ ∑Pn(Δ t)＝o(Δ t)
n=2
在上述三个条件下可以推出 (λ t)n Pn(t)＝——— e-λt n!
n=0,1,2,……
其中λ 表示单位时间平均到达的顾客数，即为到达
顾客总数
服务时间总和
6.2 几个主要概率分布
6.2.2 普阿松分布 设N(t)表示在时间区间[t0,t0+t)内到达的顾客数，
是随机变量。当N(t)满足下列三个条件时，我们说顾客
的到达符合普阿松分布。这三个条件是： (1)平稳性 (2)无后效性 (3)普通性 在时间区间[t0,t0+t)内到达的顾客数 在时间区间[t0,t0+t)内到达的顾客 在充分短的时间区间Δ t内，到达两个
对于普阿松分布，λ 表示单位时间平均到达 的顾客数，所以1/λ 表示顾客相继到达的平均间 隔时间，而这正和E[T]的意义相符。 服务时间符合负指数分布时，设它的概率密
度函数和分布函数分别为
fv(t)＝μ e-μ t； Fv(t)＝1-e-μ t (t≥0)
其中μ 表示单位时间能够服务完的顾客数，为服 务率；而1/μ 表示一个顾客的平均服务时间，正 是v的期望值。
...
n+1
...
m-1 μ
m
系统处于稳态时的概率方程如下： mλP0=μP1 (m-n+1)λPn-1+μPn+1= (m-n)λPn+ μPn （n<m) μPm=λP m-1 考虑到 P0+ P1+… + Pm=1, 解得
交通流理论—排队论
组成
排队系统的组成 (1) 输入过程：就是指各种类型的"顾客(车辆或行人)"按怎样的规律到 达。有各式各样的输入过程，例如： D—定长输入：顾客等时距到达。 M—泊松输入：顾客到达时距符合负指数分布。 Ek—爱尔朗输入：顾客到达时距符合爱尔朗分布。
组成
排队系统的组成
(2)排队规则：指到达的顾客按怎样的次序接受服务。 例如： • 损失制：顾客到达时，若所有服务台均被占，该顾客就自动消失，永不再来。 • 等待制：顾客到达时，若所有服务台均被占，他们就排成队伍，等待服务，
离去 1
到达
离去 2
到达 1
离去
2
...
n
单通道多服务台系统
到达
离去
1
到达
离去
(组1)成单通道服务系统
到达
离去
服务台的排列方式1
服务台
单通道单服务台系统
(2)多通道服务系统
(2) 多通道服务系统
离去
1
到达
离去 2
3
离去
可通的多通道系统
到达 1
离去
2
...
n
单通道多服务台系统
到达
离去
1
到达
离去
2
到达
M/M/1系统及其应用
其他参数
平均非零排队长度：
qw
1
1
(qw q ) （辆）
即排队不计算没有顾客的时间，仅计算有顾客时的平均排队长度， 即非零排队。如果把有顾客时计算在内，就是前述的平均排队长度。
M/M/1系统及其应用
其他参数
系统中顾客数超过k的概率：
P(n k) 1 P(n k)
k
1- Pi 1 (1 (1 ) ... k (1 )) i 0
交通流理论排队论模型跟弛模型与交通波模型
2.说明：排队等待的车辆从一开始起动,就产生了起 动波,该波以接近 的v f 速度向后传播。
交通运输与物流学院
29
交通流中观测的加速度
把速度简单地看成密度的函数v(k)，使得求解连续方程变得简单。 现实中交通流的平均速度v不可能瞬时地随密度发生变化，驾驶
员总是根据前方密度来调整车速
dv
k
dv
2
17
跟驰模型稳定性
多数个车辆在做跟驰运动时，一辆车状态的改变会导致其后续车 辆运行状态接二连三的改变，称为运行状态的传播
局部稳定 关注跟驰车对引导车运行波动的反应。如车头间距摆 动大则不稳定，摆动愈小则愈稳定
引导车向后面各车传播速度变化，如果速度振幅扩大，就是不稳 定，如果振幅衰减，就是渐近稳定
C T
Reuschel, Pipes
跟驰车辆的加速度与 两车速度差成比例
Chandler, Herman, Kometani and Sasaki
Gazis, Herman （跟驰模型一般形式）
m, l 的不同取值对应着不同的密度－速度关系模型
m=0, l=2, Greenshield; m=0, l=1, Grenberg 交通运输与物流学院
交通运输与物流学院
32
密度波模型
在交通流中存在密度不连续 的地方，密度在该处的移动
速度是C。单位时间内通过
断面A、B车辆数的差等于 断面内滞留的车辆数。
波阵面
(q q) q C(k k k)
C q k
C dq dk
交通运输与物流学院
33
密度波传播分析1
密度波描述了两种交通状态的转化过程，C代表转化的方向与进程
解这是一个M/M/1排队系统
第六章排队论-PPT精选
(1)损失制。这是指如果顾客到达排队系
统时，所有服务台都被先到的顾客占用， 那么他们就自动离开系统永不再来。
2．服务规则
(2)等待制 这是指当顾客来到系统时，所有服务台
都不空，顾客加入排队行列等待服务。等待制中，服务 台在选择顾客进行服务时常有如下四种规则： 1)先到先服务。按顾客到达的先后顺序对顾客进行服务。 2)后到先服务。 3)随机服务。即当服务台空闲时，不按照排队序列而随 意指定某个顾客接受服务。 4)优先权服务。
②排队等待的顾客数(排队长)的期望值Lq； ③顾客在系统中全部时间(逗留时间)的期望值W；
④顾客排队等待时间的期望值Wq。
第二节 M／N／1模型
模型的条件是： 1、输入过程――顾客源是无限的，顾客到
达完全是随机的，单个到来，到达过程 服从普阿松分布，且是平稳的； 2、排队规则――单队，且队长没有限制， 先到先服务； 3、服务机构――单服务台，服务时间的长 短是随机的，服从相同的指数分布 。
第六章 排 队 论
随机服务系统理论
第六章 排 队 论
排队系统描述 基本概念 M / M / 1 模型 M / M / S 模型
第一节 排队系统描述
顾客－－－要求服务的对象统称为“顾 客”
服务台－－－把提供服务的人或机构称 为“服务台”或“服务员”
各种形式的排队系统
各种形式的排队系统
(2)其他常用数量指标
Pn PNn:稳态系统任一 为n时 的刻 概状
特别n＝ 当0时（系统中0顾 ）客 ，数为 P0即稳态系统所 全有 部服 空务 闲台 的概
(2)其他常用数量指标
ρ ——服务强度，即每个服务台单位时间内的平 均服务时间，—般有ρ =λ ／(sμ )，这是衡量 排队系统繁忙程度的重要尺度，当ρ 趋近于0时， 表明对期望服务的数量来说，服务能力相对地 说是很大的。这时，等待时间一定很短，服务 台有大量的空闲时间；如服务强度ρ 趋近于1， 那么服务台空闲时间较少而顾客等待时间较多。 我们一般都假定平均服务率μ 大于平均到达率 λ ，即λ /μ <1,否则排队的人数会越来越多， 以后总是保持这个假设而不再声明。
统时，所有服务台都被先到的顾客占用， 那么他们就自动离开系统永不再来。
2．服务规则
(2)等待制 这是指当顾客来到系统时，所有服务台
都不空，顾客加入排队行列等待服务。等待制中，服务 台在选择顾客进行服务时常有如下四种规则： 1)先到先服务。按顾客到达的先后顺序对顾客进行服务。 2)后到先服务。 3)随机服务。即当服务台空闲时，不按照排队序列而随 意指定某个顾客接受服务。 4)优先权服务。
②排队等待的顾客数(排队长)的期望值Lq； ③顾客在系统中全部时间(逗留时间)的期望值W；
④顾客排队等待时间的期望值Wq。
第二节 M／N／1模型
模型的条件是： 1、输入过程――顾客源是无限的，顾客到
达完全是随机的，单个到来，到达过程 服从普阿松分布，且是平稳的； 2、排队规则――单队，且队长没有限制， 先到先服务； 3、服务机构――单服务台，服务时间的长 短是随机的，服从相同的指数分布 。
第六章 排 队 论
随机服务系统理论
第六章 排 队 论
排队系统描述 基本概念 M / M / 1 模型 M / M / S 模型
第一节 排队系统描述
顾客－－－要求服务的对象统称为“顾 客”
服务台－－－把提供服务的人或机构称 为“服务台”或“服务员”
各种形式的排队系统
各种形式的排队系统
(2)其他常用数量指标
Pn PNn:稳态系统任一 为n时 的刻 概状
特别n＝ 当0时（系统中0顾 ）客 ，数为 P0即稳态系统所 全有 部服 空务 闲台 的概
(2)其他常用数量指标
ρ ——服务强度，即每个服务台单位时间内的平 均服务时间，—般有ρ =λ ／(sμ )，这是衡量 排队系统繁忙程度的重要尺度，当ρ 趋近于0时， 表明对期望服务的数量来说，服务能力相对地 说是很大的。这时，等待时间一定很短，服务 台有大量的空闲时间；如服务强度ρ 趋近于1， 那么服务台空闲时间较少而顾客等待时间较多。 我们一般都假定平均服务率μ 大于平均到达率 λ ，即λ /μ <1,否则排队的人数会越来越多， 以后总是保持这个假设而不再声明。
排队论参考资料(交通流)
任意1km路段上，试求： ✓ 无车的概率； ✓ 小于5辆车的概率； ✓ 不多于5辆车的概率； ✓ 6辆及其以上的概率； ✓ 至少为3辆但不多于6辆的概率； ✓ 恰好为5辆车的概率。
2020/8/17
77
一、离散型分布
解：这里t 理解为车辆数的空间间隔，λ为车辆平 均分布率，m 为计数空间间隔内的平均车辆数。
Q=360辆/h
7.5m
24 24
二、连续性分布
解：行人横过单向行车道所需要的时间：
t =7.5/1=7.5s
因此，只有当h≥7.5s时，行人才能安全穿越，由
于双车道道路可以充分超车，车头时距符合负指
数分布，对于任意前后两辆车而言，车头时距大
于7.5s的概率为：
Qt
3607.5
P(h7.5) e 3600 e 3600 0.4724
由λ=60/10 t=1 ，因此m =λt=6（辆）
这里m即为计数空间间隔内的平均车辆数。
P(0) em e6 0.0025
P(1)
m 1
P(0)
0.0149
P( 2 )
m 2
P(1)
0.0446
P( 3 )
m 3
P( 2 )0.0892P(源自)m 4P( 3 )
0.1338
P(5)
m 5
P(4)
来车的分布为：
P(k )
mk k!
em
4k k!
e 4
求：P(k) 0.95 的k值。
2020/8/17
11 11
一、离散型分布
k
P(k)
P(≤k)
k
P(k)
P(≤k)
0 0.0183 0.0183 5 0.1563 0.7852
2020/8/17
77
一、离散型分布
解：这里t 理解为车辆数的空间间隔，λ为车辆平 均分布率，m 为计数空间间隔内的平均车辆数。
Q=360辆/h
7.5m
24 24
二、连续性分布
解：行人横过单向行车道所需要的时间：
t =7.5/1=7.5s
因此，只有当h≥7.5s时，行人才能安全穿越，由
于双车道道路可以充分超车，车头时距符合负指
数分布，对于任意前后两辆车而言，车头时距大
于7.5s的概率为：
Qt
3607.5
P(h7.5) e 3600 e 3600 0.4724
由λ=60/10 t=1 ，因此m =λt=6（辆）
这里m即为计数空间间隔内的平均车辆数。
P(0) em e6 0.0025
P(1)
m 1
P(0)
0.0149
P( 2 )
m 2
P(1)
0.0446
P( 3 )
m 3
P( 2 )0.0892P(源自)m 4P( 3 )
0.1338
P(5)
m 5
P(4)
来车的分布为：
P(k )
mk k!
em
4k k!
e 4
求：P(k) 0.95 的k值。
2020/8/17
11 11
一、离散型分布
k
P(k)
P(≤k)
k
P(k)
P(≤k)
0 0.0183 0.0183 5 0.1563 0.7852
上海交通大学管理科学-运筹学课件第六章排队论
第6章 排队论在日常生活和工作中，人们常常会为了得到某种服务而排队等候。
比如顾客到商店购买东西，病人到医院看病，汽车进加油站加油，轮船进港停靠码头等，都会因为拥挤而发生排队等候的现象。
这时，商店的售货员和顾客，医院的医生和病人，加油站的加油泵和待加油的汽车，码头的泊位和停泊的轮船等，形成了各自的排队服务系统，简称排队系统。
在一个排队系统中，通常包括一个或多个“服务设施”，服务设施可以指人，如售货员，医院大夫等。
也可以是物，如加油泵、码头泊位等。
同时还包括许多进入排队系统要求得到服务的“顾客”。
这里的顾客是指请求服务的人或物。
如到医院看病的病人，或等待加油的汽车等。
作为顾客总希望一到系统马上就能得到服务，但客观情况并非如此。
由于顾客的到达和服务机构对每个顾客的服务时间具有随机性，因此出现排队现象几乎是不可避免的。
当然，为了方便顾客减少排队时间，排队系统可以多开设服务设施。
但那将增加系统的投资和运营成本，还可能发生空闲浪费。
排队论（Queueing Theory ）是为解决上述问题而发展起来的一门学科。
排队论起源于上世纪初，当时的美国贝尔（Bell ）电话公司发明了自动电话后，满足了日益增长的电话通讯的需要。
但另一方面，也带来了新的问题，即如何合理配置电话线路的数量，以尽可能减少用户的呼叫次数。
如今，通讯系统仍然是排队论应用的主要领域。
同时在运输、港口泊位设计、机器维修、库存控制等领域也获得了广泛的应用。
6. 1 排队系统的基本概念6. 1. 1排队系统的一般表示一个排队系统可以抽象描述为：为了获得服务的顾客到达服务设施前排队，等候接受服务。
服务完毕后就自行离开。
其中把要求得到服务的对象称为顾客，而把服务者统称为服务设施或服务台。
在排队论中，把顾客的到达和离开称为排队系统的输入和输出。
而潜在的顾客总体又称为顾客源或输入源。
因此任何一个排队系统是一种输入－输出系统，其基本结构如图6-1所示。
排队系统图6-16. 1. 2排队系统的特征由排队系统的基本结构可知，任何一个排队系统的特征可以从以下三个方面加以描述。
交通工程学 交通流理论
S 2
1 N 1
N i 1
( xi
m)2
1 N 1
n
(x j m)2 f j
j 1
•
1
N
（
N 1 i1
xi2
Nm2 )
• n: 观测数据分组数
•
数f i的:频在率全（部即的对观应测的时计间数内间,在隔计的数次间数隔）t内事件K发生次
•
N: 观测的总周期（观测的间隔总数），此时观测的
总时间为T＝Nt
第八章 交通流理论
• 由于泊松分布的均值 M 和方差 D均等于λt；
而观测数据的均值 m和 S2均为无偏估计，因此， 当观测数据表明S2/m显著不等于1时，就是泊 松分布不合适的表征，所以，应选择其他分布 形式。
第八章 交通流理论
例1 设60辆车随机分布在4km长的道路上，求任意400m路 段上有4辆及4辆车以上的概率
解：行人横过单向行车道所需要的时间：
t =7.5/1=7.5s
因此，只有当h≥7.5s时，行人才能安全穿越，由 于双车道道路可以充分超车，车头时距符合负指 数分布，对于任意前后两辆车而言，车头时距大 于7.5s的概率为：
Qt
3607.5
P(h7.5) e 3600 e 3600 0.4724
车头时距分布的概率密度曲线一般总是 先升后降。
2020/2/1
31
二、排队论的基本概念
• “排队”与“排队系统”
➢ 当一队车辆通过收费站，等待服务（收费）的车 辆和正在被服务（收费）的车辆与收费站构成一 个“排队系统”。
➢ 等候的车辆自行排列成一个等待服务的队列，这 个队列则称为“排队”。
排队论(讲义)ppt课件
概率关系着对时间的数量分配。一个事件A的概率 P(A)是对应事件A要发生可能性 的数量分配。概率有很多不同的定义，常用的有三种：
(1)古个典数定。义：P(A)=NA/N 其中N是可能结果的总个数，NA是事件A在其中发生的结果的
例1. 求抛两个骰子并且决定和为7的概率p。
总共有36种可能的结果，所以N= 36
排队论 Queueing Theory
主讲：周在莹
；.
1
CONTENUNIT 1 排队模型
UNIT 2 排队网络模型
UNIT 3 应用之：QUICK PASS系统
结束语
；.
PREPARATION 概率论和随机过程
Part 1．概率论基础
1。 概率的定义
独立性： 如果P(AB)=P(A)P(B)，事件A和B叫做相互独立的事件 独立性的概念可以推广到三个或多个事件。
；.
3 全概率公式和贝叶斯定理 全概率公式：给定一组互斥事件E1，E2，，…，En，这些事件的并集包括所有可能的
结果，同时给任一个任意事件A，那么全概率公式可以表示为： n
P(A)=∑P(A|Ei)P(Ei) i=1
在离散型随机变量中，只有几何分布具有无后效性。这两种分布可以分别用来描 绘离散等待时间和连续等待时间。
在排队理论中，指数分布是很重要的。
；.
6 k-爱尔朗分布 概率密度: f(x)= (λkx)n-1λke-λkx /(n-1)! x≥0，λ>0.
0 x<0 数字特征： E[X]=1/λ; Var[X]=1/（kλ2 ）
；.
5 （负）指数分布
它是一种连续型的概率分布，它的概率密度为
f（x）= λe-λx x≥0
0
排队论
授 课 内 容 备注、更新第6章 排队论（1）排队是指因车辆数量超过服务设施的容量，致使车辆得不到及时服务而等候的现象。
（2）排队论则是研究排队现象及其规律性的理论。
（3）在交通工程中，排队论被广泛用于车辆延误、通行能力、信号灯配时以及停车场、收费亭、加油站等交通设施设计与管理等方面的研究中。
6.1 概述6.1.1排队系统基本组成1. 输入过程（1）定义：输入过程是指各种类型接受服务的车辆(或行人等)按怎样的规律到达（2）种类：①定长输入：车辆均匀到达，车头时距相同；②泊松输入：车辆到达符合泊松分布，车头时距服从负指数分布；③爱尔朗输入：车辆到达车头时距符合爱尔朗分布。
2. 排队规则（1）定义：排队规则是指到来的车辆按怎样的次序接受服务。
（2）分类：①等待制：车辆到达时，如若所有服务台均被占用，则该车辆便排队等候服务，称为等待制。
②损失制：车辆到达时，如若所有服务台均被占用，则该车辆不排队等候，称为损失制；③ 混合制：如果车辆到达时，若队长小于L，就加入排队队伍；若队长大于等于L，车辆就离去。
3.输出方式（1）定义：是指同一时刻有多少服务台可接纳车辆，每一车辆服务了多少时间。
（2）分类：①定长分布：每一车辆的服务时间都相等；②负指数分布：每一车辆的服务时间相互独立，且都服从相同的负指数分授 课 内 容备注、更新布；③ 爱尔朗分布：每一车辆的服务时间相互独立，具有相同的爱尔朗分布。
6.1.2 排队系统的主要特征指标① 服务率：它为单位时间内被服务的车辆均值。
② 交通强度：单位时间内被服务的车辆数与请求服务的车辆数之比。
③ 系统排队长度：可分为系统内的平均车辆数（Ls ）和排队等待服务平均车辆数（Lq ）。
常用于描述排队系统的服务水平。
④ 等待时间：从车辆到达时起到他开始接受服务时止这段时间。
⑤ 车辆在系统内的时间：等于车辆排队等待时间与接受服务时间之和。
6.1.3排队系统的分类记号（1）肯达尔（Kendall ）于1953年提出了排队系统的分类记号：输入分布/输出分布/并联的服务站数。
第六章排队论 ppt课件
3) 普遍性：在 t 时间内到达一个顾客的概率为 t +o(t )，
到达两个或两个以上顾客的概率为 o(t )；即两个顾客不可 能同时到达 • 泊松过程具有可迭加性 – 即独立的泊松分布变量的和仍为泊松分布
21
6.3.2.2 负指数分布
（1）推导
• 泊松过程的到达间隔时间为负指数分布 – 令 h 代表间隔时间，则概率 P{h > t}代表时间区间 △t 内没有顾客来的概率；由泊松分布
第六章 随机服务系统理论
排队论
Queuing Theory
确定型只是随机现象的特例
1
6.1 随机服务系统基础
• 系统的输入与输出是随机变量 • A.k.Erlang 于1909~1920年发表了一系列根据话务量计
算电话机键配置的方法，为随机服务理论奠定了基础 • 又称为排队论(Queuing Theory)或拥塞理论(Congestion
PB3 (1 / 8)PA0 (1 / 8)
(16 1 / 8)3 3!
e 161 / 8
e 81 / 8
0.0664
(2) 3 个顾客全是购买 B 类商品的概率为
Pn ( t ) 0
n2
26
例-2
某铁路与公路相交的平面交叉口，当火车通过 交叉口时，横木护栏挡住汽车通行。每次火车 通过时，平均封锁公路3min，公路上平均每分 钟有4辆汽车到达交叉口。求火车通过交叉口 时，汽车排队长度超过100m的概率（即排队 汽车超过12辆的概率）。
笨，没有学问无颜见爹娘 ……” • “太阳当空照，花儿对我笑，小鸟说早早早……”
4
6.1.1 基本要素
排队系统的三个基本组成部分. •输入过程 (顾客按照怎样的规律到达); •排队规则 (顾客按照一定规则排队等待服务); •服务机构 (服务机构的设置,服务台的数量,服务的 方式,服务时间分布等)
到达两个或两个以上顾客的概率为 o(t )；即两个顾客不可 能同时到达 • 泊松过程具有可迭加性 – 即独立的泊松分布变量的和仍为泊松分布
21
6.3.2.2 负指数分布
（1）推导
• 泊松过程的到达间隔时间为负指数分布 – 令 h 代表间隔时间，则概率 P{h > t}代表时间区间 △t 内没有顾客来的概率；由泊松分布
第六章 随机服务系统理论
排队论
Queuing Theory
确定型只是随机现象的特例
1
6.1 随机服务系统基础
• 系统的输入与输出是随机变量 • A.k.Erlang 于1909~1920年发表了一系列根据话务量计
算电话机键配置的方法，为随机服务理论奠定了基础 • 又称为排队论(Queuing Theory)或拥塞理论(Congestion
PB3 (1 / 8)PA0 (1 / 8)
(16 1 / 8)3 3!
e 161 / 8
e 81 / 8
0.0664
(2) 3 个顾客全是购买 B 类商品的概率为
Pn ( t ) 0
n2
26
例-2
某铁路与公路相交的平面交叉口，当火车通过 交叉口时，横木护栏挡住汽车通行。每次火车 通过时，平均封锁公路3min，公路上平均每分 钟有4辆汽车到达交叉口。求火车通过交叉口 时，汽车排队长度超过100m的概率（即排队 汽车超过12辆的概率）。
笨，没有学问无颜见爹娘 ……” • “太阳当空照，花儿对我笑，小鸟说早早早……”
4
6.1.1 基本要素
排队系统的三个基本组成部分. •输入过程 (顾客按照怎样的规律到达); •排队规则 (顾客按照一定规则排队等待服务); •服务机构 (服务机构的设置,服务台的数量,服务的 方式,服务时间分布等)
第六节 交通流理论-排队论
(3)系统中的平均车辆数： P(0) n . N! N (1 / N ) 2
N 1
（4）平均排队长度：q nຫໍສະໝຸດ (5)系统中的平均消耗时间 ：
d q
1
n
(6)排队中的平均等待时间 ：
q
例3. 一加油站，今有2400辆/h的车流量通过4个通道引向4个 加油泵，平均每辆车加油时间为5s，服从负指数分布，试按多 路多通道系统（4个M/M/1系统 ）单路多通道系统（M/M/4系统） 计算各相应指标。
n 1 6
计算结果表明排队车辆 数超过6辆的可能性极小，故可 认为该出入道的 存车量是合理的。
四、M/M/N系统
1.计算公式 设为进入多通道服务系统 车辆的平均到达率，排 队行列从每个服务台 接受服务后的平均输出 率为，则每个服务台的平均 服务时间是 1 / 。 仍记 / ，则 / N称为M / M / N系统的服务强度或交通 强度，亦可称 为饱和度。和M / M / 1相仿，当 / N 1时系统是稳定的，否则 不稳定，排 队长度将趋向于无穷大 。 M / M / N系统根据车辆排队方式 的不同，可分为： 1 ）单路排队多通道服务 ：指排成一个队等待数 条通道服务的情况，排 队 中头一车辆可视哪条通 道有空就到哪里去接受 服务； 2）多路排队多通道服务 ：指每个通道各排一个 队，每个通道只为其相 应 的一队车辆服务，车辆 不能随意换队。此种情 况相当于N个M / M / 1系统 组成的系统，其计算公 式亦相同。 对于单路排队多通道服 务的M / M / N系统，计算公式如下：
第八章 交通流理论
第三节 排队论的应用
一、引言
• 排队论是研究“服务”系统因“需求”拥挤而产生等待行列即排队的 现象，以及合理协调需求与服务关系的一种数学理论，是运筹学中以 概率论为基础的一门重要分支，亦称“随机服务系统理论”。 • 典型的例子——食堂排队； • 排队论是20世纪初开始发展的。1905年丹麦哥本哈根电话工程师爱尔 朗首先在电话自动交换机设计时应用排队论。使电话机既能满足通话 需求而又不致设线过多。第二次世界大战以后，排队论在很多领域内 被采用。在交通工程中，对于研究车辆延误、通行能力、信号灯配时 以及停车场、加油站等交通设施的设计与管理方面得到广泛的应用。 1936年亚当斯（Adams.W.F）用以考虑未设置交通信号交叉口的行人 延误问题，1951年唐纳予以推广应用，1954年伊迪（ Edie ）应用排 队模型估计收费亭的延误。同年在摩斯柯维茨的报告中，将其应用于 车辆等候交通流空档的实验报告。
交通流理论与方法---排队论
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公式，只要知道服务时间μ的期望和方差， 不管μ是服从什么分布，都可以求出系统的运行指标。
6.2排队理论的基本概念
• 6.2.1 “排队”与“排队系统”
“排队”单指等待服务的顾客（车辆或行人），不包括正在被服 务的顾客；而“排队系统”既包括了等待服务的顾客，又包括了正在 被服务的顾客。
• 6.2.2 排队系统的组成部分
1．输入过程 就是指各种类型的顾客按怎样的规律到来。常见的有如下几种服务 过程： （1）定长输入——顾客等时距到达。 （2）泊松输入——顾客到达符合泊松分布或顾客到达时距符合负指 数分布过程，这种分布最容易处理，因而应用最广泛。 （3）爱尔朗输入——顾客到达时距符合爱尔朗分布。
有效绿灯时间：周期中等候在入口的车 辆，假定以当量小客车为单位，以恒速通过信 号的时间。格林希尔兹等人，在研 究一队n辆停着的汽车，通过交通信号的总时 间，提出如下计算公式： 当n≥5，总时间＝14.2+2.1 (n-5)秒 要是所有车辆在饱和率s(1／2.1)时离去，前五 辆汽车须要有10.5秒，即有效绿灯时间是绿灯 信号时间减去3.7秒，虽然有效绿灯时间可以调 整适应于车辆具体运行条件，但是在大多数研 究中均假设排队等候的车辆可以利用黄灯的净 时隙。在入口上，一辆小客车到达时间和离去 时间的意义，可以参考图6.6来说明。 图中画了四辆汽车每辆的距离一时间曲线。AB 表示车辆通过没有延滞，PQ线表示停车线，有 排队时第一辆车停在那里等候。CDEF表示第一辆车 由于信号延滞的的轨迹。
第六部分 排队论
第七部分 排队论第十九章 排队论排队论又称随机服务系统理论，它是通过对各种服务系统在排队等待现象中概率特性的研究，来解决服务系统最优设计与最优控制一门学科。
目前，排队论已在计算机系统、计算机通信网络系统、电子对抗系统、交通运输系统、医疗卫生系统、库存管理系统、军事作战系统等方面有着重要的应用，并已成为工程技术人员、管理人员在系统分析与设计中的重要数学工具之一。
§1 排队系统的基本概念在人们的日常生活中，一个服务系统在工作过程中由于拥挤而产生的排队等待现象是经常发生的.例如，顾客在理发店内等待理发（见图）、用户在电话机前等候通话、发生故障的机器等候工人修理、进入机场上空的飞机等候降落等等。
如果我们把服务系统的含义再拓广一下，则进入雷达接收机的信号等待处理、通信系统的报文在缓冲器上等候传送、多微机系统的处理机等候访问公共内存、计算机网的用户等候使用某资源、进入水库的流水等待开闸泄放等等都可看作服务系统在运行过程中所产生的排队等候现象。
我们就将这种具有排队等候现象的服务系统通称为排队系统。
任何一个服务系统总是由两个相辅相成的要素：顾客和服务员（或服务台）所构成。
凡是要求接受服务的人与物统称为顾客；凡是给予顾客服务的人与物统称为服务员（或服务台）。
对于一个排队系统来说，如果顾客的到达时刻和对顾客的服务时间是固定的话，人们总可以适当安排或调整服务员个数、服务速率，从而使顾客到达后少排队甚至不排队而迅速进入服务，亦即容易达到供求之间的平衡关系，如通常情况下的火车调度就属于以上情况。
然而由于客观环境的复杂多变以及种种随机因素的影响，使得在绝大数情况下，顾客到达服务系统的时刻以及对顾客的服务时间都是随机的，这就给服务系统造成了一系列供求之间的矛盾。
例如，有时顾客到得多而服务跟不上（供不应求），而另一些时候则由于顾客少（或无顾客）而使服务员处于空闲状态（供过于求）。
因此，排队论的主要任务就是：通过对排队系统概率规律性的探讨来寻求某些能达到供求平衡的手段与策略，这也就是排队系统的所谓最优设计与最优控制问题。
排队论课件ppt
2023最新整理收集 do
something
第十章 排队论
Operational Research ( OR )
引言
生灭过程和Poisson过程
本
M/M/s等待制排队模型
章
M/M/s混合制排队模型
内
其他排队模型简介
容
排队系统的优化
分析排队系统的模拟方法
排队系统特征及排队论
排队 系统 的特 征及 排队 论
服
L npn n(1 ) n
n0
n1
务 台
( 2 2 33 …) ( 2 23 3 4 …)
2
3
…=
1-
模
平均排队长Lq为：
型
Lq (n 1) pn L (1 p0 )
n1
L 2 2
1 ( )
关于顾客在系统中的逗留时间T，可说明它服从参 数为μ-λ
单
P T t e()t t≥0
(3) 普通性： 在［t,t+Δt］内多于一个顾客到达的概 率为o(Δt)。 则称{N(t),t≥0}为Poisson过程。
生 灭 过 程 和
Poisson 过 程
定理1
设N(t)为时间［0,t］内到达系统的顾客数，则
{N(t),t≥0}为Poisson过程的充分必要条件是：
PN (t) n (t)n et
的
(3) 系统优化问题，又称为系统控制问题或系统运营问
题，其基本目的是使系统处于最优或最合理的状态。
基
系统优化问题包括最优设计问题和最优运营问题，其
内容很多，有最少费用问题、服务率的控制问题、服
本
务台的开关策略、顾客(或服务)根据优先权的最优排
序等方面的问题。
something
第十章 排队论
Operational Research ( OR )
引言
生灭过程和Poisson过程
本
M/M/s等待制排队模型
章
M/M/s混合制排队模型
内
其他排队模型简介
容
排队系统的优化
分析排队系统的模拟方法
排队系统特征及排队论
排队 系统 的特 征及 排队 论
服
L npn n(1 ) n
n0
n1
务 台
( 2 2 33 …) ( 2 23 3 4 …)
2
3
…=
1-
模
平均排队长Lq为：
型
Lq (n 1) pn L (1 p0 )
n1
L 2 2
1 ( )
关于顾客在系统中的逗留时间T，可说明它服从参 数为μ-λ
单
P T t e()t t≥0
(3) 普通性： 在［t,t+Δt］内多于一个顾客到达的概 率为o(Δt)。 则称{N(t),t≥0}为Poisson过程。
生 灭 过 程 和
Poisson 过 程
定理1
设N(t)为时间［0,t］内到达系统的顾客数，则
{N(t),t≥0}为Poisson过程的充分必要条件是：
PN (t) n (t)n et
的
(3) 系统优化问题，又称为系统控制问题或系统运营问
题，其基本目的是使系统处于最优或最合理的状态。
基
系统优化问题包括最优设计问题和最优运营问题，其
内容很多，有最少费用问题、服务率的控制问题、服
本
务台的开关策略、顾客(或服务)根据优先权的最优排
序等方面的问题。
交通流理论ppt课件
可编辑课件
1nti 100% T0
17
时间占有率与交通密度
时间占有率可以代替交通密度吗？
Ot
1 T
Q i1
ti
100(%)
ti li /vi
平均车长 l
l Q1
Ot
1 vi 10% 0lQ10(0%)
T
vs
时间占有率与交通密度成正比例
可编辑课件
18
连续流与间断流 Page 80
连续流
道路上行驶的车流不因外界因素干扰而停车 在没有停车或让路一类的交通标志的高速公路上 在没有信号交叉口之间的乡村路段上
计数间隔被分割成n个区间
t/n
λ
计数间隔 t
p
可编辑课件
38
负指数分布 1
基本公式
计数间隔t内没有车辆到达的概率为 P(0) = e－λt
在无车辆到达的时间间隔t内，上次车到达和下次车到达之间，
车头时距至少有t秒，换句话说，P(0)也是车头时距等于或大于t
秒的概率，于是
P( h ≥ t )=e－λt
• 密度－速度关形式的多样性
• 自由流是…
Vm
• 交通量是密度、速度的函数
• 在临界点处…
Qmax
是交通模拟模型的理论基础
可编辑课件
13
xs
1 N
N i1
xi
1 N
N 1
xi
ts
1 M
M
ti
i1
1 M
t M
1
i
可编辑课件
车头间距 space headway
车头时距 time headway
交通量（速度）
VVf aK Ka1Va1Vf
1nti 100% T0
17
时间占有率与交通密度
时间占有率可以代替交通密度吗？
Ot
1 T
Q i1
ti
100(%)
ti li /vi
平均车长 l
l Q1
Ot
1 vi 10% 0lQ10(0%)
T
vs
时间占有率与交通密度成正比例
可编辑课件
18
连续流与间断流 Page 80
连续流
道路上行驶的车流不因外界因素干扰而停车 在没有停车或让路一类的交通标志的高速公路上 在没有信号交叉口之间的乡村路段上
计数间隔被分割成n个区间
t/n
λ
计数间隔 t
p
可编辑课件
38
负指数分布 1
基本公式
计数间隔t内没有车辆到达的概率为 P(0) = e－λt
在无车辆到达的时间间隔t内，上次车到达和下次车到达之间，
车头时距至少有t秒，换句话说，P(0)也是车头时距等于或大于t
秒的概率，于是
P( h ≥ t )=e－λt
• 密度－速度关形式的多样性
• 自由流是…
Vm
• 交通量是密度、速度的函数
• 在临界点处…
Qmax
是交通模拟模型的理论基础
可编辑课件
13
xs
1 N
N i1
xi
1 N
N 1
xi
ts
1 M
M
ti
i1
1 M
t M
1
i
可编辑课件
车头间距 space headway
车头时距 time headway
交通量（速度）
VVf aK Ka1Va1Vf
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
n =1 6
计算结果表明排队车辆数超过6辆的可能性极小，故可认为该出入道的 存车量是合理的。
四、M/M/N系统 系统
1.计算公式 在M / M / N排队系统中，服务通道有N条，所以也叫“多通道服务”系统。 设λ为进入多通道服务系统车辆的平均到达率，排队行列从每个服务台 接受服务后的平均输出率为µ，则每个服务台的平均服务时间是1 / µ。 仍记ρ = λ / µ，则ρ / N称为M / M / N系统的服务强度或交通强度，亦可称 为饱和度。和M / M / 1相仿，当ρ / N < 1时系统是稳定的，否则不稳定，排 队长度将趋向于无穷大。 M / M / N系统根据车辆排队方式的不同，可分为： 1 ）单路排队多通道服务：指排成一个队等待数条通道服务的情况，排队 中头一车辆可视哪条通道有空就到哪里去接受服务； 2）多路排队多通道服务：指每个通道各排一个队，每个通道只为其相应 的一队车辆服务，车辆不能随意换队。此种情况相当于N个M / M / 1系统 组成的系统，其计算公式亦相同。 对于单路排队多通道服务的M / M / N系统，计算公式如下：
第八章 交通流理论
排队论的应用 第三节 排队论的应用
一、引言
排队论是研究“服务”系统因“需求”拥挤而产生等待行列即排队的现象， 排队论是研究“服务”系统因“需求”拥挤而产生等待行列即排队的现象， 是研究 以及合理协调需求与服务关系的一种数学理论， 需求与服务关系的一种数学理论 以及合理协调需求与服务关系的一种数学理论，是运筹学中以概率论为基 础的一门重要分支，亦称“随机服务系统理论” 础的一门重要分支，亦称“随机服务系统理论”。 典型的例子——食堂排队； 典型的例子——食堂排队； ——食堂排队 排队论是20世纪初开始发展的。1905年丹麦哥本哈根电话工程师爱尔朗首 排队论是20世纪初开始发展的。1905年丹麦哥本哈根电话工程师爱尔朗首 世纪初开始发展的 年丹麦哥本哈根电话工程师爱尔朗 先在电话自动交换机设计时应用排队论。 先在电话自动交换机设计时应用排队论。使电话机既能满足通话需求而又 不致设线过多。第二次世界大战以后，排队论在很多领域内被采用。 不致设线过多。第二次世界大战以后，排队论在很多领域内被采用。在交 通工程中，对于研究车辆延误、通行能力、信号灯配时以及停车场、 通工程中，对于研究车辆延误、通行能力、信号灯配时以及停车场、加油 站等交通设施的设计与管理方面得到广泛的应用。1936年 站等交通设施的设计与管理方面得到广泛的应用。1936年亚当斯 Adams.W.F）用以考虑未设置交通信号交叉口的行人延误问题，1951年 （Adams.W.F）用以考虑未设置交通信号交叉口的行人延误问题，1951年唐 予以推广应用，1954年伊迪（ 应用排队模型估计收费亭的延误。 纳予以推广应用，1954年伊迪（ Edie ）应用排队模型估计收费亭的延误。 同年在摩斯柯维茨的报告中，将其应用于车辆等候交通流空档的实验报告。 摩斯柯维茨的报告中 同年在摩斯柯维茨的报告中，将其应用于车辆等候交通流空档的实验报告。
k
4
10 3 . 0 . 0213 = 3 . 3 辆 q = 2 4 !× 4 5 1 − 6
5
10 n = q + ρ = 3.3 + = 6.6辆 3
3 .3 ω = = = 5s / 辆 2 λ 3 q
d =ω+
1
µ
= 5 + 5 = 10 s / 辆
排队的车辆
排队系统 中的车辆
排队的 排队系统
8辆车 10辆车 10辆车
2)排队系统的3个组成部分： 输入 排队 输出
(1)输入过程就是指各种类型的“顾客(车辆或行人)”按 怎样的规律到达。有各式各样的输入过程，例如： 定长输入：顾客等时距到达。 泊松输入：顾客到达时距符合负指数分布。这种输入过 程最容易处理，因而应用最广泛。 爱尔朗输入：顾客到达时距符合爱尔朗分布。
二、排队论的基本原理
1．基本概念 排队” 排队系统” 1) “排队”与“排队系统”的概念 排队 “排队”—单指等待服务的，不包括正在被服务的； 排队” 单指等待服务的，不包括正在被服务的； 单指等待服务的 既包括等待服务的， “排队系统”—既包括等待服务的，又包括正在被服务的车辆。 排队系统” 既包括等待服务的 又包括正在被服务的车辆。
两种系统比较
4个M/M/1 个 平均车辆数 平均排队长 平均耗时 平均等候时间 20 16.68 30 25 M/M/4 6.6 3.3 10 5
多通道服务方式
( 1 ) 系统中没有车辆的概率 P (0 ) = 1
为：
∑
N −1 k = 0
ρ
k
k!
+
ρ
N
N ! (1 − ρ / N )
( 2 ) 系统中有
k 个车辆的概率： k < N k >= N
ρ k . P ( 0 ), k! P （ k ）= ρ k P ( 0 ), N !N k−N
ρ
1− ρ
=
λ µ −λ
ρ (1 − ρ ) 2
7)系统中的平均消耗时间d =
λ
1
8)排队中的平均等待时间w = d −
µ
例2今有一停车场，到达率λ为60辆 / h，服从泊松分布。停车场的服务能力为
µ为100辆 / h，服从负指数分布。其单一的出入车道可存车6辆，问该数量
是否合适？ 解：这是一个M / M / 1排队系统问题
( 3 ) 系统中的平均车辆数： P (0 ) n = ρ + . N ! N (1 − ρ / N ) 2
ρ
N +1
（4）平均排队长度：
q = n − ρ
(5)系统中的平均消耗时间 ：
d = q
λ
+
1
µ
=
n
λ
( 6 )排队中的平均等待时间
：
ω =
q
λ
一加油站，今有2400 2400辆 的车流量通过4个通道引向4 例3. 一加油站，今有2400辆/h的车流量通过4个通道引向4个 加油泵，平均每辆车加油时间为5 服从负指数分布， 加油泵，平均每辆车加油时间为5s，服从负指数分布，试按多 路多通道系统（ M/M/1系统 单路多通道系统（M/M/4系统 系统） 路多通道系统（4个M/M/1系统 ）单路多通道系统（M/M/4系统） 计算各相应指标。 计算各相应指标。 M/M/1系统由题意可知 系统由题意可知： 解： 按4个M/M/1系统由题意可知： 2400 / 4 1 1 µ = 辆 /s = 辆/ s λ= 5 3600 6
3)排队系统的主要数量指标 3)排队系统的主要数量指标 最重要的数量指标有3 最重要的数量指标有3个： (1)等待时间即从顾客到达时起到他开始接受服务时止这段 (1)等待时间即从顾客到达时起到他开始接受服务时止这段 等待时间 时间。 时间。 (2)忙期即服务台连续繁忙的时期，这关系到服务台的工作 (2)忙期即服务台连续繁忙的时期， 忙期即服务台连续繁忙的时期 强度。 强度。 (3)队长（顾客数）有排队顾客数与排队系统中顾客之分， (3)队长（顾客数）有排队顾客数与排队系统中顾客之分， 队长 这是排队系统提供的服务水平的一种衡量。 这是排队系统提供的服务水平的一种衡量。
2)排队系统的3个组成部分： (2)排队(规则)指到达的顾客按怎样的次序接受服务。例如： 损失制：顾客到达时，若所有服务台均被占，该顾客就自动 消失，永不再来。 等待制：顾客到达时，若所有服务台均被占，他们就排成队 伍，等待服务，服务次序有先到先服务(这是最通常的情形) 和优先权服务(如急救车、消防车优先)等多种规则。 混合制：顾客到达时，若队伍长小于L，就排入队伍；若队伍 长等于L，顾客就离去，永不再来。
三、M/M/1系统—单通道服务系统 M/M/1系统— 系统
设顾客平均到达率为λ，则到达的平均时距为1 / λ。排队从单通道服务后通过接受 服务后通过的平均服务率为µ，则平均服务时间为1 / µ。比率ρ = λ / µ叫做服务强度 或交通强度，可以确定系统的状态。所谓状态，指的是排队系统的顾客数。 1)在系统中没有顾客的概率为P (0) = 1 − ρ 2)在系统中有n个顾客的概率为P (n) = ρ n (1 − ρ ) 3)系统中的平均车辆数n = 4)系统中的平均方差σ 2 = 5)平均排队长度q = n − ρ 6)非零平均排队长度q w = 1 1− ρ n
λ = 60辆 / h，µ = 100辆 / h ρ = λ / µ = 60 / 100 = 0.6 < 1，系统是稳定的。
因出入道存车量为6辆，如果超出6辆的概率很小时（一般认为小于5%），则 认为合适，否则认为不合适。 P(0) = (1 − ρ ) = 1 − 0.6 = 0.4，P(1) = ρ (1 − ρ ) = 0.6 × 0.4 = 0.24 P(2) = ρ 2 (1 − ρ ) = 0.6 2 × 0.4 = 0.14，P (3) = 0.63 × 0.4 = 0.09 P(4) = 0.6 4 × 0.4 = 0.05，P(5) = 0.65 × 0.4 = 0.03 P(6) = 0.66 × 0.4 = 0.02 P(> 6) = 1 − P (≤ 6) = 1 − ∑ P (n) = 1 − 0.97 = 0.03
为叙述方便，引用下列符号， 为叙述方便，引用下列符号，令 M代表泊松分布输入或负指数分布服务； 代表泊松分布输入或负指数分布服务； D代表定长分布输入或定长分布服务； 代表定长分布输入或定长分布服务； Ek代表爱尔朗分布的输入或服务。 代表爱尔朗分布的输入或服务。 于是泊松输入、负指数分布服务， 于是泊松输入、负指数分布服务，N个服务台的排队系统可以 写成M/M/N M/M/N； 写成M/M/N； 泊松输入、定长服务、单个服务台的系统可以写成M/D/1。 泊松输入、定长服务、单个服务台的系统可以写成M/D/1。 M/D/1 同样可以理解M/ /N，D/M/N…等符号的含义 等符号的含义。 同样可以理解M/ Ek /N，D/M/N 等符号的含义。 如果不附其它说明，则这种符号一般都指先到先服务， 如果不附其它说明，则这种符号一般都指先到先服务，单个 先到先服务 服务通道的等待制系统。 服务通道的等待制系统。
计算结果表明排队车辆数超过6辆的可能性极小，故可认为该出入道的 存车量是合理的。
四、M/M/N系统 系统
1.计算公式 在M / M / N排队系统中，服务通道有N条，所以也叫“多通道服务”系统。 设λ为进入多通道服务系统车辆的平均到达率，排队行列从每个服务台 接受服务后的平均输出率为µ，则每个服务台的平均服务时间是1 / µ。 仍记ρ = λ / µ，则ρ / N称为M / M / N系统的服务强度或交通强度，亦可称 为饱和度。和M / M / 1相仿，当ρ / N < 1时系统是稳定的，否则不稳定，排 队长度将趋向于无穷大。 M / M / N系统根据车辆排队方式的不同，可分为： 1 ）单路排队多通道服务：指排成一个队等待数条通道服务的情况，排队 中头一车辆可视哪条通道有空就到哪里去接受服务； 2）多路排队多通道服务：指每个通道各排一个队，每个通道只为其相应 的一队车辆服务，车辆不能随意换队。此种情况相当于N个M / M / 1系统 组成的系统，其计算公式亦相同。 对于单路排队多通道服务的M / M / N系统，计算公式如下：
第八章 交通流理论
排队论的应用 第三节 排队论的应用
一、引言
排队论是研究“服务”系统因“需求”拥挤而产生等待行列即排队的现象， 排队论是研究“服务”系统因“需求”拥挤而产生等待行列即排队的现象， 是研究 以及合理协调需求与服务关系的一种数学理论， 需求与服务关系的一种数学理论 以及合理协调需求与服务关系的一种数学理论，是运筹学中以概率论为基 础的一门重要分支，亦称“随机服务系统理论” 础的一门重要分支，亦称“随机服务系统理论”。 典型的例子——食堂排队； 典型的例子——食堂排队； ——食堂排队 排队论是20世纪初开始发展的。1905年丹麦哥本哈根电话工程师爱尔朗首 排队论是20世纪初开始发展的。1905年丹麦哥本哈根电话工程师爱尔朗首 世纪初开始发展的 年丹麦哥本哈根电话工程师爱尔朗 先在电话自动交换机设计时应用排队论。 先在电话自动交换机设计时应用排队论。使电话机既能满足通话需求而又 不致设线过多。第二次世界大战以后，排队论在很多领域内被采用。 不致设线过多。第二次世界大战以后，排队论在很多领域内被采用。在交 通工程中，对于研究车辆延误、通行能力、信号灯配时以及停车场、 通工程中，对于研究车辆延误、通行能力、信号灯配时以及停车场、加油 站等交通设施的设计与管理方面得到广泛的应用。1936年 站等交通设施的设计与管理方面得到广泛的应用。1936年亚当斯 Adams.W.F）用以考虑未设置交通信号交叉口的行人延误问题，1951年 （Adams.W.F）用以考虑未设置交通信号交叉口的行人延误问题，1951年唐 予以推广应用，1954年伊迪（ 应用排队模型估计收费亭的延误。 纳予以推广应用，1954年伊迪（ Edie ）应用排队模型估计收费亭的延误。 同年在摩斯柯维茨的报告中，将其应用于车辆等候交通流空档的实验报告。 摩斯柯维茨的报告中 同年在摩斯柯维茨的报告中，将其应用于车辆等候交通流空档的实验报告。
k
4
10 3 . 0 . 0213 = 3 . 3 辆 q = 2 4 !× 4 5 1 − 6
5
10 n = q + ρ = 3.3 + = 6.6辆 3
3 .3 ω = = = 5s / 辆 2 λ 3 q
d =ω+
1
µ
= 5 + 5 = 10 s / 辆
排队的车辆
排队系统 中的车辆
排队的 排队系统
8辆车 10辆车 10辆车
2)排队系统的3个组成部分： 输入 排队 输出
(1)输入过程就是指各种类型的“顾客(车辆或行人)”按 怎样的规律到达。有各式各样的输入过程，例如： 定长输入：顾客等时距到达。 泊松输入：顾客到达时距符合负指数分布。这种输入过 程最容易处理，因而应用最广泛。 爱尔朗输入：顾客到达时距符合爱尔朗分布。
二、排队论的基本原理
1．基本概念 排队” 排队系统” 1) “排队”与“排队系统”的概念 排队 “排队”—单指等待服务的，不包括正在被服务的； 排队” 单指等待服务的，不包括正在被服务的； 单指等待服务的 既包括等待服务的， “排队系统”—既包括等待服务的，又包括正在被服务的车辆。 排队系统” 既包括等待服务的 又包括正在被服务的车辆。
两种系统比较
4个M/M/1 个 平均车辆数 平均排队长 平均耗时 平均等候时间 20 16.68 30 25 M/M/4 6.6 3.3 10 5
多通道服务方式
( 1 ) 系统中没有车辆的概率 P (0 ) = 1
为：
∑
N −1 k = 0
ρ
k
k!
+
ρ
N
N ! (1 − ρ / N )
( 2 ) 系统中有
k 个车辆的概率： k < N k >= N
ρ k . P ( 0 ), k! P （ k ）= ρ k P ( 0 ), N !N k−N
ρ
1− ρ
=
λ µ −λ
ρ (1 − ρ ) 2
7)系统中的平均消耗时间d =
λ
1
8)排队中的平均等待时间w = d −
µ
例2今有一停车场，到达率λ为60辆 / h，服从泊松分布。停车场的服务能力为
µ为100辆 / h，服从负指数分布。其单一的出入车道可存车6辆，问该数量
是否合适？ 解：这是一个M / M / 1排队系统问题
( 3 ) 系统中的平均车辆数： P (0 ) n = ρ + . N ! N (1 − ρ / N ) 2
ρ
N +1
（4）平均排队长度：
q = n − ρ
(5)系统中的平均消耗时间 ：
d = q
λ
+
1
µ
=
n
λ
( 6 )排队中的平均等待时间
：
ω =
q
λ
一加油站，今有2400 2400辆 的车流量通过4个通道引向4 例3. 一加油站，今有2400辆/h的车流量通过4个通道引向4个 加油泵，平均每辆车加油时间为5 服从负指数分布， 加油泵，平均每辆车加油时间为5s，服从负指数分布，试按多 路多通道系统（ M/M/1系统 单路多通道系统（M/M/4系统 系统） 路多通道系统（4个M/M/1系统 ）单路多通道系统（M/M/4系统） 计算各相应指标。 计算各相应指标。 M/M/1系统由题意可知 系统由题意可知： 解： 按4个M/M/1系统由题意可知： 2400 / 4 1 1 µ = 辆 /s = 辆/ s λ= 5 3600 6
3)排队系统的主要数量指标 3)排队系统的主要数量指标 最重要的数量指标有3 最重要的数量指标有3个： (1)等待时间即从顾客到达时起到他开始接受服务时止这段 (1)等待时间即从顾客到达时起到他开始接受服务时止这段 等待时间 时间。 时间。 (2)忙期即服务台连续繁忙的时期，这关系到服务台的工作 (2)忙期即服务台连续繁忙的时期， 忙期即服务台连续繁忙的时期 强度。 强度。 (3)队长（顾客数）有排队顾客数与排队系统中顾客之分， (3)队长（顾客数）有排队顾客数与排队系统中顾客之分， 队长 这是排队系统提供的服务水平的一种衡量。 这是排队系统提供的服务水平的一种衡量。
2)排队系统的3个组成部分： (2)排队(规则)指到达的顾客按怎样的次序接受服务。例如： 损失制：顾客到达时，若所有服务台均被占，该顾客就自动 消失，永不再来。 等待制：顾客到达时，若所有服务台均被占，他们就排成队 伍，等待服务，服务次序有先到先服务(这是最通常的情形) 和优先权服务(如急救车、消防车优先)等多种规则。 混合制：顾客到达时，若队伍长小于L，就排入队伍；若队伍 长等于L，顾客就离去，永不再来。
三、M/M/1系统—单通道服务系统 M/M/1系统— 系统
设顾客平均到达率为λ，则到达的平均时距为1 / λ。排队从单通道服务后通过接受 服务后通过的平均服务率为µ，则平均服务时间为1 / µ。比率ρ = λ / µ叫做服务强度 或交通强度，可以确定系统的状态。所谓状态，指的是排队系统的顾客数。 1)在系统中没有顾客的概率为P (0) = 1 − ρ 2)在系统中有n个顾客的概率为P (n) = ρ n (1 − ρ ) 3)系统中的平均车辆数n = 4)系统中的平均方差σ 2 = 5)平均排队长度q = n − ρ 6)非零平均排队长度q w = 1 1− ρ n
λ = 60辆 / h，µ = 100辆 / h ρ = λ / µ = 60 / 100 = 0.6 < 1，系统是稳定的。
因出入道存车量为6辆，如果超出6辆的概率很小时（一般认为小于5%），则 认为合适，否则认为不合适。 P(0) = (1 − ρ ) = 1 − 0.6 = 0.4，P(1) = ρ (1 − ρ ) = 0.6 × 0.4 = 0.24 P(2) = ρ 2 (1 − ρ ) = 0.6 2 × 0.4 = 0.14，P (3) = 0.63 × 0.4 = 0.09 P(4) = 0.6 4 × 0.4 = 0.05，P(5) = 0.65 × 0.4 = 0.03 P(6) = 0.66 × 0.4 = 0.02 P(> 6) = 1 − P (≤ 6) = 1 − ∑ P (n) = 1 − 0.97 = 0.03
为叙述方便，引用下列符号， 为叙述方便，引用下列符号，令 M代表泊松分布输入或负指数分布服务； 代表泊松分布输入或负指数分布服务； D代表定长分布输入或定长分布服务； 代表定长分布输入或定长分布服务； Ek代表爱尔朗分布的输入或服务。 代表爱尔朗分布的输入或服务。 于是泊松输入、负指数分布服务， 于是泊松输入、负指数分布服务，N个服务台的排队系统可以 写成M/M/N M/M/N； 写成M/M/N； 泊松输入、定长服务、单个服务台的系统可以写成M/D/1。 泊松输入、定长服务、单个服务台的系统可以写成M/D/1。 M/D/1 同样可以理解M/ /N，D/M/N…等符号的含义 等符号的含义。 同样可以理解M/ Ek /N，D/M/N 等符号的含义。 如果不附其它说明，则这种符号一般都指先到先服务， 如果不附其它说明，则这种符号一般都指先到先服务，单个 先到先服务 服务通道的等待制系统。 服务通道的等待制系统。