交通系统分析第4章交通系统状态描述.ppt

《交通系统分析第4章交通系统状态描述.ppt》由会员分享，可在线阅读，更多相关《交通系统分析第4章交通系统状态描述.ppt（140页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第4章章 交通系统状态描述交通系统状态描述交通系统分析交通系统分析主要内容主要内容v排队理论排队理论v跟驰理论跟驰理论v连续流理论连续流理论v车队离散理论车队离散理论 排队论(Queuing Theory)，又称随机服务系统理论(Random Service System Theory),是一门研究拥挤现象(排队、等待)的科学。具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题。前前 言言o排队是我们在日常生活和生产中经常遇到的现象。例例如如，上、下班搭乘公共汽车；顾客到商店购买物品；病员到医院看病；旅客到售票处购买车票；学生去食堂就餐等就常常出现排

2、队和等待现象。o除了上述有形的排队之外，还有大量的所谓“无无形形”排队现象，如几个顾客打电话到出租汽车站要求派车，如果出租汽车站无足够车辆、则部分顾客只得在各自的要车处等待，他们分散在不同地方，却形成了一个无形队列在等待派车。o排队的不一定是人不一定是人，也可以是物也可以是物o例如，通讯卫星与地面若干待传递的信息；生产线上的原料、半成品等待加工；因故障停止运转的机器等待工人修理；码头的船只等待装卸货物；要降落的飞机因跑道不空而在空中盘旋等等。显然，上述各种问题虽互不相同，但却都有要求得到某种服务的人或物和提供服务的人或机构。排队论里把要要求求服服务务的的对对象象统称为“顾顾客客”,而把提提供供

3、服服务务的的机机构构或或人人称为“服服务务台台”或“服服务务员员”。不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统。o面对拥挤现象，人们总是希望尽量设法减少排队，通常的做法是增加服务设施。但是增加的数量越多，人力、物力的支出就越大，甚至会出现空闲浪费，如果服务设施太少，顾客排队等待的时间就会很长，这样对顾客会带来不良影响。o于是，顾顾客客排排队队时时间间的的长长短短与服服务务设设施施规规模模的的大大小小，就构成了设计随机服务系统中的一对矛盾。如何做到既保证一定的服务质量指标，又使服务设施费用经济

4、合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾，这就是随机服务系统理论排队论所要研究解决的问题。排队论是1909年由丹麦工程师爱爱尔尔朗朗(A.K.Erlang)在研究电话系统时创立的，几十年来排队论的应用领域越来越广泛，理论也日渐完善。特别是自二十世纪60年代以来，由于计算机的飞速发展，更为排队论的应用开拓了宽阔的前景。排队论研究的基本问题 排队论研究的首要问题是排队系统主要数量指标的概率规律，即研究系统的整体性质，然后进一步研究系统的优化问题。与这两个问题相关的还包括排队系统的统计推断问题。(1)通过研究主要数量指标在瞬时或平稳状态下的概率分布及其数字特征，了解系统运行的基本特征。

5、(2)统计推断问题，建立适当的排队模型是排队论研究的第一步，建立模型过程中经常会碰到如下问题：检验系统是否达到平稳状态；检验顾客相继到达时间间隔的相互独立性；确定服务时间的分布及有关参数等。(3)系统优化问题，又称为系统控制问题或系统运营问题，其基本目的是使系统处于最优或最合理的状态。系统优化问题包括最优设计问题和最优运营问题，其内容很多，有最少费用问题、服务率的控制问题、服务台的开关策略、顾客(或服务)根据优先权的最优排序等方面的问题。第一节第一节 排队论的基本知识排队论的基本知识o服务过程特征服务过程特征1）有要求服务的人或物）有要求服务的人或物。如：去食堂就餐的顾如：去食堂就餐的顾客，去

6、医院看病的病人，要求通过交叉口的汽车，客，去医院看病的病人，要求通过交叉口的汽车，请求着陆的飞机等。请求着陆的飞机等。2）有为顾客服务的人或物）有为顾客服务的人或物。如：食堂服务员，。如：食堂服务员，医院大夫，信号交叉口，飞机跑道等，在排队论医院大夫，信号交叉口，飞机跑道等，在排队论中，统称它们为中，统称它们为“服务员服务员”或或“服务台服务台”。由顾。由顾客和服务员组成一个服务系统。客和服务员组成一个服务系统。3）顾客到达服务系统的时刻是随机的）顾客到达服务系统的时刻是随机的。如：汽车到达交叉口，顾客到达商店等都如：汽车到达交叉口，顾客到达商店等都是随机的。每位顾客需要的服务时间也是是随机的

