交通系统分析第4章交通系统状态描述.ppt
《交通系统分析第4章交通系统状态描述.ppt》由会员分享,可在线阅读,更多相关《交通系统分析第4章交通系统状态描述.ppt(140页珍藏版)》请在三一办公上搜索。
1、第4章 交通系统状态描述,交通系统分析,主要内容,排队理论跟驰理论连续流理论车队离散理论,排队论(Queuing Theory),又称随机服务系统理论(Random Service System Theory),是一门研究拥挤现象(排队、等待)的科学。具体地说,它是在研究各种排队系统概率规律性的基础上,解决相应排队系统的最优设计和最优控制问题。,前 言,排队是我们在日常生活和生产中经常遇到的现象。例如,上、下班搭乘公共汽车;顾客到商店购买物品;病员到医院看病;旅客到售票处购买车票;学生去食堂就餐等就常常出现排队和等待现象。除了上述有形的排队之外,还有大量的所谓“无形”排队现象,如几个顾客打电话
2、到出租汽车站要求派车,如果出租汽车站无足够车辆、则部分顾客只得在各自的要车处等待,他们分散在不同地方,却形成了一个无形队列在等待派车。,排队的不一定是人,也可以是物例如,通讯卫星与地面若干待传递的信息;生产线上的原料、半成品等待加工;因故障停止运转的机器等待工人修理;码头的船只等待装卸货物;要降落的飞机因跑道不空而在空中盘旋等等。,显然,上述各种问题虽互不相同,但却都有要求得到某种服务的人或物和提供服务的人或机构。排队论里把要求服务的对象统称为“顾客”,而把提供服务的机构或人称为“服务台”或“服务员”。不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务
3、而又允许排队等待,则加入等待队伍,待获得服务后离开系统。,面对拥挤现象,人们总是希望尽量设法减少排队,通常的做法是增加服务设施。但是增加的数量越多,人力、物力的支出就越大,甚至会出现空闲浪费,如果服务设施太少,顾客排队等待的时间就会很长,这样对顾客会带来不良影响。于是,顾客排队时间的长短与服务设施规模的大小,就构成了设计随机服务系统中的一对矛盾。如何做到既保证一定的服务质量指标,又使服务设施费用经济合理,恰当地解决顾客排队时间与服务设施费用大小这对矛盾,这就是随机服务系统理论排队论所要研究解决的问题。,排队论是1909年由丹麦工程师爱尔朗(A.K.Erlang)在研究电话系统时创立的,几十年来
4、排队论的应用领域越来越广泛,理论也日渐完善。特别是自二十世纪60年代以来,由于计算机的飞速发展,更为排队论的应用开拓了宽阔的前景。,排队论研究的基本问题 排队论研究的首要问题是排队系统主要数量指标的概率规律,即研究系统的整体性质,然后进一步研究系统的优化问题。与这两个问题相关的还包括排队系统的统计推断问题。(1)通过研究主要数量指标在瞬时或平稳状态下的概率分布及其数字特征,了解系统运行的基本特征。(2)统计推断问题,建立适当的排队模型是排队论研究的第一步,建立模型过程中经常会碰到如下问题:检验系统是否达到平稳状态;检验顾客相继到达时间间隔的相互独立性;确定服务时间的分布及有关参数等。,(3)系
5、统优化问题,又称为系统控制问题或系统运营问题,其基本目的是使系统处于最优或最合理的状态。系统优化问题包括最优设计问题和最优运营问题,其内容很多,有最少费用问题、服务率的控制问题、服务台的开关策略、顾客(或服务)根据优先权的最优排序等方面的问题。,第一节 排队论的基本知识,服务过程特征1)有要求服务的人或物。如:去食堂就餐的顾客,去医院看病的病人,要求通过交叉口的汽车,请求着陆的飞机等。2)有为顾客服务的人或物。如:食堂服务员,医院大夫,信号交叉口,飞机跑道等,在排队论中,统称它们为“服务员”或“服务台”。由顾客和服务员组成一个服务系统。,3)顾客到达服务系统的时刻是随机的。如:汽车到达交叉口,
6、顾客到达商店等都是随机的。每位顾客需要的服务时间也是随机的,有的服务时间长,有的服务时间短。因而整个服务系统的状态也是随机的。服务系统的随机性造成某个阶段顾客排队长,而某些时候,服务员又空闲无事。,一般的排队过程为:顾客由顾客源出发,到达服务机构(服务台、服务员)前,按排队规则排队等待接受服务,服务机构按服务规则给顾客服务,顾客接受完服务后就离开。排队过程的一般过程可用下图表示。我们所说的服务系统就是指图中实框所包括的部分。,对上面所说的“顾客”和“服务员”要作广泛的理解。它们可以是人,也可以是某种物质或设备。排队可以是有形的,也可以是无形的。,排队过程的一般表示,损失制系统 当顾客到达这种服
7、务系统时,若服务员都忙着,则顾客立即离去,另求服务。例如,打电话遇到占线,用户搁置而去;汽车停车场放满时,就立即离去,另找停车场。等待制系统 顾客到达该服务系统时,服务员都在为先到的顾客服务,后到的顾客只好参加排队,等候服务,一直等到有空的服务员来为它服务为止。例如,汽车在通过信号交叉口时,如果遇到红灯,汽车只好在停车线后排队等候,等到绿灯时通过。,服务系统分类,混合制系统 介于前两个系统之间,当顾客到达时,若服务员都不空,他就排队,但如果顾客到达时服务员都不空,且排队位置已满,顾客就立即离去,这是排队长度有限制的服务系统。例如,去理发店理发,当等待理发的位置都满时,后来的顾客只得离去。在混合
8、制中,还有另外一种形式:当顾客到达时,服务员不空,他就排队,等待服务,当顾客等了一段时间后,仍轮不到为他服务,顾客就离开队列,另求服务,这称为排队时间有限制的服务系统。例如,药品、电子元件等过期失效均属此类系统。,服务系统分类,服务系统组成,尽管排队系统是多种多样的,但从决定排队系统进程的因素来看,它有三个基本的组成部分,这就是输入过程、排队规则及服务机构。,1)输入过程:描述顾客来源以及顾客到达排队系统的规律。包括:顾客相继到达的时间间隔是确定型的还是随机型的;如:列车是按列车时刻表进站,到站时刻是确定型的;城市信号交叉口,汽车到达交叉口的时刻是随机的。顾客的总体(即顾客源)的组成是无限的还
9、是有限的。如,在道路交叉口,到达车辆的总体可以看成是无限的,而工厂内停机待修的机器显然是有限的。,2)排队规则:(在损失制系统中,没有顾客排队,所以不存在排队问题,这里的排队规则是相对于等待制和混合制系统而言的),先到先服务(FCFS):即按顾客到达的先后次序给予服务,这是最普遍的情况。后到先服务(LCFS):如在情报系统中,最后到达的情报往往是最有价值的,应优先采用;如堆在仓库中的钢板,使用时先用堆在上面的(即后堆上去的)钢板。,随机服务(RSS):当一个顾客被服务完了之后,服务员从排队的顾客中任取一个,给予服务。如电话交换台接通呼叫电话就是一例。有优先权的服务(PR):分轻重缓急给予服务。
10、如加急电报要先于普通电报拍发;重病号应先于轻病号医疗等。,3)服务机构:包括为每个顾客服务所需时间的概率分布,服务台的数目以及服务台的排列方式(串联、并联等)。顾客的服务时间一般具有两种形式:一种是每个顾客的服务时间是一个确定量,一种是每个顾客的服务时间是一个随机变量,它服从某一概率分布。对于服务台的排列方式,分单通道与多通道两种。,单通道服务系统,单通道单服务台系统,单通道多服务台串联系统(如装配流水线),多通道服务系统,可通的多通道系统,不可通的多通道系统,多通道混合系统,排队模型的表示方法,在1953年提出了一个分类方法,按照系统的三个最主要的、影响最大的三个特征要素进行分类,它们是:顾
11、客相继到达的间隔时间分布、服务时间的分布、并列的服务台个数。按照这三个特征要素分类的排队系统,用符号(称为Kendall记号)表示为 X/Y/Z其中X处填写顾客相继到达的间隔时间分布,Y处填写服务时间的分布,Z处填写并列的服务台个数。例如M/M/1,表示顾客相继到达的间隔时间为负指数分布、服务时间为负指数分布、单服务台的模型。,后来,在1971年关于排队论符号标准化的会议上决定,将Kendall符号扩充为:X/Y/Z/A/B/C 其中前三项意义不变。A处填写系统容量限制;B处填写顾客源中的顾客数目;C处填写服务规则(如先到先服务FCFS,后到先服务LCFS)。表示相继到达间隔时间和服务时间的各
12、种分布的符号为:M-负指数分布;D-确定型分布;Ek-k阶爱尔朗分布;GI-一般独立随机分布;G-一般随机分布。,服务系统的运行指标,对于一个排队系统,运行状况的好坏既涉及到顾客的利益,又涉及到服务机构的利益,还有社会效果好坏的问题。为了研究排队系统运行的效率、估计服务质量、研究设计改进措施,必须确定一些基本指标,用以判断系统运行状况的优劣。下面介绍几种常用的指标。,1)队长:把系统中的顾客数称为队长,它的期望值记作Ls。而把系统中排队等待服务的顾客数称为排队长(队列长),它的期望值记作Lq。显然有 队长排队长正被服务的顾客数。,2)逗留时间:一个顾客从到达排队系统到服务完毕离去的总停留时间称
13、为逗留时间,它的期望值记作Ws。一个顾客在系统中排队等待的时间称为等待时间(或排队时间),它的期望值记作Wq。显然有 逗留时间等待时间服务时间。3)忙期:指从顾客到达空闲服务机构起到服务机构再次空闲止的时间长度,即服务机构连续繁忙的时间长度。,研究目的:通过对排队系统中概率规律的研究,使系统达到最优设计和最优控制,以最小费用实现系统的最大效益。,第二节 顾客到达分布和服务时间分布,泊松分布负指数分布,泊松(poisson)输入,又称最简单流。满足下面3个条件的输入称之为最简单流。(1)平稳性。又称作输入过程是平稳的,指在长度为t的时段内恰好到达k个顾客的概率仅与时段长度有关,而与时段起点无关。
14、即对任意(0,),在(,+t或(0,t)内恰好到达k个顾客的概率相等。,(2)无后效性。指在任意几个不相交的时间区间内,各自到达的顾客数是相互独立的。通俗地说就是以前到达的顾客情况,对以后顾客的到来没有影响。否则就是关联的。(3)单个性又称普通性。指在充分小的时段内最多到达一个顾客。在一个充分小的时间间隔里不可能有两个或两个以上的顾客到达,只能有一个顾客到达。换句话说,有两个或两个以上的顾客到达的概率与有一个顾客到达的概率相比小到可以忽略的程度。因为泊松流实际应用最广,也最容易处理,因而研究得也较多可以证明,对于泊松流,在长度为t的时间内到达K个顾客的概率vk(t)服从泊松分布,即,如果顾客的
15、到达过程(在确定的时间区间内到达的顾客数)服从最简单流,则顾客的到达时间间隔服从参数为 的负指数分布。如果顾客的服务过程(即离开服务台的过程)服从最简单流,则顾客的服务时间服从参数 的负指数分布。从本质上看,泊松分布与负指数分布是同一个过程的不同表现形式。,第三节 生灭过程,研究系统内部状态变化的过程,系统状态i,状态i+1,状态i-1,在t时刻内发生两个或两个以上事件的概率为O(t),一个事件,一个事件,一、生灭过程定义,t0,O(t)0,系统具有0,1,2,个状态。在任何时刻,若系统处于状态i,并且系统状态随时间变化的过程满足以下条件,称为一个生灭过程:,1、在(t,t+t)内系统由状态i
16、转移到状态i+1的概率为it+O(t)平稳性条件,t内有一个顾客到达的概率,2、在(t,t+t)内系统由状态i转移到状态i-1的概率为it+O(t)平稳性条件,t内有一个顾客离开的概率,3、在(t,t+t)内系统发生两次以上转移的概率为O(t),即有2个以上顾客到达或离开的概率为,普遍性条件,只要排队系统的输入过程和服务过程符合泊松分布,排队过程符合生灭过程,二、生灭过程状态转移图,状态,顾客到达率,系统服务率,t时,Pi(t)趋向于常数:系统达到稳定,系统达到稳定后:每个状态转入率的期望值与转出率的期望值相等。,对于状态i:转出率的期望值为,转入率的期望值为,P0,P1,P2,Pi,有,对于
17、S0,转入,转出,转出,转入,对于Sk,P0,P1,P2,Pi,状态转移方程,求解该方程,可以获得各状态对应的概率,对于S0,对于S1,依次类推,且有,例:,某排队系统:M/M/1/3/FCFS,=2,=3。求解各状态对应的概率。,首先,做出相应的状态转移图,对于S0,对于S1,对于S2,生灭过程求解排队系统各状态概率过程,建立状态转移图,建立状态转移方程,求解状态转移方程,各状态转入率期望值与转出率期望值相等,各状态概率,第三节 M/M/1排队系统,顾客到达服从泊松分布顾客到达率为服务过程服从泊松分布(负指数分布)系统服务率为单通道,先到先服务,最简单的M/M/1排队系统:,M/M/1/,M
18、/M/1/m/,M/M/1/排队系统,系统容量无限、顾客源无限,最基本的排队系统,排队过程为生灭过程,列状态转移方程组求各状态概率,M/M/1/排队系统各状态概率归结为无穷等比数列求和,1,数列收敛,P0=1-,1,数列发散,系统稳定,系统不稳定,称为服务强度,若服务强度大于1,说明单位时间内到达的顾客数比完成服务的顾客数多,系统中排队长度越来越大,产生阻塞。,利用排队系统各状态概率计算运行指标,1、队长系统中的顾客数量,队长,2、排队长系统中等待的顾客数量,通道数,3、逗留时间顾客在排队系统中的总时间,李太勒公式,前后2名顾客到达系统的时间间隔,4、排队时间顾客在排队系统中的等待时间,李太勒
19、公式,前后2名顾客到达系统的时间间隔,M/M/1/m/排队系统,系统容量有限、顾客源无限,列状态转移方程组求各状态概率,并不要求1。,特别地,当=1时,P0=1/(m+1),(1),利用排队系统各状态概率计算运行指标,1、队长系统中的顾客数量,队长,2、排队长系统中等待的顾客数量,通道数,3、逗留时间顾客在排队系统中的总时间,李太勒公式,前后2名顾客到达系统的时间间隔,有效到达率e,当排队长度未满容量时,平均到达率为当排队容量已满容量时,平均到达率为0,逗留时间,4、排队时间顾客在排队系统中的等待时间,李太勒公式,前后2名顾客到达系统的时间间隔,顾客的到达是服从参数的泊松分布;顾客的服务时间是
20、服从参数为的负指数分布;有S个服务台,顾客按到达的先后次序接受服务。,第四节 M/M/S排队系统,当顾客到达时,若有空闲的服务台就立即接受服务,若所有的服务台都忙着,则顾客排成一个队列等待服务。,常见的M/M/S/及M/M/S/m/两类,M/M/S/排队系统标准M/M/S系统,系统中个服务台的服务率均为,于是整个服务机构的最大服务率为S。与M/M/1/系统类似,只有当 时,才能使服务系统达到稳态而不排成无限的队列。,系统的服务强度,当系统中只有一个顾客时,则有S-1个服务台空闲着,仅一个服务台在服务,这时的服务率为,当系统有2个顾客时,就有2个服务台工作,其服务率为2,当系统中有S个顾客时,则
21、服务率达到最大值S,当系统中的顾客数超过S时,由于个服务台都忙着,其余顾客必须排队,这时的服务率仍为S,M/M/1系统,M/M/S系统,M/M/S系统,根据正则条件,利用排队系统各状态概率计算运行指标,1、排队长,2、平均等候时间,3、逗留时间,、平均顾客数,系统容量受限制、顾客源无限、先到先服务的M/M/S系统。该系统共有m-S个位置可供顾客排队。当顾客到达时,若系统饱和,即服务台都忙着,排队位置已排满,则后到的顾客立即离去,另求服务。因此,该系统中只可能有m+1个状态。,M/M/S/m/排队系统,与M/M/S/系统的推导类似,可得M/M/S/m/系统的状态指标及运行指标。,第五节 排队服务
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 交通 系统分析 系统 状态 描述

链接地址:https://www.31ppt.com/p-6361453.html