交通排队理论

1、7 交通排队技术,7.1排队系统排队现象,排队是日常生活中经常遇到的现象，如顾客到商店购买物品形成的排队；上下班坐公共汽车，等待公共汽车的排队；文件等待打印和发送；电话占线；故障机器停机待修；水库的存贮调节等。 在交通系统中，排队现象也相当普遍，如车辆通过信号交叉口时常需排队，汽车在加油站加油常需排队，汽车在通过道路的“瓶颈”地段时常需排队，货轮进港、飞机着落等也常需排队。 对于各种排队系统或服务系统，将其中要求得到服务的对象统称为“顾客”，将提供服务者统称为“服务机构”，顾客与服务机构之间存在一种服务关系。,7.1排队系统排队现象,实际的排队系统千差万别，但都可概括为：顾客为得到某种服务到达

2、服务机构，若不能立即得到服务又允许排队等待，则加入等待队伍，直到获得服务后离去。 如果到达服务系统的顾客完全按固定的间隔时间到达，服务设施用在每个顾客身上的服务时间也是固定的，就象工厂流水生产线那样有固定的节拍，这类服务系统的设计计算是比较方便的。 但在大多数的服务系统中，顾客的到达经常是随机的，并且服务设施用于每个顾客身上的服务时间往往也是随机的，对于这样一类随机服务系统的设计计算要复杂得多。,7.1排队系统排队现象,排队现象不可避免。如果增加服务设备（服务台），就要增加投资或发生空闲浪费；如果服务设备太少，排队现象就会严重，对顾客个人和对社会都会带来不利影响。 车站的售票口应开设多少个比较

3、合适那？开设越多，方便旅客，减少排队时间；但售票口增多了，就要增加服务人员及相关的设施，增加服务费用。 顾客排队时间长短与服务设施规模大小构成随机服务系统中的一对矛盾。有些场合下，如公共汽车的班次可以随季节及顾客到达规律的变化进行调整，但另一些场合，服务设施的规模，如机场跑道、港口泊位、电话线路等一旦建成则不易改动，因此需要有一个进行设计计算遵循的理论依据。,7.1排队系统排队现象,到底怎样才能做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用这对矛盾，这就是研究随机服务系统的理论排队论所要研究解决的问题。 排队论（Queuing theory），亦称

4、随机服务系统理论，是研究排队现象的一门科学，是20世纪初丹麦科学家爱尔兰（A.K.Erlang）在研究电话通话的拥挤问题时提出的理论。排队论首先应用于电话行业，目前已被广泛应用于交通、运输等公用事业系统及其他领域。,7.1排队系统排队问题构成,到达总体 到达间隔,泊松分布 负指数分布,损失制 等待制 混合制,先到先服务 后到先服务 优先服务 随机服务,泊松分布 负指数分布,到达过程/服务过程/服务台数/系统容量/顾客源容量/排队规则,X/Y/Z,肯道尔表示排队模型,7.1排队系统服务系统,7.1排队系统服务系统,多通道混合服务系统,7.1排队系统顾客到达分布,影响排队的主要因素是单位时间内要求

5、服务机构给予服务的顾客数和每个顾客所需的服务时间。 要想预测在某一时刻将有多少顾客要求服务系统服务，或者预测某一顾客的服务时间将要延误多久这都是不可能的。 只能对单位时间内到达系统的顾客数、服务时间这两个随机变量进行概率的描述。 描述顾客到达和服务时间的方法。一般是求出它的概率密度函数或概率的分布函数。具体地说，就是要求出单位时间内有个顾客到达系统要求服务的概率，以及服务时间不少于某一时间长度的概率。 在排队论中，描述到达分布和服务时间分布的分布形式有最简单（泊松流）、负指数分布、爱尔朗分布、二项分布、正态分布等。,7.1排队系统顾客到达分布,顾客到达分布一般服从最简单流，又称为平稳的泊松流。

