基于Q图的M(t)/M/C服务台配置优化

高琦，宫丽芳，武艳华，戴洪帅

山东财经大学 统计学院，济南 250000

排队系统的研究大体可分为3个方面：① 性能分析； ② 统计推断； ③ 资源配置[1]．在排队模型的研究中，目前学者们通常假设顾客的到达率是不变的，具有平稳性．但在很多情况下，如医院急诊室[2]，顾客的到达具有时变的特征，文献[3]指出若到达率只是偶尔非平稳，利用平稳排队模型分析系统的性能指标，得到的效果并不是最优的．文献[4]指出即使到达率只是适度的不平稳，若利用平稳排队模型拟合系统，也会造成性能指标的严重低估，因此，逐段近似的方法成为研究非平稳排队模型的一类重要方法．最近几十年，具有时变到达率的排队模型的资源配置问题成为学者们的研究热点之一．文献[5]研究了非平稳到达过程的一般模型，使用平方根公式建立了服务台配置算法．文献[6]根据改进的遗传算法建立了有关立体车库的排队模型，该模型可以缓解城市交通的压力，从而可以提升立体车库的服务率．文献[7]为了实现资源利用效率的最大化，提出了以能量最小化为基础的虚拟机簇分配方法．

近年来，排队模型的统计控制问题引起了学者们的广泛关注．文献[8]通过转移概率，给出变点监测的方法，并为M/G/1和GI/M/1模型系统利用率的监测提供了控制限．文献[9]通过CUSUM表监控排队系统M/M/1队列的服务性能，并与几种替代方法进行了对比．考虑到数据的自相关性，文献[10]提出了一种基于加权似然比检验的WLRT控制图，该控制图能有效地监控排队系统的性能指标，尤其是对于M/M/1队列系统利用率的监控．

目前在排队论的研究中，学者们通常把排队系统的性能监控和资源配置优化问题分开考虑．另外，现实中很多排队系统的服务效率主要与服务台本身有关，如超市收银台的服务速率主要与收银员的熟练程度有关[11]．基于以上考虑，本文将系统性能的监控和服务台配置综合考虑，基于Q图研究M(t)/M/C模型服务台优化配置的问题．

1 理论基础

在M(t)/M/C模型中，到达过程服从Poisson分布，但此时到达率不再恒定而是关于时间t的函数．本文采用M/M/C模型和Q图技术对动态M(t)/M/C排队模型到达率的变化进行检测，从而优化服务台的配置问题，下面对符号术语进行简要的介绍．

1.1 M/M/C

本文采用逐段近似的方式优化M(t)/M/C模型的服务台配置问题，通过监测变点对排队系统进行合理的分段，每段近似服从平稳的M/M/C模型，并利用该模型研究相关问题．在M/M/C模型中，顾客的到达速率服从参数为λ的泊松分布，服务时间服从参数为μ的指数分布，服务台的数量为C，等待空间和客源数量为无穷大，服务规则是先到先服务[12]．其中，ρc=λ/(Cμ)表示系统的服务强度，一般来说只有当ρc<1时才能保证系统的平稳运行．W是用来刻画顾客等待时间的参数，其平均值为E(W|W>0)，概率为P(W≤T|W>0)．进一步有

E(W|W>0)=1/[Cμ(1-ρc)]

(1)

P(W≤T|W>0)=1-exp[-CμT(1-ρc)]，T>0

(2)

1.2 Q图

传统控制图通常只能监测服从标准正态分布的数据，对于服从泊松过程的数据其监测性能较差．文献[13]将Q统计量应用于自适应移动加权平均控制图中，将参数值进行标准化处理，对常规控制方法进行了改进．文献[14]也对Q图进行了性能的改进，在绘制泊松属性图的工作中采用了近似标准化的控制图，通过泊松分布进行变换，使数据近似标准化，并给出检测泊松参数的Q图技术．因此，本文采用改进后的Q图来检测排队系统到达速率的变化．

2 模型

在M(t)/M/C模型中，顾客的到达服从强度为λ(t)的非齐次Poisson分布．为了对队列的到达速率进行实时监测，本文构建了基于Q控制图的监测方法，通过逐段平稳的M(t)/M/C模型对其服务台配置问题进行研究．

2.1 Q统计量