7、。每位顾客需要的服务时间也是随机的，有的服务时间长，有的服务时间随机的，有的服务时间长，有的服务时间短。因而整个服务系统的状态也是随机的。短。因而整个服务系统的状态也是随机的。服务系统的随机性造成某个阶段顾客排队服务系统的随机性造成某个阶段顾客排队长，而某些时候，服务员又空闲无事。长，而某些时候，服务员又空闲无事。一般的一般的排队过程排队过程为：顾客由顾客源出发，到达为：顾客由顾客源出发，到达服务机构（服务台、服务员）前，按排队规则排队服务机构（服务台、服务员）前，按排队规则排队等待接受服务，服务机构按服务规则给顾客服务，等待接受服务，服务机构按服务规则给顾客服务，顾客接受完服务后就离开。排队

8、过程的一般顾客接受完服务后就离开。排队过程的一般过程过程可可用下图表示。我们所说的用下图表示。我们所说的服务系统就是指图中实框服务系统就是指图中实框所包括的部分所包括的部分。对上面所说的对上面所说的“顾客顾客”和和“服务员服务员”要作广泛的理解。要作广泛的理解。它们可以是人，也可以是某种物质或设备。排队可以它们可以是人，也可以是某种物质或设备。排队可以是有形的，也可以是无形的。是有形的，也可以是无形的。排队过程的一般表示排队过程的一般表示o损失制系统损失制系统 当顾客到达这种服务系统时，若服务员都忙着，则顾客立即离去，另求服务。例如，打电话遇到占线，用户搁置而去；汽车停车场放满时，就立即离去，

9、另找停车场。o等待制系统等待制系统 顾客到达该服务系统时，服务员都在为先到的顾客服务，后到的顾客只好参加排队，等候服务，一直等到有空的服务员来为它服务为止。例如，汽车在通过信号交叉口时，如果遇到红灯，汽车只好在停车线后排队等候，等到绿灯时通过。服务系统分类服务系统分类o混合制系统混合制系统 介于前两个系统之间，当顾客到达时，若服务员都不空，他就排队，但如果顾客到达时服务员都不空，且排队位置已满，顾客就立即离去，这是排队长度有限制的服务系统。例如，去理发店理发，当等待理发的位置都满时，后来的顾客只得离去。在混合制中，还有另外一种形式：当顾客到达时，服务员不空，他就排队，等待服务，当顾客等了一段时

10、间后，仍轮不到为他服务，顾客就离开队列，另求服务，这称为排队时间有限制的服务系统。例如，药品、电子元件等过期失效均属此类系统。服务系统分类服务系统分类服务系统组成服务系统组成 尽管排队系统是多种多样的，但从决定排队系统尽管排队系统是多种多样的，但从决定排队系统进程的因素来看，它有三个基本的组成部分，这就是进程的因素来看，它有三个基本的组成部分，这就是输入过程、排队规则及服务机构。输入过程、排队规则及服务机构。1)1)输入过程：输入过程：描述顾客来源以及顾客到达排队系统的规律。包描述顾客来源以及顾客到达排队系统的规律。包括：括：顾客相继到达的时间间隔是顾客相继到达的时间间隔是确定型的确定型的还还

11、是随机型的是随机型的；如：列车是按列车时刻表进站，到站时刻是确定型的；城市如：列车是按列车时刻表进站，到站时刻是确定型的；城市信号交叉口，汽车到达交叉口的时刻是随机的。信号交叉口，汽车到达交叉口的时刻是随机的。顾客顾客的总体（即顾客源）的组成是无限的还是有限的。的总体（即顾客源）的组成是无限的还是有限的。如，在道路交叉口，到达车辆的总体可以看成是无限的，而如，在道路交叉口，到达车辆的总体可以看成是无限的，而工厂内停机待修的机器显然是有限的。工厂内停机待修的机器显然是有限的。2 2）排队规则）排队规则:（在损失制系统中，没有顾客排队，（在损失制系统中，没有顾客排队，所以不存在排队问题，这里的排队

12、规则是相对于等所以不存在排队问题，这里的排队规则是相对于等待制和混合制系统而言的）待制和混合制系统而言的）o先到先服务先到先服务（FCFSFCFS）：即按顾客到达的先后次序给：即按顾客到达的先后次序给予服务，这是最普遍的情况。予服务，这是最普遍的情况。o后到先服务后到先服务（LCFSLCFS）：如在情报系统中，最后到达：如在情报系统中，最后到达的情报往往是最有价值的，应优先采用；如堆在仓的情报往往是最有价值的，应优先采用；如堆在仓库中的钢板，使用时先用堆在上面的（即后堆上去库中的钢板，使用时先用堆在上面的（即后堆上去的）钢板。的）钢板。o随机服务随机服务（RSSRSS）：当一个顾客被服务完了之

13、后，：当一个顾客被服务完了之后，服务员从排队的顾客中任取一个，给予服务。服务员从排队的顾客中任取一个，给予服务。如电话交换台接通呼叫电话就是一例。如电话交换台接通呼叫电话就是一例。o有优先权的服务有优先权的服务（PRPR）：分轻重缓急给予服务。：分轻重缓急给予服务。如加急电报要先于普通电报拍发；重病号应先如加急电报要先于普通电报拍发；重病号应先于轻病号医疗等。于轻病号医疗等。3 3）服务机构）服务机构：包括为每个顾客服务所需时间的概率分布，服务台包括为每个顾客服务所需时间的概率分布，服务台的数目以及服务台的排列方式（串联、并联等）。顾客的数目以及服务台的排列方式（串联、并联等）。顾客的服务时间

