高琦，宮麗芳，武艷華，戴洪帥

山東財經(jīng)大學(xué) 統(tǒng)計學(xué)院，濟南 250000

排隊系統(tǒng)的研究大體可分為3個方面：① 性能分析； ② 統(tǒng)計推斷； ③ 資源配置[1]．在排隊模型的研究中，目前學(xué)者們通常假設(shè)顧客的到達率是不變的，具有平穩(wěn)性．但在很多情況下，如醫(yī)院急診室[2]，顧客的到達具有時變的特征，文獻[3]指出若到達率只是偶爾非平穩(wěn)，利用平穩(wěn)排隊模型分析系統(tǒng)的性能指標，得到的效果并不是最優(yōu)的．文獻[4]指出即使到達率只是適度的不平穩(wěn)，若利用平穩(wěn)排隊模型擬合系統(tǒng)，也會造成性能指標的嚴重低估，因此，逐段近似的方法成為研究非平穩(wěn)排隊模型的一類重要方法．最近幾十年，具有時變到達率的排隊模型的資源配置問題成為學(xué)者們的研究熱點之一．文獻[5]研究了非平穩(wěn)到達過程的一般模型，使用平方根公式建立了服務(wù)臺配置算法．文獻[6]根據(jù)改進的遺傳算法建立了有關(guān)立體車庫的排隊模型，該模型可以緩解城市交通的壓力，從而可以提升立體車庫的服務(wù)率．文獻[7]為了實現(xiàn)資源利用效率的最大化，提出了以能量最小化為基礎(chǔ)的虛擬機簇分配方法．

近年來，排隊模型的統(tǒng)計控制問題引起了學(xué)者們的廣泛關(guān)注．文獻[8]通過轉(zhuǎn)移概率，給出變點監(jiān)測的方法，并為M/G/1和GI/M/1模型系統(tǒng)利用率的監(jiān)測提供了控制限．文獻[9]通過CUSUM表監(jiān)控排隊系統(tǒng)M/M/1隊列的服務(wù)性能，并與幾種替代方法進行了對比．考慮到數(shù)據(jù)的自相關(guān)性，文獻[10]提出了一種基于加權(quán)似然比檢驗的WLRT控制圖，該控制圖能有效地監(jiān)控排隊系統(tǒng)的性能指標，尤其是對于M/M/1隊列系統(tǒng)利用率的監(jiān)控．

目前在排隊論的研究中，學(xué)者們通常把排隊系統(tǒng)的性能監(jiān)控和資源配置優(yōu)化問題分開考慮．另外，現(xiàn)實中很多排隊系統(tǒng)的服務(wù)效率主要與服務(wù)臺本身有關(guān)，如超市收銀臺的服務(wù)速率主要與收銀員的熟練程度有關(guān)[11]．基于以上考慮，本文將系統(tǒng)性能的監(jiān)控和服務(wù)臺配置綜合考慮，基于Q圖研究M(t)/M/C模型服務(wù)臺優(yōu)化配置的問題．

1 理論基礎(chǔ)

在M(t)/M/C模型中，到達過程服從Poisson分布，但此時到達率不再恒定而是關(guān)于時間t的函數(shù)．本文采用M/M/C模型和Q圖技術(shù)對動態(tài)M(t)/M/C排隊模型到達率的變化進行檢測，從而優(yōu)化服務(wù)臺的配置問題，下面對符號術(shù)語進行簡要的介紹．

1.1 M/M/C

本文采用逐段近似的方式優(yōu)化M(t)/M/C模型的服務(wù)臺配置問題，通過監(jiān)測變點對排隊系統(tǒng)進行合理的分段，每段近似服從平穩(wěn)的M/M/C模型，并利用該模型研究相關(guān)問題．在M/M/C模型中，顧客的到達速率服從參數(shù)為λ的泊松分布，服務(wù)時間服從參數(shù)為μ的指數(shù)分布，服務(wù)臺的數(shù)量為C，等待空間和客源數(shù)量為無窮大，服務(wù)規(guī)則是先到先服務(wù)[12]．其中，ρc=λ/(Cμ)表示系統(tǒng)的服務(wù)強度，一般來說只有當ρc<1時才能保證系統(tǒng)的平穩(wěn)運行．W是用來刻畫顧客等待時間的參數(shù)，其平均值為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圖

