7交通排队理论

7交通排队技术排队是日常生活中经常遇到的现象，如顾客到商店购买物品形成的排队；上下班坐公共汽车，等待公共汽车的排队；文件等待打印和发送；电话占线；故障机器停机待修；水库的存贮调节等。在交通系统中，排队现象也相当普遍，如车辆通过信号交叉口时常需排队，汽车在加油站加油常需排队，汽车在通过道路的“瓶颈”地段时常需排队，货轮进港、飞机着落等也常需排队。对于各种排队系统或服务系统，将其中要求得到服务的对象统称为“顾客”，将提供服务者统称为“服务机构”，顾客与服务机构之间存在一种服务关系。实际的排队系统千差万别，但都可概括为：顾客为得到某种服务到达服务机构，若不能立即得到服务又允许排队等待，则加入等待队伍，直到获得服务后离去。如果到达服务系统的顾客完全按固定的间隔时间到达，服务设施用在每个顾客身上的服务时间也是固定的，就象工厂流水生产线那样有固定的节拍，这类服务系统的设计计算是比较方便的。但在大多数的服务系统中，顾客的到达经常是随机的，并且服务设施用于每个顾客身上的服务时间往往也是随机的，对于这样一类随机服务系统的设计计算要复杂得多。排队现象不可避免。如果增加服务设备（服务台），就要增加投资或发生空闲浪费；如果服务设备太少，排队现象就会严重，对顾客个人和对社会都会带来不利影响。车站的售票口应开设多少个比较合适那？开设越多，方便旅客，减少排队时间；但售票口增多了，就要增加服务人员及相关的设施，增加服务费用。顾客排队时间长短与服务设施规模大小构成随机服务系统中的一对矛盾。有些场合下，如公共汽车的班次可以随季节及顾客到达规律的变化进行调整，但另一些场合，服务设施的规模，如机场跑道、港口泊位、电话线路等一旦建成则不易改动，因此需要有一个进行设计计算遵循的理论依据。到底怎样才能做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用这对矛盾，这就是研究随机服务系统的理论——排队论所要研究解决的问题。排队论（Queuingtheory），亦称随机服务系统理论，是研究排队现象的一门科学，是20世纪初丹麦科学家爱尔兰（A.K.Erlang）在研究电话通话的拥挤问题时提出的理论。排队论首先应用于电话行业，目前已被广泛应用于交通、运输等公用事业系统及其他领域。到达总体到达间隔泊松分布负指数分布损失制等待制混合制先到先服务后到先服务优先服务随机服务泊松分布负指数分布到达过程/服务过程/服务台数/系统容量/顾客源容量/排队规则X/Y/Z肯道尔表示排队模型顾客来源排队结构服务机构顾客到来服务规则排队规则排队结构离去顾客来源服务机构顾客到来123到达服务台服务台服务台服务台离去单通道多服务台串联系统离去123到达离去离去离去可互通的多通道系统1服务台离去单通道单服务台系统顾客到达1离去顾客到达3离去顾客到达2离去顾客到达不可互通的多通道系统12112k多通道混合服务系统影响排队的主要因素是单位时间内要求服务机构给予服务的顾客数和每个顾客所需的服务时间。要想预测在某一时刻将有多少顾客要求服务系统服务，或者预测某一顾客的服务时间将要延误多久这都是不可能的。只能对单位时间内到达系统的顾客数、服务时间这两个随机变量进行概率的描述。描述顾客到达和服务时间的方法。一般是求出它的概率密度函数或概率的分布函数。具体地说，就是要求出单位时间内有Ｋ个顾客到达系统要求服务的概率，以及服务时间不少于某一时间长度的概率。在排队论中，描述到达分布和服务时间分布的分布形式有最简单（泊松流）、负指数分布、爱尔朗分布、二项分布、正态分布等。()()(0,1,2,)!ntntptenn顾客到达分布一般服从最简单流，又称为平稳的泊松流。即对于最简单流，在长度为△t的时间区间内，顾客到达数N(△t)为服务从参数为λ△t的泊松分布。它的数学期望和方差分别为：[()][()]arENttVNtt7.1排队系统————顾客到达分布某铁路与公路相交的平面交叉口，当火车通过交叉口时，横木护栏挡住汽车通行，每次火车通过时，平均封锁公路3min，公路上平均每分钟有４辆汽车到达交叉口。求火车通过交叉口时，汽车排队长度超过12辆的概率。()()!3min4/minntntPtent辆排队汽车不超过12辆的概率为：011212()()()()PtPtPtPt12120034120()()!(34)!0.576ntnnnnntePtnen排队汽车超过12辆的概率为：12()112()PtPt10.5760.424有42.4%的情况，汽车排队长度超过12辆。7.1排队系统————服务时间分布排队系统服务时间分布一般服从负指数分布。如果顾客服务完毕，从服务机构离去的流也是完全随机的，在时段△t内，有n个顾客从服务机构离去的概率120()()(0,1,2,)!ntnntePtnn式中：Pn(△t)——服从参数为μ△t的泊松分布，其中n为单位时间内顾客服务完毕而离去的平均数——平均服务率；1/μ为每个顾客的平均服务时间tnnenttP!)()(2()1()1arETVTtetTP1)(当n＝０时即表示在长度为△t的时段内没有顾客离去的概率为(11()teptr在时段内没有顾客离去)=p(每一顾客的服务时间t)=-p(每一顾客的服务时间t)=-Ft()tnPte1）队长—系统中平均顾客数，包括排队的顾客和正在接受服务的顾客。2）排队长—系统中排队等待服务的平均顾客数。3）逗留时间—顾客的平均逗留时间，包括排队时间和接受服务时间。4）等待时间—顾客排队等待的平均时间。5）系统空闲概率—系统统没有顾客的概率。6）系统中有个顾客的概率。7）忙期—从顾客到达空闲服务结构起到服务结构再次空闲的概率。一般地，对顾客总体数量无限、系统中的队长无限、排队规则为先到先服务，排队系统又可表述为X/Y/Z。最常用的排队系统为M/M/1排队系统和M/M/S排队系统。生灭过程是生物界用来研究诸如细菌的繁殖、人口的增长等现象的数学模型。由于在排队服务系统中，顾客的到达相当于“生”，顾客的离去相当于“灭”，顾客在系统中数量的增长正如社会系统中人口的增长一样，因此可以把服务系统用生灭过程来描写。生灭过程具有随机性，服务系统也具有随机性，顾客到达服务系统的时间和数量是随机的，对每个顾客进行服务所需要的时间长短也是不确定的。这两方面共同作用的结果是，服务系统内的顾客有时要排队，有时不排队、排队的队伍有时长、有时短。对于状i态i来说，转出率期望值为：()iiiiiiippp转入率的期望值为：1111iiiipp必须有以下的平衡：1111()iiiiiiippp对于状态0i有：1100pp对于状态ik有：11kkkkpp0101002211122111001111111012102121201011()()()(1)1iiiiiiPPPPPPPPPPPPPPPPPiKPkii=0而根据正则条件得到：p根据正则条件得到10kiip可求，进而求0pip2220134333ssss某排队模型为M/M/1/3/∞/FCFS,λ=2,μ=3.试求该系统的状态概率Pi.该系统的到达过程，服务过程均为泊松流，故其内部状态符合生灭过程。系统具有４个状态：S0,S1,S2,S3,其状态转移图如图所示。23首先，根据每个状态的平衡条件建立状态方程组由S0状态得由S1状态得由S2状态得0211210242323,39PPPPPPP即1322320282323,327PPPPPPP即0110223,23PPPP即00000123248139270.415,0.277,0.185,0.123PPPPPPPPki=01iP由正则条件可得01211iiissssssM/M/1/∞/∞系统是指系统容量，顾客源均为无限的M/M/1系统，在排队论中，它有特殊的地位，通常称之为标准的M/M/1系统。由生灭过程的定义可知，该系统的排队过程为一生灭过程该系统的状态转移图如图所示。M/M/1/∞/∞系统的状态转移图000101PPPP,2,1,0n式中：。111112000011nnnnnnnnnnnnnnPPPPPPPPρ有着重要的意义，通常称之为服务强度，它是相同时间间隔内顾客的平均到达数与能被服务的平均数之比；或是对于相同的顾客数，服务时间之和的期望值与到达间隔时间之和的期望值之比，这个比是刻画服务效率和服务机构利用程度的重要指标。在M/M/1/∞/∞排队系统中，必须有ρ1，即服务率大于到达率。如果ρ1，即单位时间内到达服务系统的顾客数大于离开服务系统的顾客数，那么当t→∞时，排队长度将无限增加，使系统达不到稳定状态。当ρ=1时，系统的负荷水平达到100%，即单位时间内到达的顾客数等于离开的顾客数，但这时也无法达到稳定状态。虽然这时平均到达率等于平均服务率，但由于到达是随机的，可能有些时候服务台是空闲的，因而失去了一些可用于服务的时间，这种时间损失越多，排队积累越快，渐渐的越排越长，而达不到统计平衡。nPPnn1)1(11001201mipppp220000001(1)11nnpppppp由正则条件可得：P0、Pn称为系统的状态概率，P0表示系统中没有顾客（即服务台空闲）的概率，Pn表示系统有n个顾客（其中有n-1个顾客排队）的概率。以P0、Pn为基础，可以导出系统的一系列运行指标系统中的平均顾客数（队长期望值）L，设系统中的顾客数（包括排队的和正在被服务台的）为N，则N是个随机变量。令L是N的期望值，则(01)10112323423(1)(23)(23)1nnnnnnnnn0()snnLENnPsL11n01(1)nnPP01211iiissssss11,sqsqsqsqLL11,sqsqsqsqLL1.L2.L3.4.,sqssqqWWLWLWsq系统中的平均顾客数（队长期望值）系统中排队等候的平均顾客数（排队长期望值）顾客在系统中的平均逗留时间顾客在系统中的平均排队时间11,sqsqsqsqLL1.L2.L3.4.,sqssqqWWLWLWsq系统中的平均顾客数（队长期望值）系统中排队等候的平均顾客数（排队长期望值）顾客在系统中的平均逗留时间顾客在系统中的平均排队时间11,sqsqsqsqLL1.L2.L3.4.,sqssqqWWLWLWsq系统中的平均顾客数（队长期望值）系统中排队等候的平均顾客数（排队长期望值）顾客在系统中的平均逗留时间顾客在系统中的平均排队时间11,sqsqsqsqLL