本文首先对到达率λ(ti)进行估计并检测变点，根据检测出的变点时刻将排队队列分为i(i=1，2，…，m)段，每段的时间记为ti，经过ni次观测，顾客的到达速率为λ(ti)，到达速率随着ni的变化记为niλ(ti)．当每段中顾客的到达速率和到达人数均相同时，ni和λ(ti)为常数，即ni=n，λ(ti)=λ0，计算可得每段顾客人数的均值为nλ0，方差为nλ0，利用传统的3σ控制图构造上下控制限，则

每段所需观测的最小样本数如下所示：

(3)

当λ(ti)随时间ti变化时，上下控制限的误差增大，控制图的灵敏度降低．为了提高控制图的检测性能，本文将服从泊松分布的顾客数量的观测值xi转化为可以在标准化正态Q图上绘制的值，Xi是不同时段所有顾客数量的观测值xi的和，即Xi=x1+x2+…+xi，Ni是整个系统的总观测次数，ni是该时段观测的总次数，即Ni=n1+n2+…+ni．将x1，x2，…，xi转化为Q统计量，通过下式给出相应的变换：

Qi=φ-1(γi)，其中γi=B(xi；Xi；ni/Ni)

(4)

2.2 服务台配置优化算法

本文利用逐段平稳方法研究M(t)/M/C模型的服务台配置优化问题．利用Q图检测到达速率λ的变化，将发生变点的时刻记为t1，在t1处对到达过程进行分段处理，并分别估计出每段的到达速率λ1和λ2的值．若估计得到的λ2和λ1相等，则说明产生了误报，此时是一个伪检验，不需要采取任何措施； 若得到的λ2与λ1相差较大，表明到达速率λ发生了变化，收到报警信号后，通过到达率λ2与λ1构造新的到达率λ的值，根据平稳模型对服务台的数量进行调整，从而优化系统中顾客的拥堵程度和等待时间．

具体算法如下：

① 利用Q图检测整个排队过程中到达率的变点，得到发生变点的时刻t1和到达率的估计值λ1；

② 基于到达率λ1和给定的延迟概率α，利用M/M/C模型的相关性质，计算服务台的数量C，即

P(W≤T|W>0)=1-exp[-CμT(1-ρc)]≤α，T>0

(5)

通过上式可知，服务台数量C满足

C≤λ/μ-ln(1-α)/(μT)

(6)

③ 在时刻t1之后，基于到达率的估计值λ2，若λ1=λ2，则将检测下一个变点，若λ1≠λ2，则重复步骤②计算该段服务台的最优配置；

④ 重复上面的步骤，直至周期结束．

3 模拟实验

本节设计了随机模拟实验证明该模型的理论优势．首先选取i个样本观测值，对λ设定不同的参数来模拟Q图的监测过程．本文共选取了48个样本点，即i=1，2，…，48．根据式(3)计算得到样本的最小值为4，因此，可将前40个样本观测值每个节点的观测次数ni=4，后8个样本观测值的每个节点的观测次数ni=5．到达速率初始值设为λ1=1.7，λ2=3.4，服务速率设为μ1=μ2=1．假定i=39时，到达速率λ发生变化，即前39个观测点服从λ1=1.7的泊松分布，后9个观测点服从λ2=3.4的泊松分布．模拟得到系统中每个节点的观测次数ni和人数xi的取值如表1所示．

表1 模拟数据

经计算可得

Xi=x1+x2+…+x48=420Ni=n1+n2+…+n48=200

通过式(4)，计算得到的Q分位数结果如表2所示．

表2 Q分位数

在Q控制图中描绘出各模拟点的值，从图1可以看出不同点对应的Q分位数的波动．其中，第39个点对应的分位数超出了控制限[-3，3]的范围，系统发出警报，表明该控制图检测出了λ的变化．

图1 模拟数据的Q控制图

由于式(4)中的二项分布是泊松分布的最小方差无偏估计[14]，因此可以用二项分布的概率pi=ni/Ni来估计到达速率λi，得到λ1=1.756 998，λ2=3.358 514．其中，估计得到的λ1和λ2相差较大，说明没有发生误报．第39个样本点是发生变化的点，根据逐段平稳的性质对系统进行分段处理，将前38个样本观测点规划到前一个节点内，后10个样本观测点规划到后一个节点内，得到权重ω1和ω2的值．

因此，根据优化后模型的权重计算到达速率λ的值为

λ=ω1λ1+ω2λ2=2.090 647