14、一般具有两种形式：一种是每个顾客的服务的服务时间一般具有两种形式：一种是每个顾客的服务时间是一个确定量，一种是每个顾客的服务时间是一个时间是一个确定量，一种是每个顾客的服务时间是一个随机变量，它服从某一概率分布。对于服务台的排列方随机变量，它服从某一概率分布。对于服务台的排列方式，分单通道与多通道两种。式，分单通道与多通道两种。o单通道服务系统单通道服务系统单通道单服务台系单通道单服务台系统统单通道多服务台串联系统单通道多服务台串联系统 (如装配流水线如装配流水线)o多通道服务系统多通道服务系统可通的多通道系统可通的多通道系统不可通的多通道系统不可通的多通道系统多通道混合系统多通道混合系统 排

15、队模型的表示方法排队模型的表示方法 在在1953年提出了一个分类方法，按照系统的三个最主年提出了一个分类方法，按照系统的三个最主要的、影响最大的三个特征要素进行分类，它们是：顾客要的、影响最大的三个特征要素进行分类，它们是：顾客相继到达的间隔时间分布、服务时间的分布、并列的服务相继到达的间隔时间分布、服务时间的分布、并列的服务台个数。按照这三个特征要素分类的排队系统，用符号台个数。按照这三个特征要素分类的排队系统，用符号（称为（称为KendallKendall记号）表示为记号）表示为 X/Y/Z其中其中X X处填写顾客相继到达的间隔时间分布，处填写顾客相继到达的间隔时间分布，Y Y处填写服务处

16、填写服务时间的分布，时间的分布，Z Z处填写并列的服务台个数。处填写并列的服务台个数。例如例如M/M/1，表示顾客相继到达的间隔时间为负指数表示顾客相继到达的间隔时间为负指数分布、服务时间为负指数分布、单服务台的模型。分布、服务时间为负指数分布、单服务台的模型。后来，在后来，在19711971年关于排队论符号标准化的会议上决年关于排队论符号标准化的会议上决定，将定，将KendallKendall符号扩充为：符号扩充为：X/Y/Z/A/B/C 其中前三项意义不变其中前三项意义不变。A A处填写系统容量限制处填写系统容量限制;B B处填写顾客源中的顾客数目处填写顾客源中的顾客数目;C C处填写服务

17、规则（如先到先服务处填写服务规则（如先到先服务FCFSFCFS，后到先服务后到先服务LCFSLCFS）。）。表示相继到达间隔时间和服务时间的各种分布的符号为：表示相继到达间隔时间和服务时间的各种分布的符号为：M-负指数分布；负指数分布；D-确定型分布；确定型分布；Ek-k阶爱尔朗分阶爱尔朗分布；布；GI-一般独立随机分布；一般独立随机分布；G-一般随机分布。一般随机分布。服务系统的运行指标服务系统的运行指标 对于一个排队系统，运行状况的好坏既涉及到顾客对于一个排队系统，运行状况的好坏既涉及到顾客的利益，又涉及到服务机构的利益，还有社会效果好坏的利益，又涉及到服务机构的利益，还有社会效果好坏的问

18、题。为了研究排队系统运行的效率、估计服务质量、的问题。为了研究排队系统运行的效率、估计服务质量、研究设计改进措施，必须确定一些基本指标，用以判断研究设计改进措施，必须确定一些基本指标，用以判断系统运行状况的优劣。下面介绍几种常用的指标。系统运行状况的优劣。下面介绍几种常用的指标。1)1)队长：把系统中的顾客数称为队长：把系统中的顾客数称为队长队长，它的期望值记，它的期望值记作作Ls。而把系统中排队等待服务的顾客数称为而把系统中排队等待服务的顾客数称为排队长排队长（队列长）（队列长），它的期望值记作，它的期望值记作LqLq。显然显然有有 队长排队长正被服务的顾客数。队长排队长正被服务的顾客数。2

19、)2)逗留时间：逗留时间：一个一个顾客从到达排队系统到服务完毕离顾客从到达排队系统到服务完毕离去的总停留时间称为去的总停留时间称为逗留时间逗留时间，它的期望值记作，它的期望值记作Ws。一个一个顾客在系统中排队等待的时间称为顾客在系统中排队等待的时间称为等待时间等待时间（或（或排队时间）排队时间），它的期望值记作它的期望值记作Wq。显然显然有有 逗留时间等待时间服务时间。逗留时间等待时间服务时间。3 3）忙期：指从顾客到达空闲服务机构起到服务机构再）忙期：指从顾客到达空闲服务机构起到服务机构再次空闲止的时间长度，即服务机构连续繁忙的时间长度。次空闲止的时间长度，即服务机构连续繁忙的时间长度。研究