6、,即对于最简单流，在长度为t的时间区间内，顾客到达数N(t)为服务从参数为t 的泊松分布。它的数学期望和方差分别为：,7.1排队系统顾客到达分布,某铁路与公路相交的平面交叉口，当火车通过交叉口时，横木护栏挡住汽车通行，每次火车通过时，平均封锁公路3min，公路上平均每分钟有辆汽车到达交叉口。求火车通过交叉口时，汽车排队长度超过12辆的概率。,7.1排队系统顾客到达分布,排队汽车不超过12辆的概率为：,排队汽车超过12辆的概率为：,有42.4%的情况，汽车排队长度超过12辆。,7.1排队系统服务时间分布,排队系统服务时间分布一般服从负指数分布。 如果顾客服务完毕，从服务机构离去的流也是完全随机的

7、，在时段t内，有n个顾客从服务机构离去的概率,式中：Pn(t)服从参数为t的泊松分布，其中n为单位时间内顾客服务完毕而离去的平均数平均服务率；1/ 为每个顾客的平均服务时间,7.1排队系统服务时间分布,当n时,即表示在长度为t的时段内没有顾客离去的概率为,7.1排队系统排队系统指标,1）队长系统中平均顾客数，包括排队的顾客和正在接受服务的顾客。 2）排队长系统中排队等待服务的平均顾客数。 3）逗留时间顾客的平均逗留时间，包括排队时间和接受服务时间。 4）等待时间顾客排队等待的平均时间。 5）系统空闲概率系统统没有顾客的概率。 6）系统中有个顾客的概率。 7）忙期从顾客到达空闲服务结构起到服务结

8、构再次空闲的概率。,7.1排队系统排队系统类型,一般地，对顾客总体数量无限、系统中的队长无限、排队规则为先到先服务，排队系统又可表述为X/Y/Z。 最常用的排队系统为M/M/1排队系统和M/M/S排队系统。,7.1排队系统排队系统类型,7.2生灭过程生灭过程定义,生灭过程是生物界用来研究诸如细菌的繁殖、人口的增长等现象的数学模型。由于在排队服务系统中，顾客的到达相当于“生”，顾客的离去相当于“灭”，顾客在系统中数量的增长正如社会系统中人口的增长一样，因此可以把服务系统用生灭过程来描写。 生灭过程具有随机性，服务系统也具有随机性，顾客到达服务系统的时间和数量是随机的，对每个顾客进行服务所需要的时

9、间长短也是不确定的。这两方面共同作用的结果是，服务系统内的顾客有时要排队，有时不排队、排队的队伍有时长、有时短。,7.2生灭过程生灭过程定义,7.2生灭过程状态转移方程,7.2生灭过程状态转移方程,根据正则条件得到,可求 ，进而求,7.2生灭过程应用算例,某排队模型为M/M/1/3/FCFS,=2,=3.试求该系统的状态概率Pi.,该系统的到达过程，服务过程均为泊松流，故其内部状态符合生灭过程。系统具有个状态：S0,S1,S2,S3,其状态转移图如图所示。,2,3,7.2生灭过程应用算例,首先，根据每个状态的平衡条件建立状态方程组,由S0状态得,由S1状态得,由S2状态得,7.3 M/M/1系

10、统M/M/1/系统特征,M/M/1/系统是指系统容量，顾客源均为无限的M/M/1系统，在排队论中，它有特殊的地位，通常称之为标准的M/M/1系统。 由生灭过程的定义可知，该系统的排队过程为一生灭过程该系统的状态转移图如图所示。,M/M/1/系统的状态转移图,7.3 M/M/1系统M/M/1/系统特征,有着重要的意义，通常称之为服务强度，它是相同时间间隔内顾客的平均到达数与能被服务的平均数之比；或是对于相同的顾客数，服务时间之和的期望值与到达间隔时间之和的期望值之比，这个比是刻画服务效率和服务机构利用程度的重要指标。,7.3 M/M/1系统M/M/1/系统特征,在M/M/1/排队系统中，必须有1

11、，即单位时间内到达服务系统的顾客数大于离开服务系统的顾客数，那么当t时，排队长度将无限增加，使系统达不到稳定状态。 当=1时，系统的负荷水平达到100%，即单位时间内到达的顾客数等于离开的顾客数，但这时也无法达到稳定状态。虽然这时平均到达率等于平均服务率，但由于到达是随机的，可能有些时候服务台是空闲的，因而失去了一些可用于服务的时间，这种时间损失越多，排队积累越快，渐渐的越排越长，而达不到统计平衡。,7.3 M/M/1系统M/M/1/系统特征,由正则条件可得：,P0、Pn称为系统的状态概率， P0表示系统中没有顾客（即服务台空闲）的概率， Pn表示系统有n个顾客（其中有n-1个顾客排队）的概率