通过算术平均计算得到的到达率λ′的值为

λ′=(λ1+λ2)/2=2.557 756

基于Green等标准的服务水平优化目标[15]，本文设置延迟概率不超过80%，即α=0.8，可以得到等待时间小于T的概率，

P(W≤T|W>0)≤0.8

为了使顾客的等待时间相对较少，令T=10/60=1/6，由此计算出满足此条件的服务台数量为C≤11.74，这里服务台个数取整为12．由式(1)可以得出排队系统中每一位顾客的平均等待时间为W=0.100 9．同理根据λ′计算得出其服务台数量和等待时间分别为C′≤12.21，W′=0.105 9，服务台个数取整为12．为了能够合理地分配总的服务台个数，根据系统的逐段平稳性质得到第一个节点和第二个节点所需要的服务台数量为

通过模拟，根据C1和C2的取值，可以更加合理地安排不同时段的服务台数量，第一段安排服务台数量为11，等待时间W1=0.097 6，第二段安排服务台数量为13，等待时间W2=0.093 9．

2种模型计算的结果如表3所示．

表3 模拟结果对比表

对比这2种模型所需服务台的数量和顾客的等待时间，研究发现优化之后的模型更加实用，主要体现在以下2个方面：

① 从顾客角度来说，优化之后的模型可以减少每一位顾客的等待时间，进而可以提高顾客的满意度．

② 从资源利用的角度来说，优化后的模型能够根据顾客到达率的变化合理安排服务台的个数，可以更为有效地利用服务资源，完成资源的优化配置．

4 实证分析

本文选取与现实生活密切相关的高速公路人工收费车道问题进行实证分析．随着车辆的不断增加，高速公路收费站处会出现到达车辆不能及时得到服务的状况，为了解决车辆排队的拥堵现象，文献[16-17]分别采用M/M/N和M/G/K模型系统描述收费站的排队情况．本文以山东省某收费站为例，利用上述模型对车流量进行监测，并合理安排人工收费车道的数量．该收费站共有8个服务台，3条ETC通道，5条人工通道，由于ETC通道全天候开放，故只对人工通道的车流量进行观测并记录，其中工作人员实行三班轮换制，即每8 h换班一次．由于每周的车流量数据具有一定的周期性，因此每周只选取一天进行观测，连续观测6周，于每周三6：00-21：00每15 min记录一次观测值，发现同一时段的观测值相差不大，随机选取收费站某天的车流量数据进行实证分析．

各时段车流量数据共计60个观测值，其分布直方图如图2所示．为了对各时段车流量数据的分布进行研究，采用K-S检验法，由图2可知P值为0.058，因此该数据近似服从泊松分布．其中前40个观测值的ni=4，后20个观测值的ni=5，μ≈50辆/h，T=1/6 h，车流量的Q图如图3所示．

利用Q图对数据进行监测，图3表明当第1、第3和第36个点超出控制限时，系统发生报警．由于开始时系统的不平稳特征[18]，我们排除第1和第3个点的干扰，即无需改变人工收费站的数量．因此以第36个点作为变点进行分段处理，由极大似然估计可得λ1=165辆/h，λ2=233辆/h，经计算可得，C=5，W≈0.018 h，λ=193辆/h，λ′=199辆/h，C1=4，C2=5．该模型的计算结果表明，在变点之前安排4个人工收费车道，在变点之后安排5个人工收费车道，相比较于收费站全天候开放5个人工收费车道，优化之后的模型可以及时调整人工收费车道的开放个数，从而能够降低人工费用等各项支出．

图2 车流量分布与K-S检验图

图3 车流量的Q控制图

5 结论

本文基于Q控制图对到达速率λ的动态变化进行监控，通过控制图找到异常点，根据变点时刻分段，得到逐段平稳的排队列，利用M(t)/M/C模型的相关理论知识计算出服务台的数量和等待时间，合理地安排服务台数量．此方法的优点是将变点检测和逐段平稳相结合，从而优化了动态排队模型的服务台配置问题．本文利用收费站某天的车流量数据进行了实证分析，结果表明，Q控制图能够对动态的车流量数据进行实时监测，检测出车流量变化幅度较大的点．根据变点计算出各段的人工收费车道数量，进而实时调整服务资源，缓解收费站的拥堵情况，降低收费站人工成本等各类的支出，具有重要的现实意义．