傳統(tǒng)控制圖通常只能監(jiān)測服從標準正態(tài)分布的數(shù)據(jù)，對于服從泊松過程的數(shù)據(jù)其監(jiān)測性能較差．文獻[13]將Q統(tǒng)計量應(yīng)用于自適應(yīng)移動加權(quán)平均控制圖中，將參數(shù)值進行標準化處理，對常規(guī)控制方法進行了改進．文獻[14]也對Q圖進行了性能的改進，在繪制泊松屬性圖的工作中采用了近似標準化的控制圖，通過泊松分布進行變換，使數(shù)據(jù)近似標準化，并給出檢測泊松參數(shù)的Q圖技術(shù)．因此，本文采用改進后的Q圖來檢測排隊系統(tǒng)到達速率的變化．

2 模型

在M(t)/M/C模型中，顧客的到達服從強度為λ(t)的非齊次Poisson分布．為了對隊列的到達速率進行實時監(jiān)測，本文構(gòu)建了基于Q控制圖的監(jiān)測方法，通過逐段平穩(wěn)的M(t)/M/C模型對其服務(wù)臺配置問題進行研究．

2.1 Q統(tǒng)計量

本文首先對到達率λ(ti)進行估計并檢測變點，根據(jù)檢測出的變點時刻將排隊隊列分為i(i=1，2，…，m)段，每段的時間記為ti，經(jīng)過ni次觀測，顧客的到達速率為λ(ti)，到達速率隨著ni的變化記為niλ(ti)．當每段中顧客的到達速率和到達人數(shù)均相同時，ni和λ(ti)為常數(shù)，即ni=n，λ(ti)=λ0，計算可得每段顧客人數(shù)的均值為nλ0，方差為nλ0，利用傳統(tǒng)的3σ控制圖構(gòu)造上下控制限，則

每段所需觀測的最小樣本數(shù)如下所示：

(3)

當λ(ti)隨時間ti變化時，上下控制限的誤差增大，控制圖的靈敏度降低．為了提高控制圖的檢測性能，本文將服從泊松分布的顧客數(shù)量的觀測值xi轉(zhuǎn)化為可以在標準化正態(tài)Q圖上繪制的值，Xi是不同時段所有顧客數(shù)量的觀測值xi的和，即Xi=x1+x2+…+xi，Ni是整個系統(tǒng)的總觀測次數(shù)，ni是該時段觀測的總次數(shù)，即Ni=n1+n2+…+ni．將x1，x2，…，xi轉(zhuǎn)化為Q統(tǒng)計量，通過下式給出相應(yīng)的變換：

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

(4)

2.2 服務(wù)臺配置優(yōu)化算法

本文利用逐段平穩(wěn)方法研究M(t)/M/C模型的服務(wù)臺配置優(yōu)化問題．利用Q圖檢測到達速率λ的變化，將發(fā)生變點的時刻記為t1，在t1處對到達過程進行分段處理，并分別估計出每段的到達速率λ1和λ2的值．若估計得到的λ2和λ1相等，則說明產(chǎn)生了誤報，此時是一個偽檢驗，不需要采取任何措施； 若得到的λ2與λ1相差較大，表明到達速率λ發(fā)生了變化，收到報警信號后，通過到達率λ2與λ1構(gòu)造新的到達率λ的值，根據(jù)平穩(wěn)模型對服務(wù)臺的數(shù)量進行調(diào)整，從而優(yōu)化系統(tǒng)中顧客的擁堵程度和等待時間．

具體算法如下：

① 利用Q圖檢測整個排隊過程中到達率的變點，得到發(fā)生變點的時刻t1和到達率的估計值λ1；

② 基于到達率λ1和給定的延遲概率α，利用M/M/C模型的相關(guān)性質(zhì)，計算服務(wù)臺的數(shù)量C，即

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

(5)

通過上式可知，服務(wù)臺數(shù)量C滿足

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

(6)