20、目的：通过对排队系统中概率规律的研究，使系统研究目的：通过对排队系统中概率规律的研究，使系统达到最优设计和最优控制，以最小费用实现系统的最大达到最优设计和最优控制，以最小费用实现系统的最大效益。效益。第二节第二节 顾客顾客到达分布和服务时间分布到达分布和服务时间分布泊松分布泊松分布负指数分布负指数分布 泊松(poisson)输入，又称最简单流。满足下面3个条件的输入称之为最简单流。(1)平稳性。又称作输入过程是平稳的，指在长度为t的时段内恰好到达k个顾客的概率仅与时段长度有关，而与时段起点无关。即对任意(0,)，在(,+t或(0,t)内恰好到达k个顾客的概率相等。(2)无后效性。指在任意几个不

21、相交的时间区间内，各自到达的顾客数是相互独立的。通俗地说就是以前到达的顾客情况，对以后顾客的到来没有影响。否则就是关联的。(3)单个性又称普通性。指在充分小的时段内最多到达一个顾客。在一个充分小的时间间隔里不可能有两个或两个以上的顾客到达，只能有一个顾客到达。换句话说，有两个或两个以上的顾客到达的概率与有一个顾客到达的概率相比小到可以忽略的程度。因为泊松流实际应用最广，也最容易处理，因而研究得也较多可以证明，对于泊松流，在长度为t的时间内到达K个顾客的概率vk(t)服从泊松分布，即o如果顾客的到达过程（在确定的时间区间内到如果顾客的到达过程（在确定的时间区间内到达的顾客数）服从最简单流，则顾客

22、的到达时达的顾客数）服从最简单流，则顾客的到达时间间隔服从参数为间间隔服从参数为 的负指数分布的负指数分布。o如果顾客的服务过程（即离开服务台的过程）如果顾客的服务过程（即离开服务台的过程）服从最简单流，则顾客的服务时间服从参数服从最简单流，则顾客的服务时间服从参数 的负指数分布。的负指数分布。o从本质上看，泊松分布与负指数分布是同一个从本质上看，泊松分布与负指数分布是同一个过程的不同表现形式。过程的不同表现形式。第三节第三节 生灭过程生灭过程o研究系统内部状态变化的过程研究系统内部状态变化的过程系统状态系统状态i i状态状态i+1i+1状态状态i-1i-1在在t t时刻内发生两个或两个以上时

23、刻内发生两个或两个以上事件的概率为事件的概率为O(O(t)t)一个事件一个事件一个事件一个事件一、生灭过程定义一、生灭过程定义t0t0，O(O(t)0t)0 系统具有系统具有0,1,2,0,1,2,个状态。在任何时刻，若系统个状态。在任何时刻，若系统处于状态处于状态i i，并且系统状态随时间变化的过程满足，并且系统状态随时间变化的过程满足以下条件，称为一个生灭过程：以下条件，称为一个生灭过程：1 1、在（、在（t,t+t,t+t t）内系统由状态）内系统由状态i i转移到状态转移到状态i+1i+1的的概率为概率为i it+O(t+O(t)t)平稳性条件平稳性条件t t内有一个顾客到达的概率内有

24、一个顾客到达的概率2 2、在（、在（t,t+t,t+t t）内系统由状态）内系统由状态i i转移到状态转移到状态i-1i-1的的概率为概率为i it+O(t+O(t)t)平稳性条件平稳性条件t t内有一个顾客离开的概率内有一个顾客离开的概率3 3、在（、在（t,t+t,t+t t）内系统发生两次以上转移的概率）内系统发生两次以上转移的概率为为O(O(t)t)，即有，即有2 2个以上顾客到达或离开的概率为个以上顾客到达或离开的概率为 普遍性条件普遍性条件只要排队系统的输入过程和服务过程符合泊松分布，只要排队系统的输入过程和服务过程符合泊松分布，排队过程符合生灭过程排队过程符合生灭过程二、生灭过程

25、状态转移图二、生灭过程状态转移图S0S1S2Si-1SiSi+1Sk-1Sk123i-1ii+1i+2k-1k012i-2i-1ii+1k-2k-1状态状态顾客到达率顾客到达率系统服务率系统服务率tt时，时，P Pi i(t)(t)趋向于常数：系统达到稳定趋向于常数：系统达到稳定o系统达到稳定后：每个状态转入率的期系统达到稳定后：每个状态转入率的期望值与转出率的期望值相等。望值与转出率的期望值相等。对于状态对于状态i i：转出率的期望值为：转出率的期望值为转入率的期望值为转入率的期望值为S0S1S2Si-1SiSi+1Sk-1Sk123i-1ii+1i+2k-1k012i-2i-1ii+1k-

26、2k-1P P0 0P P1 1P P2 2P Pi i有有对于对于S S0 0转入转入转出转出转出转出转入转入对于对于S Sk kS0S1S2Si-1SiSi+1Sk-1Sk123i-1ii+1i+2k-1k012i-2i-1ii+1k-2k-1P P0 0P P1 1P P2 2P Pi i状态转移方程状态转移方程求解该方程，可以获得各状态对应的概率求解该方程，可以获得各状态对应的概率对于对于S S0 0对于对于S S1 1依次类推依次类推且有且有例：例：某排队系统：某排队系统：M/M/1/3/FCFSM/M/1/3/FCFS，=2=2，=3=3。求解各状态对应的概率。求解各状态对应的概率

27、。首先，做出相应的状态转移图首先，做出相应的状态转移图S0S1S2S3222333对于对于S S0 0对于对于S S1 1对于对于S S2 2生灭过程求解排队系统各状态概率过程生灭过程求解排队系统各状态概率过程建立状态转移图建立状态转移图建立状态转移方程建立状态转移方程求解状态转移方程求解状态转移方程各状态转入率期望值各状态转入率期望值与转出率期望值相等与转出率期望值相等各状态概率各状态概率第三节第三节 M/M/1M/M/1排队系统排队系统顾客到达服从泊松分布顾客到达服从泊松分布顾客到达率为顾客到达率为服务过程服从泊松分布（负指数分布）服务过程服从泊松分布（负指数分布）系统服务率为系统服务率为

28、单通道，先到先服务单通道，先到先服务最简单的最简单的M/M/1M/M/1排队系统：排队系统：M/M/1/M/M/1/M/M/1/m/M/M/1/m/M/M/1/M/M/1/排队系统排队系统系统容量无限、顾客源无限系统容量无限、顾客源无限最基本的排队系统最基本的排队系统排队过程为生灭过程排队过程为生灭过程S0S1S2Si-1SiSi+1P P0 0P P1 1P P2 2P Pi i列状态转移方程组求各状态概率列状态转移方程组求各状态概率M/M/1/M/M/1/排队系统各状态概率排队系统各状态概率归结为无穷等比数列求和归结为无穷等比数列求和11 1，数列发散，数列发散系统稳定系统稳定系统不稳定系

29、统不稳定称称为服务强度，若服务强度大于为服务强度，若服务强度大于1 1，说明单位时间内到达的顾客，说明单位时间内到达的顾客数比完成服务的顾客数多，系统中排队长度越来越大，产生阻塞。数比完成服务的顾客数多，系统中排队长度越来越大，产生阻塞。利用排队系统各状态概率计算运行指标利用排队系统各状态概率计算运行指标o1、队长、队长系统中的顾客数量系统中的顾客数量队长队长o2、排队长、排队长系统中等待的顾客数量系统中等待的顾客数量通道数通道数v3、逗留时间、逗留时间顾客在排队系统中的总时间顾客在排队系统中的总时间李太勒公式李太勒公式前后前后2 2名顾客到达系统的时间间隔名顾客到达系统的时间间隔4、排队时间

30、、排队时间顾客在排队系统中的等待时顾客在排队系统中的等待时间间李太勒公式李太勒公式前后前后2 2名顾客到达系统的时间间隔名顾客到达系统的时间间隔M/M/1/m/M/M/1/m/排队系统排队系统系统容量有限、顾客源无限系统容量有限、顾客源无限P P0 0P P1 1P P2 2S2S0S1SiSmP Pi iP Pm m列状态转移方程组求各状态概率列状态转移方程组求各状态概率并不要求并不要求11。特别地，当特别地，当=1=1时，时，P P0 0=1/(m+1)=1/(m+1)(1)1)利用排队系统各状态概率计算运行指标利用排队系统各状态概率计算运行指标o1、队长、队长系统中的顾客数量系统中的顾客