12、。,7.3 M/M/1系统M/M/1/系统特征,以P0、Pn为基础，可以导出系统的一系列运行指标 系统中的平均顾客数（队长期望值）L，设系统中的顾客数（包括排队的和正在被服务台的）为N，则N是个随机变量。令L是N的期望值，则,7.3 M/M/1系统M/M/1/系统特征,7.3 M/M/1系统M/M/1/系统特征,7.3 M/M/1系统M/M/1/系统特征,7.3 M/M/1系统公路收费口排队系统,某收费公路入口处设有一收费亭，汽车进入公路必须向收费亭交费，收费亭的收费时间服从负指数分布，平均每辆汽车的交费时间为7.2s，汽车的到达率为400辆/h，并服从泊松分布。试求： 收费亭空闲的概率； 收

13、费亭前没有车辆排队的概率； 收费亭前排队长度超过100 m（即排队车辆超过12辆）的概率； 平均排队长度； 车辆通过收费亭所花费时间的平均值； 车辆的平均排队时间。,7.3 M/M/1系统公路收费口排队系统,=400辆/h = 3600/7.2=500辆/h =/=400/500=0.8,这是一个M/M/1/排队系统，收费亭是服务台，汽车是顾客，汽车向收费亭交费便是接受服务。 由题意可知：,7.3 M/M/1系统公路收费口排队系统,收费亭空闲的概率 收费亭空闲的概率即为系统中没有车辆到达的概率P0。 P0=1-=1-0.8=0.2,没有车辆排队的概率 当系统中没有车辆或只有一辆车辆（这辆车正在

14、被服务）时，便没有车辆排队。所以，没有车辆排队的概率为：,7.3 M/M/1系统公路收费口排队系统,排队长度超过100m的概率 排队长度超过100m的概率即为排队车辆超过12辆的概率，也就是系统中车辆超过13辆的概率。所以,平均排队长度,7.3 M/M/1系统公路收费口排队系统,车辆通过收费亭所花的平均时间,车辆的平均排队时间,7.3 M/M/1系统交叉口规划问题,某主要道路与次要道路相交的无控制交叉口，主要道路有优先通行权，即主路上的汽车通行不受次路上的汽车影响，次路上的汽车必须等候主路上汽车流中的较大的车头时距横穿通过，两条道路上的车流到达过程符合泊松分布。 我们把车辆通过交叉口看成是车辆

15、接受了服务，那么次要道路上排队车流中的第一辆汽车为正在接受服务的顾客，第一辆汽车从到达停车线到通过交叉口的时间就是服务时间，它与主路车流的车头时距分布有关，当主路车流符合泊松流时，次路车辆的服务时间总是服从负指数分布的。,7.3 M/M/1系统交叉口规划问题,在次路车流中，从第二辆起的汽车即为排队等候服务的顾客，因此，该交叉口系统就是一个标准的M/M/1系统。设次路车流的交通量为350辆/h。次路车辆从到达停车线到通过交叉口的平均服务时间为10s。试求该系统的运行指标,7.3 M/M/1系统交叉口规划问题,该系统中,交叉口没有车辆的概率,交叉口前排队车辆（包括正待通过的第一辆车）超过50辆的概

16、率,7.3 M/M/1系统交叉口规划问题,交叉口前的平均排队车辆数（包括第一辆）,车辆到达通过交叉口所需的平均时间,从上面的这些指标可以看出，该交叉口时相当拥挤的，交叉口前有97%的时间出现排队现象，平均排队长度达35辆，有24%的时间排队长度超过50辆，车辆在交叉口前平均需要排队6min，阻塞相当严重，应采取措施予以改善，如拓宽进口，设置两条平行的进口车道，或设置交通信号灯等。,7.3 M/M/1系统M/M/1/m/系统,所谓M/M/1/m/排队系统是指系统容量受限制，顾客源为无限，先到先服务的M/M/1系统，设系统容量为 m，即排队容量m-1，当顾客到达时，若服务台不空，则顾客参加排队等候