③ 在時刻t1之后，基于到達率的估計值λ2，若λ1=λ2，則將檢測下一個變點，若λ1≠λ2，則重復(fù)步驟②計算該段服務(wù)臺的最優(yōu)配置；

④ 重復(fù)上面的步驟，直至周期結(jié)束．

3 模擬實驗

本節(jié)設(shè)計了隨機模擬實驗證明該模型的理論優(yōu)勢．首先選取i個樣本觀測值，對λ設(shè)定不同的參數(shù)來模擬Q圖的監(jiān)測過程．本文共選取了48個樣本點，即i=1，2，…，48．根據(jù)式(3)計算得到樣本的最小值為4，因此，可將前40個樣本觀測值每個節(jié)點的觀測次數(shù)ni=4，后8個樣本觀測值的每個節(jié)點的觀測次數(shù)ni=5．到達速率初始值設(shè)為λ1=1.7，λ2=3.4，服務(wù)速率設(shè)為μ1=μ2=1．假定i=39時，到達速率λ發(fā)生變化，即前39個觀測點服從λ1=1.7的泊松分布，后9個觀測點服從λ2=3.4的泊松分布．模擬得到系統(tǒng)中每個節(jié)點的觀測次數(shù)ni和人數(shù)xi的取值如表1所示．

表1 模擬數(shù)據(jù)

經(jīng)計算可得

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

通過式(4)，計算得到的Q分位數(shù)結(jié)果如表2所示．

表2 Q分位數(shù)

在Q控制圖中描繪出各模擬點的值，從圖1可以看出不同點對應(yīng)的Q分位數(shù)的波動．其中，第39個點對應(yīng)的分位數(shù)超出了控制限[-3，3]的范圍，系統(tǒng)發(fā)出警報，表明該控制圖檢測出了λ的變化．

圖1 模擬數(shù)據(jù)的Q控制圖

由于式(4)中的二項分布是泊松分布的最小方差無偏估計[14]，因此可以用二項分布的概率pi=ni/Ni來估計到達速率λi，得到λ1=1.756 998，λ2=3.358 514．其中，估計得到的λ1和λ2相差較大，說明沒有發(fā)生誤報．第39個樣本點是發(fā)生變化的點，根據(jù)逐段平穩(wěn)的性質(zhì)對系統(tǒng)進行分段處理，將前38個樣本觀測點規(guī)劃到前一個節(jié)點內(nèi)，后10個樣本觀測點規(guī)劃到后一個節(jié)點內(nèi)，得到權(quán)重ω1和ω2的值．

因此，根據(jù)優(yōu)化后模型的權(quán)重計算到達速率λ的值為

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

通過算術(shù)平均計算得到的到達率λ′的值為

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

基于Green等標準的服務(wù)水平優(yōu)化目標[15]，本文設(shè)置延遲概率不超過80%，即α=0.8，可以得到等待時間小于T的概率，

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

為了使顧客的等待時間相對較少，令T=10/60=1/6，由此計算出滿足此條件的服務(wù)臺數(shù)量為C≤11.74，這里服務(wù)臺個數(shù)取整為12．由式(1)可以得出排隊系統(tǒng)中每一位顧客的平均等待時間為W=0.100 9．同理根據(jù)λ′計算得出其服務(wù)臺數(shù)量和等待時間分別為C′≤12.21，W′=0.105 9，服務(wù)臺個數(shù)取整為12．為了能夠合理地分配總的服務(wù)臺個數(shù)，根據(jù)系統(tǒng)的逐段平穩(wěn)性質(zhì)得到第一個節(jié)點和第二個節(jié)點所需要的服務(wù)臺數(shù)量為

通過模擬，根據(jù)C1和C2的取值，可以更加合理地安排不同時段的服務(wù)臺數(shù)量，第一段安排服務(wù)臺數(shù)量為11，等待時間W1=0.097 6，第二段安排服務(wù)臺數(shù)量為13，等待時間W2=0.093 9．

2種模型計算的結(jié)果如表3所示．

表3 模擬結(jié)果對比表

對比這2種模型所需服務(wù)臺的數(shù)量和顧客的等待時間，研究發(fā)現(xiàn)優(yōu)化之后的模型更加實用，主要體現(xiàn)在以下2個方面：