31、数量队长队长o2、排队长、排队长系统中等待的顾客数量系统中等待的顾客数量通道数通道数v3、逗留时间、逗留时间顾客在排队系统中的总时间顾客在排队系统中的总时间李太勒公式李太勒公式前后前后2 2名顾客到达系统的时间间隔名顾客到达系统的时间间隔有效到达率有效到达率e e当排队长度未满容量时，平均到达率为当排队长度未满容量时，平均到达率为当排队容量已满容量时，平均到达率为当排队容量已满容量时，平均到达率为0 0逗留时间逗留时间4、排队时间、排队时间顾客在排队系统中的等待时顾客在排队系统中的等待时间间李太勒公式李太勒公式前后前后2 2名顾客到达系统的时间间隔名顾客到达系统的时间间隔o顾客的到达是服从参数

32、的泊松分布；o顾客的服务时间是服从参数为的负指数分布；o有S个服务台，顾客按到达的先后次序接受服务。第四节第四节 M/M/S排队系统排队系统o当顾客到达时，若有空闲的服务台就立即接受服务，若所有的服务台都忙着，则顾客排成一个队列等待服务。常见的M/M/S/及M/M/S/m/两类 M/M/S/排队系统标准M/M/S系统 o系统中个服务台的服务率均为，于是整个服务机构的最大服务率为S。与M/M/1/系统类似，只有当 时，才能使服务系统达到稳态而不排成无限的队列。系统的服务强度 当系统中只有一个顾客时，则有S-1个服务台空闲着，仅一个服务台在服务，这时的服务率为，当系统有2个顾客时，就有2个服务台工

