【大學(xué)】QuickPass系統(tǒng)排隊問題

1、.常常是件很令人惱火的事情尤其是在我們這樣的人口大國v電話亭1978年在北京15%的電話要在1小時后才能接通。在電報大樓打電話的人還要帶著午飯去排隊 v銀行窗口，ATMv醫(yī)院、理發(fā)、火車售票v游樂場的游樂項目?.v在游樂園中的頻頻排隊會極為掃興vDisneyLand中的FastPass(QuickPass)系統(tǒng)就是想解決這個問題的.What is QuickPass?v工作原理：v到達(dá)的顧客將自己的票插入FastPass的slot中vFastPass計算出建議顧客返回的時間間隔（time interval）或時間點或時間窗（time window）1.顧客無需排隊，在指定的時間返回就可持票進(jìn)入

2、.怎樣縮短排隊的等待時間？v銀行的排隊叫號機(jī) 只是有序的組織了顧客，并沒有減少等待時間v如果能實現(xiàn)知道輪到自己需要等待多少時間，再選擇合適的時間來，豈不很好？.FastPass存在的問題：v預(yù)知的返回時間間隔存在誤差按時返回卻仍需要排隊v建議的返回時間間隔太長如果告訴你4小時以后再回來呢？v顧客可能不會完全按照安排的時間返回v如果新來的顧客不想使用FastPass系統(tǒng)？現(xiàn)有的Fast Pass真的那么好用嗎？.我們的目的就是對FastPass系統(tǒng)建立合理的離散統(tǒng)計模型（Distributed Statistical Model），求出最優(yōu)的顧客返回時間。 建模的一般步驟以及：* 模型的改進(jìn)*

3、啟發(fā)與待解決的問題.1 模型的假設(shè)v游樂園開放時間為8:00-18:00,一天中不同時間的顧客流量不同，比如上午10:00和下午3:00的顧客流量是最大的。v顧客的到達(dá)時間符合非時間齊次泊松過程(Nonhomogeneous Possion Process)，到達(dá)速率是 （t）.Poisson Processiii( ( ) ),0,1,2.!ktt tekk整數(shù)值的隨機(jī)過程N(t),t0是強度為 的Poisson過程，如果（i）N(0)=0,(ii)N(t)是獨立增量過程，（） t0,s0,PN(s+t)-N(t)=k=.Poisson Processexp()ititi顧客到達(dá)時間間隔（t

4、）exp( (t)t)T顧客 接受服務(wù)的時間（t）和 的確定都將在后面仿真的部分給出. 分析1：能否得到準(zhǔn)確的返回時間？ (1. ),1immii1,m+1ii1,m+1如果能夠準(zhǔn)確得知前面所有顧客的到達(dá)時間間隔t 和接受服務(wù)的時間T當(dāng)然可以知道第個顧客到達(dá)就可以馬上接受服務(wù)的時間隔t.可現(xiàn)在t 和T都是隨機(jī)變量，我們只能用隨機(jī)過程的方法，求出t期望值。 2 在我們開始動手建模之前，先要問幾個問題：. 分析2：使用FastPass后排隊是不是可以避免的？vFastPass給出的返回時間只是期望值，而非確定值v假設(shè)所有的顧客都使用FastPass,但需考慮有的顧客可能會不遵守FastPass給出

5、的返回時間 2 在我們開始動手建模之前，先要問幾個問題：FastPass2,m+1結(jié)論：使用后顧客仍需排隊，但是排隊的時間會大大減少。并設(shè)第m+1個顧客排隊的時間是t. 分析3：我們優(yōu)化的目標(biāo)函數(shù)（或cost function）是什么？是排隊時間嗎？ 2 在我們開始動手建模之前，先要問幾個問題：1.FastPass1,iw2,i給 出 的 顧 客 i的 等 待 時 間 t太 長 ,同 樣 會 引來 抱 怨 ,并 且 不 能 超 過 公 園 的 開 放 時 間 T2.排 隊 的 時 間 t也 要 考 慮但 是 后 者 引 來 的 抱 怨 更 大 ； 而 且 等 待 的 時 間 越 長 ， 抱怨

6、越 多 .結(jié) 論 ： 目 標(biāo) 函 數(shù) 應(yīng) 該 是 兩 者 的 時 變 加 權(quán) 和 （ time-variantweighted average）. 優(yōu)化問題的目標(biāo)函數(shù)為： 11221,11,11,1min ( )( ) . .ijiwjiiiwzE Uc t tc t tttTs ttttT公園一天的開放時間3 模型的建立（1）目標(biāo)函數(shù). 3 模型的建立（1）目標(biāo)函數(shù).v根據(jù)排隊論（queueing theory）的分類規(guī)則,（X/Y/Z/A）代表一類排隊的規(guī)則，其中 X:顧客流到達(dá)所符合的分布 Y:顧客接受服務(wù)的時間所服從的分布 a Z:服務(wù)臺的個數(shù) A:服務(wù)臺一次可服務(wù)的顧客數(shù)量（系統(tǒng)的容