17、服务，因为系统内只有m-1个排队位置，当客满时，后来的顾客立即离去，另求服务，因此，该系统只可能具有 m+1个状态；S0、S1、S2、Sm。,M/M/1/m/系统状态转移图,7.3 M/M/1系统M/M/1/m/系统,正则条件可得：,n,7.3 M/M/1系统M/M/1/m/系统,系统平均顾客数（队长）Ls 当1时，,或,当=1时，,7.3 M/M/1系统M/M/1/m/系统,平均排队顾客数（排队长）Lq,7.3 M/M/1系统M/M/1/m/系统,顾客在系统中的平均逗留时间Ws 在系统中，当排队长度未满排队容量时，平均到达率为，而一旦排满，到达率为0，即：,因此，有必要寻求整个过程的有效到达

18、率，取有效到达率为到达率的期望值：,7.3 M/M/1系统M/M/1/m/系统,即,所以，由李太勒公式得：,顾客在系统中的平均排队时间Wq,7.3 M/M/1系统加油站排队系统,某市区有一加油站为汽车加油，站上服务台平均36s处理一辆汽车，加油时间服从负指数分布，汽车到加油站加油到达率为80辆/h，并服从泊松分布，当等候加油的汽车超过10辆（即排队长度超过80m，不包括正在加油的汽车）时，将影响加油站附近街道的正常交通，因而规定排队汽车不得超过10辆。试求： 加油站空闲的概率； 汽车来加油但因排队已满而被拒绝的概率； 在系统中的平均顾客数； 平均排队长度； 汽车在整个加油过程中所花的时间； 汽

19、车排队等候时间。,7.3 M/M/1系统加油站排队系统,该系统为M/M/1/m/系统，并且m=11,加油站空闲的概率,汽车被拒绝加油的概率 汽车被拒绝的概率，就是系统饱和时的状态概率,即约有2%的汽车因队满而被拒绝加油,7.3 M/M/1系统加油站排队系统,系统中的平均汽车数,平均长度,汽车在整个加油过程中花费的时间,有效到达率,汽车排队等候时间,7.4 M/M/S系统M/M/S / /系统,M/M/S/ /排队系统是指顾客源，系统容量均为无限的M/M/S/系统，通常称之为标准的M/M/S/系统。 由于系统中S个服务台的服务率均为u，于是整个机构的最大服务率为Su。与M/M/1/ /系统类似，

20、只有当/Su 1时，才能使服务系统达到稳态而不排成无限的队列 令 = /Su 称它为这个系统的服务强度。,7.4 M/M/S系统M/M/S / /系统,当系统中只有一个顾客时，则有S-1个服务台空闲着，仅一个服务台在服务，这时的服务率为u，当系统有2个顾客时，就有2个服务台工作，其服务率为2u，当系统中有S个顾客时，则服务率达到最大值Su，当系统中的顾客数超过S时，由于S个服务台都忙着，其余顾客必须排队，这时的服务率仍为Su,即,M/M/S/系统的状态转移图,7.4 M/M/S系统M/M/S / /系统,当nS时,当nS时,7.4 M/M/S系统M/M/S / /系统,而,即,s,7.4 M/

21、M/S系统M/M/S / /系统,系统中的平均排队长度Lq,7.4 M/M/S系统M/M/S / /系统,顾客在系统中的平均等候时间Wq 由李太勒公式得,顾客在系统中的平均逗留时间Ws,系统内的平均顾客数Ls 由李太勒公式得,7.4 M/M/S系统修理站服务系统,某汽车修理服务站，前来修理的车辆是随机到达的，到达率为4辆/h，每辆汽车在站上修理的持续时间平均0.5h,并服从负指数分布。该站有5个修理服务台可供修理。试求该服务站的运行指标。 解：该服务站的服务系统为没M/M/S/系统，并且S=5，=4辆/h，u=1/0.5=2辆/h, /=2，=/Su=4/52=0.4,无来车修理的概率（既所有