33、作，其服务率为2 ，当系统中有S个顾客时，则服务率达到最大值S ，当系统中的顾客数超过S时，由于个服务台都忙着，其余顾客必须排队，这时的服务率仍为S M/M/1系统M/M/S系统M/M/S系统根据正则条件利用排队系统各状态概率计算运行指标利用排队系统各状态概率计算运行指标o1、排队长、排队长o2、平均等候时间平均等候时间 v3、逗留时间、逗留时间v、平均顾客数、平均顾客数 系统容量受限制、顾客源无限、先到先服务的M/M/S系统。该系统共有m-S个位置可供顾客排队。当顾客到达时，若系统饱和，即服务台都忙着，排队位置已排满，则后到的顾客立即离去，另求服务。因此，该系统中只可能有m+1个状态。M/M

34、/S/m/排队系统 与M/M/S/系统的推导类似，可得M/M/S/m/系统的状态指标及运行指标。第五节 排队服务系统的最优化问题 o排队系统设计最优化的目标在于使系统设施达到最大使用效益，或者说，在一定的质量指标下要求服务机构最为经济o一般要求系统最优o对于顾客来说，总是要求提高服务水平（如增设服务台数、加快服务时间）以减少排队费用，若要完全满足顾客的要求，则会导致服务机构过大，使用效率降低，造成浪费。o从服务机构来说，总是希望服务机构能达到最高的使用效率，每个服务台都不出现空闲状态，这必然导致顾客等候费用的增加，影响顾客的利益。o排队系统最优化的目的是综合考虑两者的利益，使二者费用之和为最小

35、，确定达到这个目标的最优服务水平。o另一常用的目标函数是使系统的纯收入（服务收入与服务成本之差）为最大 o排队服务系统的最优化问题通常归结为求极值问题求导（求偏导）迭代法 试算法 常用的求极值方法有：例例3 某收费公路处设有一收费亭，汽车进入公路某收费公路处设有一收费亭，汽车进入公路必须向收费亭收费。收费亭的收费时间服从负指数分必须向收费亭收费。收费亭的收费时间服从负指数分布，平均每辆汽车的交费时间为布，平均每辆汽车的交费时间为7.2s，汽车的到达，汽车的到达率为率为400辆辆/h，并服从泊松分布，试求，并服从泊松分布，试求：收费亭收费亭空闲的概率空闲的概率：收费亭前没有车辆排队收费亭前没有车

36、辆排队的概率的概率；收费亭前排队长队超过收费亭前排队长队超过100m100m（即排队车辆（即排队车辆超过超过1212辆）的概率辆）的概率；平均排队长度；平均排队长度；车辆通过收费亭所花费时间的平均值车辆通过收费亭所花费时间的平均值；车辆的平均排队车辆的平均排队时间时间 。解解解解：收费亭收费亭空闲的概率空闲的概率：也就是系统中没有车辆：也就是系统中没有车辆到达的概率。到达的概率。没有没有车辆排排队的概率的概率当系统中没有车辆或只有一辆车（这辆车正在被服当系统中没有车辆或只有一辆车（这辆车正在被服务）时，便没有车辆排队。务）时，便没有车辆排队。排排队车辆超超过12辆的概率的概率 也就是系也就是系