7、量）v針對各個游樂項目的特點，我們主要討論兩種排隊系統(tǒng):模型的建立（2） 排隊模型的分類/1/ / %M MM M c ac電話亭（phonebooth）的隊列模型和過山車（scenic railway）的隊列模型.v特點：系統(tǒng)容量為1，顧客的到達(dá)是Poisson流，服務(wù)時間服從指數(shù)分布，只有一條隊列模型的建立（3） 電話亭模型.v加入QuickPass系統(tǒng)以后的Poisson排隊模型模型的建立（3）電話亭模型.v求出這類系統(tǒng)的代價函數(shù)表達(dá)式模型的建立（3）電話亭模型12,( , )1()*nn kkini ktEPA *,0;( )0,0.x xxx1,1nnnnjkiAttEP第n個顧客的

8、返回時間：是第k個顧客可以接受服務(wù)的時刻是隊列中的顧客i仍會停留的時間（包括使用系統(tǒng)的時間）.v近似將總的優(yōu)化目標(biāo)函數(shù)等效為對顧客i的目標(biāo)函數(shù)：模型的建立（3）電話亭模型11,22,111,2,2,( , )0,min ( )( )min()nnnnnn kn kkn kzE Uc t tc t tc E tcQ tQP nk其中，顧客前有 個顧客在排隊.,111, 2212,1111111,1 ,1 ,1 ,1,11()(.),(1),(), (0 )kkknkkkknkskskksnkkkkkkkkkkkikikikikkkiniQPEPAQPEPPAQPEPPAAAEPEEPAEPQQQ