22、服务台均空闲的概率）,7.4 M/M/S系统修理站服务系统,修理站前的不出现汽车排队的概率 当在修理站修理的汽车不超过5辆时，就不会出现排队现象。,7.4 M/M/S系统修理站服务系统,所以，不出现排队现象的概率为：,即在97.3%的情况下，不会出现排队现象。,修理站前的平均排队长度,出现排队的概率,7.4 M/M/S系统修理站服务系统,整个系统中的车辆平均数,汽车排队等候修理所花费的时间,汽车在整个修理过程中所花的时间,7.4 M/M/S系统收费亭问题,在某收费公路入口处，并排设有3个收费亭，车辆进入收费公路需在收费亭缴费，因而在收费亭前常出现排队现象，收费亭前的排队引道可考虑采用两种方案。

23、,7.4 M/M/S系统收费亭问题,a)方案为车辆到达后排成一队，依次向任一空闲的收费亭缴费进入公路；b) 方案为车辆到达后在三个收费亭前排成三队，三队中间设有分隔带，每队中的车辆只能从相应的收费亭进入公路。 设三个收费亭的服务率是相同的，平均10s处理一辆汽车，车辆的到达率为900辆/h，试比较两种排队系统的运行指标。,1. a)方案排队系统分析 该系统为标准的M/M/S排队系统,7.4 M/M/S系统收费亭问题,收费亭空闲的概率P0,车辆必须排队的概率（P3）,排队的平均车辆数,7.4 M/M/S系统收费亭问题,整个系统中平均车辆数,汽车的平均排队时间,汽车通过收费亭所花的总时间,7.4

24、M/M/S系统收费亭问题,b)方案排队系统分析 该系统实际上就是三个并列的标准M/M/1排队系统。每个子系统中： u=360辆/h =300辆/h =300/360=0.833 每个子系统运行指标如下： P0 P0=1-=0.167,7.4 M/M/S系统收费亭问题,车辆必须排队的概率P（1）,Lq,Ls,Wq,Ws,7.4 M/M/S系统收费亭问题,两种方案的主要运行指标比较 将上面计算的两个系统的主要运行指标列于表，由表可见，在相同的到达率及相同的服务率下，M/M/S排队系统明显优于多个M/M/1并联的排队系统。,两方案主要运行指标,7.4 M/M/S系统收费亭问题,在相同的到达率及相同的

25、服务率下，M/M/S排队系统明显优于多个M/M/1并联的排队系统。 在多个M/M/1并联系统中，表面上看起来车流被分散到三个服务台，但实际上受着排队车道与服务台一一对应的束缚，当某一服务台空闲时，其他服务台前的排队车辆不能改道来利用这个服务台，造成某些服务台空闲，而有些服务台前还有车辆排队的现象。 在M/M/S排队系统中，排在第一位的车辆可以到任一空闲的服务台接受服务，比较机动，因此，就整个系统而言， M/M/S系统疏散排队车流的速度反而比多个M/M/1并联系统的疏散速度要快得多。,7.4 M/M/S系统M/M/S /m/系统,所谓M/M/S/m/排队系统是指系统容量受限制、顾客源无限，先到先

26、服务的M/M/S/系统：该系统共有n-s个位置可供顾客排队。当顾客到达时，若系统饱和，即服务台都忙着，排队位置已满，则后到的顾客立即离去，另求服务。因此，该系统中只可能有m+1个状态。,M/M/S/m/ 系统的状态转移图,7.4 M/M/S系统M/M/S /m/系统,7.4 M/M/S系统M/M/S /m/系统,特别当 m=S时，我们称这种情况为通道损失制排队系统，即当S个服务台均不空时，顾客来到服务系统不予服务，顾客立即离去，另求服务，这种情况也是常见的。例如，在闹市的停车场，就不允许汽车排队等待空位，这时,7.4 M/M/S系统加油站加油系统,汽车自动加油站上设有两条加油管，汽车按最简单流到达，每2min到达一辆，汽车加油时间服从负指数分布，平均加油时间为2min/辆。自动加油站上最多只能停3辆汽车等候加油。如果汽车到来时，系统已饱和，则汽车另求服务。试求该系统的运