37、统中中车辆超超过13辆的概率的概率；平均排平均排队长队长度；度；车辆通通过收收费亭所花的平均亭所花的平均时间时间；车辆的平均排的平均排队时间时间 例例4 某某市区有一加油站市区有一加油站为为汽汽车车加油。加油。站上站上服务台服务台平均平均36s时间时间处理一辆处理一辆汽汽车，加车，加油油 时间服从负指数时间服从负指数分分布布，汽，汽车到车到加加油油站站加油加油的到达的到达率率为为80辆辆/h，并，并服服从从泊泊松分布松分布。当。当要要等候加油的等候加油的汽车超过汽车超过10辆辆(即排队即排队长度超过长度超过80m，不，不包括正包括正在加油的汽车）时，在加油的汽车）时，将影将影响加油站附近响加油

38、站附近街道街道的的正常正常交通，因而规定排队汽车交通，因而规定排队汽车不不得超过得超过10辆，试求：辆，试求：加油站加油站空闲的概率空闲的概率：汽车来加油汽车来加油但但因排队因排队已已满而被拒绝的概率满而被拒绝的概率；在在系统系统中中的的平平均顾客数；均顾客数；平均排队长度；平均排队长度；汽汽车在整个车在整个加加油过程中所花油过程中所花的时间；的时间；汽车排队等候时间汽车排队等候时间 。解解解解：加油站加油站空闲的概率空闲的概率：也就是系统中没有车辆：也就是系统中没有车辆到达的概率。到达的概率。汽汽车车来加油来加油但但因排因排队队已已满满而被拒而被拒绝绝的概率的概率汽车被拒绝的概率，就是系统饱

39、和时的状态概率：汽车被拒绝的概率，就是系统饱和时的状态概率：在在系系统统中中的的平平均均顾顾客数；客数；平均排平均排队长队长度；度；汽汽车在整个在整个加加油油过程中所花程中所花的的时间时间；汽汽车车排排队队等候等候时间时间 例例5 某汽车修理服务站，前来修理的车辆是随机到达某汽车修理服务站，前来修理的车辆是随机到达的，到达率为的，到达率为4辆辆/h，每辆汽车在站上修理的持续时间，每辆汽车在站上修理的持续时间平均为平均为0.5h，并服从负指数分布。该站有，并服从负指数分布。该站有5个修理服务个修理服务台可供修理，试求该服务站的运行指标。台可供修理，试求该服务站的运行指标。解：解：无来车修理无来车

40、修理的概率的概率：也就是所有服务台均空：也就是所有服务台均空闲的概率。闲的概率。修理站前不出修理站前不出现汽汽车排排队的概率的概率当在修理站修理的汽车不超过当在修理站修理的汽车不超过5辆时，就不会出现辆时，就不会出现排队现象。排队现象。不出现排队现象的概率为：不出现排队现象的概率为：修理站前修理站前平均排平均排队长队长度；度；整个系整个系统的的车辆平均数平均数；汽汽车车排排队队等候等候修理所花修理所花费时间时间 出出现排排队的概率的概率；汽汽车车在整个修理在整个修理过程中所花程中所花费时间时间 例例6 某主要道路与次要道路相交的无控交叉口，两条道路上的某主要道路与次要道路相交的无控交叉口，两条

41、道路上的车流到达过程符合泊松分布。把车辆通过交叉口看成是车辆接车流到达过程符合泊松分布。把车辆通过交叉口看成是车辆接受了服务，那么次要道路上排队车流中第一辆车为正在接受服受了服务，那么次要道路上排队车流中第一辆车为正在接受服务的顾客，第一辆车从到达停车线到通过交叉口的时间就是服务的顾客，第一辆车从到达停车线到通过交叉口的时间就是服务时间，它与主路车流的车头时距分布有关，当主路车流符合务时间，它与主路车流的车头时距分布有关，当主路车流符合泊松流时，次路车辆的服务时间总是服从负指数分布。在次路泊松流时，次路车辆的服务时间总是服从负指数分布。在次路车流中，从第二辆起的汽车即为排队等候服务的顾客。因此

42、，车流中，从第二辆起的汽车即为排队等候服务的顾客。因此，该交叉口系统就是一个标准的该交叉口系统就是一个标准的M/M/1系统。设次路车流的交通系统。设次路车流的交通量为量为350辆辆/h，次路车辆从到达停车线到通过交叉口的平均服，次路车辆从到达停车线到通过交叉口的平均服务时间为务时间为10s。试求系统的运行指标。试求系统的运行指标。解：解：交叉口没有车辆交叉口没有车辆的概率的概率。交叉口前排交叉口前排队车辆(包括正等待通包括正等待通过的第一的第一辆车)超超过50辆的概率的概率。交叉口前的平均排交叉口前的平均排队车辆数数(包括第一包括第一辆)；车辆从到达停从到达停车线到通到通过交叉口所需平均交叉口

43、所需平均时间；从从这些指些指标可以看出，交叉口前可以看出，交叉口前约有有97的的时间出出现排排队，平均排，平均排队长度达度达35辆，约有有24的的时间排排队长度超度超过50辆，车辆在交叉口前平均在交叉口前平均需要排需要排队6min，阻塞相当，阻塞相当严重，重，应予以改善。予以改善。如拓如拓宽进口，口，设置两条平行的置两条平行的进口道，或口道，或设置交置交通信号灯。通信号灯。例例7 某收费公路入口处，设有某收费公路入口处，设有3个收费亭，收费亭前的个收费亭，收费亭前的排队引道可考虑两种方案。方案排队引道可考虑两种方案。方案1为车辆到达后排成一为车辆到达后排成一队，依次向任一空闲的收费亭缴费进入公

44、路，方案队，依次向任一空闲的收费亭缴费进入公路，方案2为为车辆到达后在车辆到达后在3个收费亭前排成三队，中间设有分隔带。个收费亭前排成三队，中间设有分隔带。设设3个收费亭服务率相同，平均个收费亭服务率相同，平均10s处理一辆车，车的处理一辆车，车的到达率为到达率为900辆辆/h。比较两种排队系统的运行指标。比较两种排队系统的运行指标。解：解：收费亭空闲收费亭空闲的概率的概率。车辆必必须排排队的概率的概率。排排队的平均的平均车辆数数整个系整个系统的平均的平均车辆数数；汽汽车的平均排的平均排队时间；汽汽车车通通过收收费亭所用亭所用时间每个子系统中每个子系统中收费亭空闲收费亭空闲的概率的概率。车辆必

45、必须排排队的概率的概率。排排队的平均的平均车辆数数整个系整个系统的平均的平均车辆数数；汽汽车的平均排的平均排队时间；汽汽车车通通过收收费亭所用亭所用时间两种方案的指标比较两种方案的指标比较例例8 一加油站，今有一加油站，今有2400辆辆/h的车流量通过的车流量通过4个通道引个通道引向向4个加油泵，平均每辆车加油时间为个加油泵，平均每辆车加油时间为5s，服从负指数服从负指数分布，试按多路多通道系统（分布，试按多路多通道系统（4个个M/M/1系统系统）单路）单路多通道系统（多通道系统（M/M/4系统）计算各相应指标。系统）计算各相应指标。解：解：按按4个个M/M/1系统由题意可知：系统由题意可知：

46、按单路多通道系统按单路多通道系统M/M/4计算：计算：4个个M/M/1M/M/4平均车辆数平均车辆数206.6平均排队长平均排队长16.683.3平均耗时平均耗时3010平均等候时间平均等候时间255两种系统比较两种系统比较主要内容主要内容v排队理论排队理论v跟驰理论跟驰理论v连续流理论连续流理论v车队离散理论车队离散理论n跟驰理论是运用动力学方法，研究在无法超车的单一车道上车辆列队行驶时，后车跟随前车的行驶状态，并且借数学模式表达并加以分析阐明的一种理论。n由于有1950年鲁契尔的研究和1953年派普斯的研究，跟驰理论的解析方法才告定型。而赫尔曼和罗瑟瑞于1960年在美国通用汽车公司动力实验

47、室进行的研究为跟驰理论作了进一步的扩充。车辆跟驰特性分析车辆跟驰特性分析在道路上行驶的一队高密度汽车，车间距在道路上行驶的一队高密度汽车，车间距离不大，车队中任一辆车的车速都受前车速度离不大，车队中任一辆车的车速都受前车速度的制约，驾驶员只能按前车所提供的信息采用的制约，驾驶员只能按前车所提供的信息采用相应的车速。这种状态亦称为非自由行驶状态。相应的车速。这种状态亦称为非自由行驶状态。跟驰理论跟驰理论只研究只研究非自由行驶状态非自由行驶状态下车队的特性。下车队的特性。非自由行驶状态的车队有以下三个特性：非自由行驶状态的车队有以下三个特性：1 1制约性制约性2 2传递性传递性3 3延迟性延迟性1

48、、制约性 在后车有“紧随要求”的前提下，前车车速制约着后车车速和两车间距，后车运动状态随前车运动状态的改变而改变。“紧随要求”、“车速条件”、“间距要求”构成了跟驶行驶的制约性。2、传递性 车流中某一车辆运行状态的改变，会一辆接一辆的向后连续影响，即这种影响具有传递性。3、延迟性（滞后性）前、后车运行状态的改变不是同步的，后车总是在前车运行状态改变后，过一段时间（反应时间）才能作出相应的动作。线性跟驰模型线性跟驰模型跟驰模型是一种刺激反应的表达式。一个驾驶员所接受的刺激是指其前方导引车的加速或减速以及随之而发生的这两车之间的速度差和车间距离的变化；该驾驶员对刺激的反应是指其为了紧密而安全地跟踪

49、前车所作的加速或减速动作及其实际效果。假定驾驶员保持他所驾驶车辆与前导车的距离为s(t)，以便在前导车刹车时能使车停下而不致于和前导车尾相撞。设驾驶员的反应时间为T，在反应时间T内，车速不变，设n为前导车，nl为后随车。这两辆车在t时刻的相对位置以及两车在刹车操作后的相对位置如图所示。线性跟车模型示意图线性跟驰模型线性跟驰模型上式是在前导车刹车、两车的减速距离相等以及后车在反应时间T内速度不变等假定下推导出来的。实际的跟车操作要比这两条假定所限定的情形复杂得多。比方说，刺激也可能是由前车加速而引起的。而两车的变速过程中行驶的距离可能不相等。为了适应更一般的情形，把上式修改为：式中 称为反应强度

50、系数，量纲为 ，这里 不再理解为敏感度，而应看成是与驾驶员动作的强弱程度直接相关。上式表明后车的反应与前车发出的刺激成正比，此公式称为线性跟车模型。线性跟驰模型的稳定性线性跟驰模型的稳定性交通稳定性有两方面含义:一方面是指前后两车的速度大致相等，车间距离大体保持某一常数值，这称为局部稳定性。局部稳定性关注的是跟驰车辆对它前面车辆运行波动的反应，即关注车辆间配合的局部行为。另一方面是指在车队中某车的速度变化向其后各车传播的特性，如果速度变化的振幅在传播过程中扩大了，叫做不稳定，如果振幅逐渐衰弱，则称为渐进稳定。渐进稳定性关注车队中每一辆车的波动特性在车队中的表现，即车队的整体波动特性。对于稳定性