9、QQPAE下 面 求 出 狀 態(tài) 轉(zhuǎn) 換 平 衡 狀 態(tài) 方 程 ：）且模型的建立（3）電話亭模型.v如果簡化c1,c2為常數(shù)，并計算第二個人的無需等待返回時間的期望值，得v用MatLab能夠作出 的函數(shù)，并從圖中得出結(jié)果模型的求解（4）電話亭模型21 1,22121,221,2()(1()Uc tcPttN tt22wTtT0( )1,0 xtxtN xedtex 21,2()Ut.模型的求解（4）電話亭模型Average call time(min*10) U2 t2508.051617.08023.051632.5.v第三個人的無需等待返回時間的期望值，同理可以算出，并用圖解法求出模型的

10、求解（4）電話亭模型2,3231,31231,3231,321,231,31,21,2231,321,2231,312231,321,2231,312231,3(1()()()()(1()()(1()(1()()(1()(1()()tN tttPtttN tttN ttN ttttPttN ttG tttPPtttN ttG tttPPttt但是第4個人，第5個人呢？這種方法太繁瑣，似乎不好用可否有近似的算法？.v與前一個模型的區(qū)別在于：系統(tǒng)容量是c1,服務(wù)時間固定，顧客的到達(dá)仍然是Poisson流。服務(wù)系統(tǒng)數(shù)量是1模型的建立（5） 過山車模型.還要考慮：v實際的FastPass 系統(tǒng)有兩條隊

11、列：FastPass 和Standby隊列v不考慮standby隊列，將得到Greedy algorithm模型v考慮standby隊列，將得到效用函數(shù)模型模型的建立（5）過山車.v只有一條隊列，即所有的人都只用FastPass系統(tǒng)v為了防止前面的人等的時間太長，過山車只要載滿一定數(shù)量的人后就開車，假設(shè)為80c。v用貪心算法（greedy algorithm),將每個顧客盡量安排在離顧客到達(dá)時間最近的，且還沒有安排滿人的一班車上。v假設(shè)被安排的顧客按照Beta分布到達(dá)所被安排的時間段內(nèi)模型的建立（5）過山車模型.貪心算法模型的建立（5）過山車模型.v很容易想到，全局優(yōu)化的目標(biāo)變量1. 如果開車

12、的時間不固定，則a%是多少最優(yōu)？就是說顧客坐滿多少就開車？ 2.如果開車的時間間隔是固定的，則多長時間開一次是最優(yōu)的？v衡量的標(biāo)準(zhǔn)：目標(biāo)函數(shù)模型的建立（5）過山車模型.一個區(qū)間內(nèi)的顧客返回示意圖：.目標(biāo)函數(shù)：模型的建立（5）過山車模型121121,1,2,1,2 2,2212121212,.()()()()()()kjjiij kkkkkjkjkjkkkjkkkjjkjkkkkkh hhbbbttzzEc tc tE c tc tcEEtc bEccEc tc bccc tcj-1i2,iii個人被安排在中的一班車設(shè)i個人的返回時間是則t121)()jjkkkbEccc tk常數(shù)， 由 決定，

13、.222%,jjjjkjjcacbc bckb ，如果開車時坐滿的人數(shù)固定如果開車的時間間隔固定則常數(shù)模型的建立（5）過山車模型怎樣求解最優(yōu)的a%c和最優(yōu)的開車間隔？對于這類復(fù)雜的問題，離散仿真是最好的方法了.v仿真：用計算機(jī)生成一些符合某種分布的隨機(jī)數(shù)據(jù)點，模擬離散時間的發(fā)生v這里的仿真用完成：v步驟：1.生成Poisson顧客流（模擬到達(dá)時間） 2.給定不同的a%c, 開車時間間隔不定，計算代價函數(shù)，畫出代價函數(shù)性能曲線 3.開車時間固定，給出不同的開車時間間隔，計算畫出代價函數(shù)性能曲線 4.得出最優(yōu)的結(jié)論模型的仿真（5）過山車模型. 過山車模型的仿真（）得到v在第j天的某一固定時刻 i

14、采集樣本,i=1m,j=1100形成樣本空間的矩陣11121,10021222,100,1,2,100. . . . . .mmmlllllllll( ) t. 過山車模型的仿真（）v 用列向量的均值估計參數(shù)v樣本的更新用時間序列的方法（time serial analysis）,計算列向量的Eucilid距離dthreshold就更新一次( )it,1,2,100,. Tiiimeanlll21()mkkkdll. 對某一個或一組變量x(t)進(jìn)行觀察測量，將在一系列時刻t1, t2, , tn (t為自變量且t1t2 tn ) 所得到的離散數(shù)字組成序列集合x(t1), x(t2), , x(

15、tn)，我們稱之為時間序列，這種有時間意義的序列也稱為動態(tài)數(shù)據(jù)。時間序列分析是根據(jù)系統(tǒng)觀測得到的時間序列數(shù)據(jù)，通過曲線擬合和參數(shù)估計來建立數(shù)學(xué)模型的理論和方法 時間序列分析（time serial analysis）. 過山車模型的仿真（）啟發(fā)：有沒有別的方法判別樣本如何更新？如：求樣本矩陣的秩， 求樣本向量的相關(guān)系數(shù).生成的樣本空間過山車模型的仿真（）實用的一種模擬Poisson流的方法：某個區(qū)間 個顧客到達(dá)時間Uniform( ) t.Poisson流顧客到達(dá)時間過山車模型的仿真（）按照貪心算法指定的顧客乘坐的過山車的班次.兩種a%c的情況下顧客等待時間過山車模型的仿真（）.a%c的性能曲

16、線：可見a%c=70最優(yōu)過山車模型的仿真（）.開車間隔的優(yōu)化：可是cost function是間隔的單調(diào)函數(shù)？怎么辦？過山車模型的仿真（）.解決：考慮開車的成本：開車的時間間隔越短，次數(shù)愈多，運行成本越大找平衡點 最優(yōu)過山車模型的仿真（）123456789100.511.522.53x 104cycle interval: minEcomomic gains of an amusement item: $average delayeconomic gainaverage delay aver.6 模型的穩(wěn)健性與優(yōu)缺點v電話亭模型較精確，雖可行但復(fù)雜v過山車模型的貪心算法，簡單，但不是最優(yōu)（qu

17、asi-optimal）（為什么不是最優(yōu)?）vStandby隊列會有什么影響？v每個人的c1和c2可能不同.v將顧客的到達(dá)看成是顧客流(traffic),用Trunking Theory中的Erlang C公式，能夠得出阻塞概率P(Block)，系統(tǒng)容量C，顧客流的強度A（ ）三者的關(guān)系v平均隊列長度為：v可將顧客安排在一天之內(nèi)平均隊列短的時刻7 過山車模型的改進(jìn) ( ) t10P(_)!(1)!CkCCkAblockedGoS GradeofserviceAAACCk( )PrtlblockedAt.Erlang C的圖形7 過山車模型的改進(jìn).統(tǒng)計得出的隊列長度，以及仿真得出的實際隊列長度說

18、明可以用統(tǒng)計曲線作安排返回時間的依據(jù)7 過山車模型的改進(jìn).7 過山車模型的改進(jìn).7 過山車模型的改進(jìn)但是：可能所有的顧客都被安排到同一個隊列長度短的時段了.如果考慮Standby隊列？7 過山車模型的改進(jìn)使用邊際效用函數(shù)(Marginal Utility Function)的思想：FastPass隊列中每增加一個人，會對Standby隊列中的人造成目標(biāo)函數(shù)的損失.v使用IC卡門票，記錄顧客的特點，數(shù)據(jù)集中在中心數(shù)據(jù)庫v給顧客提供預(yù)計的當(dāng)天實時隊列長度表，顧客可自己選擇返回時間，選擇t1,t2時間的長度v你的更好的辦法？8 將來的工作：設(shè)計更好的FastPass系統(tǒng).v怎樣寫數(shù)學(xué)建模論文？v怎樣求解沒有顯式表達(dá)的式子？v如何模擬離散隨機(jī)時間？v如何通過仿真的結(jié)果求參數(shù)的優(yōu)化使用數(shù)學(xué)軟件，仿真的過程中常常也會的到新的想法與結(jié)論v靈活借鑒其他學(xué)科中的方