① 從顧客角度來說，優(yōu)化之后的模型可以減少每一位顧客的等待時間，進而可以提高顧客的滿意度．

② 從資源利用的角度來說，優(yōu)化后的模型能夠根據(jù)顧客到達率的變化合理安排服務(wù)臺的個數(shù)，可以更為有效地利用服務(wù)資源，完成資源的優(yōu)化配置．

4 實證分析

本文選取與現(xiàn)實生活密切相關(guān)的高速公路人工收費車道問題進行實證分析．隨著車輛的不斷增加，高速公路收費站處會出現(xiàn)到達車輛不能及時得到服務(wù)的狀況，為了解決車輛排隊的擁堵現(xiàn)象，文獻[16-17]分別采用M/M/N和M/G/K模型系統(tǒng)描述收費站的排隊情況．本文以山東省某收費站為例，利用上述模型對車流量進行監(jiān)測，并合理安排人工收費車道的數(shù)量．該收費站共有8個服務(wù)臺，3條ETC通道，5條人工通道，由于ETC通道全天候開放，故只對人工通道的車流量進行觀測并記錄，其中工作人員實行三班輪換制，即每8 h換班一次．由于每周的車流量數(shù)據(jù)具有一定的周期性，因此每周只選取一天進行觀測，連續(xù)觀測6周，于每周三6：00-21：00每15 min記錄一次觀測值，發(fā)現(xiàn)同一時段的觀測值相差不大，隨機選取收費站某天的車流量數(shù)據(jù)進行實證分析．

各時段車流量數(shù)據(jù)共計60個觀測值，其分布直方圖如圖2所示．為了對各時段車流量數(shù)據(jù)的分布進行研究，采用K-S檢驗法，由圖2可知P值為0.058，因此該數(shù)據(jù)近似服從泊松分布．其中前40個觀測值的ni=4，后20個觀測值的ni=5，μ≈50輛/h，T=1/6 h，車流量的Q圖如圖3所示．

利用Q圖對數(shù)據(jù)進行監(jiān)測，圖3表明當?shù)?、第3和第36個點超出控制限時，系統(tǒng)發(fā)生報警．由于開始時系統(tǒng)的不平穩(wěn)特征[18]，我們排除第1和第3個點的干擾，即無需改變?nèi)斯な召M站的數(shù)量．因此以第36個點作為變點進行分段處理，由極大似然估計可得λ1=165輛/h，λ2=233輛/h，經(jīng)計算可得，C=5，W≈0.018 h，λ=193輛/h，λ′=199輛/h，C1=4，C2=5．該模型的計算結(jié)果表明，在變點之前安排4個人工收費車道，在變點之后安排5個人工收費車道，相比較于收費站全天候開放5個人工收費車道，優(yōu)化之后的模型可以及時調(diào)整人工收費車道的開放個數(shù)，從而能夠降低人工費用等各項支出．

圖2 車流量分布與K-S檢驗圖

圖3 車流量的Q控制圖

5 結(jié)論

本文基于Q控制圖對到達速率λ的動態(tài)變化進行監(jiān)控，通過控制圖找到異常點，根據(jù)變點時刻分段，得到逐段平穩(wěn)的排隊列，利用M(t)/M/C模型的相關(guān)理論知識計算出服務(wù)臺的數(shù)量和等待時間，合理地安排服務(wù)臺數(shù)量．此方法的優(yōu)點是將變點檢測和逐段平穩(wěn)相結(jié)合，從而優(yōu)化了動態(tài)排隊模型的服務(wù)臺配置問題．本文利用收費站某天的車流量數(shù)據(jù)進行了實證分析，結(jié)果表明，Q控制圖能夠?qū)討B(tài)的車流量數(shù)據(jù)進行實時監(jiān)測，檢測出車流量變化幅度較大的點．根據(jù)變點計算出各段的人工收費車道數(shù)量，進而實時調(diào)整服務(wù)資源，緩解收費站的擁堵情況，降低收費站人工成本等各類的支出，具有重要的現(xiàn)實意義．