【大學(xué)】QuickPass系統(tǒng)排隊(duì)問(wèn)題ppt課件

1、v亭1978年在北京15%的要在1小時(shí)后才干接通。在電報(bào)大樓打的人還要帶著午飯去排隊(duì) v銀行窗口，ATMv醫(yī)院、理發(fā)、火車售票v游樂(lè)場(chǎng)的游樂(lè)工程?v在游樂(lè)園中的頻頻排隊(duì)v會(huì)極為敗興vDisneyLand中v的FastPassv(QuickPass)系統(tǒng)v就是想處理這v個(gè)問(wèn)題的What is QuickPass?v任務(wù)原理：v到達(dá)的顧客將本人的票插入FastPass的slot中vFastPass計(jì)算出建議顧客前往的時(shí)間間隔time interval或時(shí)間點(diǎn)或時(shí)間窗time windowv顧客無(wú)需排隊(duì)，在指定的時(shí)間前往就可持票進(jìn)入怎樣縮短排隊(duì)的等待時(shí)間？v銀行的排隊(duì)叫號(hào)機(jī)v 只是有序的組織了顧客，

2、并沒(méi)有減少等待時(shí)間v假設(shè)能實(shí)現(xiàn)知道輪到本人需求等待多少時(shí)間，再選擇適宜的時(shí)間來(lái)，豈不很好？FastPass存在的問(wèn)題：v預(yù)知的前往時(shí)間間隔存在誤差v按時(shí)前往卻仍需求排隊(duì)v建議的前往時(shí)間間隔太長(zhǎng)v假設(shè)通知他4小時(shí)以后再回來(lái)呢？v顧客能夠不會(huì)完全按照安排的時(shí)間前往v假設(shè)新來(lái)的顧客不想運(yùn)用FastPass系統(tǒng)？現(xiàn)有的Fast Pass真的那么好用嗎？我們的目的就是對(duì)FastPass系統(tǒng)建立合理的離散統(tǒng)計(jì)模型Distributed Statistical Model，求出最優(yōu)的顧客前往時(shí)間。 建模的普通步驟以及：* 模型的改良* 啟發(fā)與待處理的問(wèn)題1 模型的假設(shè)v游樂(lè)園開放時(shí)間為8:00-18:00,

3、一天中不同時(shí)間的顧客流量不同，比如上午10:00和下午3:00的顧客流量是最大的。v顧客的到達(dá)時(shí)間符合非時(shí)間齊次泊松過(guò)程(Nonhomogeneous Possion Process)，到達(dá)速率是 （t）Poisson Processiii( ( ) ),0,1,2.!ktt tekk整數(shù)值的隨機(jī)過(guò)程N(yùn)(t),t0是強(qiáng)度為 的Poisson過(guò)程，如果（i）N(0)=0,(ii)N(t)是獨(dú)立增量過(guò)程，（） t0,s0,PN(s+t)-N(t)=k=Poisson Processexp()ititi顧客到達(dá)時(shí)間間隔（t）exp( (t)t)T顧客 接受服務(wù)的時(shí)間（t）和 的確定都將在后面仿真的部

4、分給出 分析1：能否得到準(zhǔn)確的前往時(shí)間？ (1. ),1immii1,m+1ii1,m+1如果能夠準(zhǔn)確得知前面所有顧客的到達(dá)時(shí)間間隔t 和接受服務(wù)的時(shí)間T當(dāng)然可以知道第個(gè)顧客到達(dá)就可以馬上接受服務(wù)的時(shí)間隔t.可現(xiàn)在t 和T都是隨機(jī)變量，我們只能用隨機(jī)過(guò)程的方法，求出t期望值。 2 在我們開場(chǎng)動(dòng)手建模之前，先要問(wèn)幾個(gè)問(wèn)題： 分析2：運(yùn)用FastPass后排隊(duì)是不是可以防止的？FastPass給出的前往時(shí)間只是期望值，而非確定值假設(shè)一切的顧客都運(yùn)用FastPass,但需思索有的顧客能夠會(huì)不遵守FastPass給出的前往時(shí)間 2 在我們開場(chǎng)動(dòng)手建模之前，先要問(wèn)幾個(gè)問(wèn)題：FastPass2,m+1結(jié)論

5、：使用后顧客仍需排隊(duì)，但是排隊(duì)的時(shí)間會(huì)大大減少。并設(shè)第m+1個(gè)顧客排隊(duì)的時(shí)間是t 分析3：我們優(yōu)化的目的函數(shù)或cost function是什么？是排隊(duì)時(shí)間嗎？ 2 在我們開場(chǎng)動(dòng)手建模之前，先要問(wèn)幾個(gè)問(wèn)題：1.FastPass1,iw2,i給 出 的 顧 客 i的 等 待 時(shí) 間 t太 長(zhǎng) ,同 樣 會(huì) 引來(lái) 抱 怨 ,并 且 不 能 超 過(guò) 公 園 的 開 放 時(shí) 間 T2.排 隊(duì) 的 時(shí) 間 t也 要 考 慮但 是 后 者 引 來(lái) 的 抱 怨 更 大 ； 而 且 等 待 的 時(shí) 間 越 長(zhǎng) ， 抱怨 越 多 .結(jié) 論 ： 目 標(biāo) 函 數(shù) 應(yīng) 該 是 兩 者 的 時(shí) 變 加 權(quán) 和 （ tim

6、e-variantweighted average） 優(yōu)化問(wèn)題的目的函數(shù)為： 11221,11,11,1min ( )( ) . .ijiwjiiiwzE Uc t tc t tttTs ttttT公園一天的開放時(shí)間3 模型的建立1目的函數(shù) 3 模型的建立1目的函數(shù)v根據(jù)排隊(duì)論queueing theory的分類規(guī)那么,X/Y/Z/A代表一類排隊(duì)的規(guī)那么，其中v X:顧客流到達(dá)所符合的分布 v Y:顧客接受效力的時(shí)間所服從的分布 av Z:效力臺(tái)的個(gè)數(shù) v A:效力臺(tái)一次可效力的顧客數(shù)量系統(tǒng)的容量v針對(duì)各個(gè)游樂(lè)工程的特點(diǎn)，我們主要討論兩種排隊(duì)系統(tǒng):模型的建立2 排隊(duì)模型的分類/1/ / %M

7、MM M c ac電話亭（phonebooth）的隊(duì)列模型和過(guò)山車（scenic railway）的隊(duì)列模型v特點(diǎn)：系統(tǒng)容量為1，顧客的到達(dá)是Poisson流，效力時(shí)間服從指數(shù)分布，只需一條隊(duì)列模型的建立3 亭模型v參與QuickPass系統(tǒng)以后的Poisson排隊(duì)模型模型的建立3亭模型v求出這類系統(tǒng)的代價(jià)函數(shù)表達(dá)式模型的建立3亭模型12,( , )1()*nn kkini ktEPA *,0;( )0,0.x xxx1,1nnnnjkiAttEP第n個(gè)顧客的返回時(shí)間：是第k個(gè)顧客可以接受服務(wù)的時(shí)刻是隊(duì)列中的顧客i仍會(huì)停留的時(shí)間（包括使用系統(tǒng)的時(shí)間）v近似將總的優(yōu)化目的函數(shù)等效為對(duì)顧客i的目的

8、函數(shù)：模型的建立3亭模型11,22,111,2,2,( , )0,min ( )( )min()nnnnnn kn kkn kzE Uc t tc t tc E tcQ tQP nk其中，顧客前有 個(gè)顧客在排隊(duì),111, 2212,1111111,1 ,1 ,1 ,1,11()(.),(1),(), (0 )kkknkkkknkskskksnkkkkkkkkkkkikikikikkkiniQPEPAQPEPPAQPEPPAAAEPEEPAEPQQQQQPAE下 面 求 出 狀 態(tài) 轉(zhuǎn) 換 平 衡 狀 態(tài) 方 程 ：）且模型的建立3亭模型v假設(shè)簡(jiǎn)化c1,c2為常數(shù)，并計(jì)算第二個(gè)人的無(wú)需等待前往時(shí)

9、間的期望值，得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.5v第三個(gè)人的無(wú)需等待前往時(shí)間的期望值，同理可以算出，并用圖解法求出模型的求解4亭模型2,3231,31231,3231,321,231,31,21,2231,321,2231,312231,321,2231,312231,3(1()()()()(1(

10、)()(1()(1()()(1()(1()()tN tttPtttN tttN ttN ttttPttN ttG tttPPtttN ttG tttPPttt但是第4個(gè)人，第5個(gè)人呢？這種方法太繁瑣，似乎不好用可否有近似的算法？v與前一個(gè)模型的區(qū)別在于：系統(tǒng)容量是c1,效力時(shí)間固定，顧客的到達(dá)依然是Poisson流。效力系統(tǒng)數(shù)量是1模型的建立5 過(guò)山車模型還要思索：實(shí)踐的FastPass 系統(tǒng)有兩條隊(duì)列：FastPass 和Standby隊(duì)列不思索standby隊(duì)列，將得到Greedy algorithm模型思索standby隊(duì)列，將得到成效函數(shù)模型模型的建立5過(guò)山車模型的建立5過(guò)山車模型貪婪

11、算法模型的建立5過(guò)山車模型v很容易想到，全局優(yōu)化的目的變量vv1. 假設(shè)開車的時(shí)間不固定，那么a%是多少最優(yōu)？就是說(shuō)顧客坐滿多少就開車？v 2.假設(shè)開車的時(shí)間間隔是固定的，那么多長(zhǎng)時(shí)間開一次是最優(yōu)的？v衡量的規(guī)范：目的函數(shù)模型的建立5過(guò)山車模型一個(gè)區(qū)間內(nèi)的顧客前往表示圖：目的函數(shù)：模型的建立5過(guò)山車模型121121,1,2,1,2 2,2212121212,.()()()()()()kjjiij kkkkkjkjkjkkkjkkkjjkjkkkkkh hhbbbttzzEc tc tE c tc tc EEtc bEcc Ectc bccctcj-1i2,iii個(gè)人被安排在中的一班車設(shè)i個(gè)人的

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

13、型的仿真5過(guò)山車模型 過(guò)山車模型的仿真5.1得到v在第j天的某一固v定時(shí)辰 i 采集樣本,vi=1m,vj=1100v構(gòu)成樣本空間的v矩陣11121,10021222,100,1,2,100. . . . . .mmmlllllllll( ) t 過(guò)山車模型的仿真5.1v 用列向量的均值v估計(jì)參數(shù)v樣本的更新用時(shí)間序列的方法time serial analysis,計(jì)算列向量的Eucilid間隔vdthreshold就更新一次( )it,1,2,100,. Tiiimeanlll21()mkkkdllv 對(duì)某一個(gè)或一組變量x(t)進(jìn)展察看丈量，將在一系列時(shí)辰t1, t2, , tn (t為自變

14、量且t1t2 tn ) 所得到的離散數(shù)字組成序列集合x(t1), x(t2), , x(tn)，我們稱之為時(shí)間序列，這種有時(shí)間意義的序列也稱為動(dòng)態(tài)數(shù)據(jù)。時(shí)間序列分析是根據(jù)系統(tǒng)觀測(cè)得到的時(shí)間序列數(shù)據(jù)，經(jīng)過(guò)曲線擬合和參數(shù)估計(jì)來(lái)建立數(shù)學(xué)模型的實(shí)際和方法 時(shí)間序列分析time serial analysis 過(guò)山車模型的仿真5.1啟發(fā)：有沒(méi)有別的方法判別樣本如何更新？如：求樣本矩陣的秩， 求樣本向量的相關(guān)系數(shù)生成的樣本空間過(guò)山車模型的仿真5.1適用的一種模擬Poisson流的方法：某個(gè)區(qū)間 個(gè)顧客到達(dá)時(shí)間Uniform( ) tPoisson流顧客到達(dá)時(shí)間過(guò)山車模型的仿真5.2按照貪婪算法指定的顧客乘

15、坐的過(guò)山車的班次兩種a%c的情況下顧客等待時(shí)間過(guò)山車模型的仿真5.3a%c的性能曲線：可見a%c=70最優(yōu)過(guò)山車模型的仿真5.3開車間隔的優(yōu)化：可是cost function是間隔的單調(diào)函數(shù)？怎樣辦？過(guò)山車模型的仿真5.4處理：思索開車的本錢：開車的時(shí)間間隔越短，次數(shù)愈多，運(yùn)轉(zhuǎn)本錢越大找平衡點(diǎn) 4.67min最優(yōu)過(guò)山車模型的仿真5.4123456789100.511.522.53x 104cycle interval: minEcomomic gains of an amusement item: $average delayeconomic gainaverage delay aver6 模

16、型的穩(wěn)健性與優(yōu)缺陷v亭模型較準(zhǔn)確，雖可行但復(fù)雜v過(guò)山車模型的貪婪算法，簡(jiǎn)單，但不是最優(yōu)quasi-optimal為什么不是最優(yōu)?vStandby隊(duì)列會(huì)有什么影響？v每個(gè)人的c1和c2能夠不同v將顧客的到達(dá)看成是顧客流(traffic),用Trunking Theory中的Erlang C公式，可以得出阻塞概率P(Block)，系統(tǒng)容量C，顧客流的強(qiáng)度A 三者的關(guān)系v平均隊(duì)列長(zhǎng)度為：v可將顧客安排在一天之內(nèi)平均隊(duì)列短的時(shí)辰7 過(guò)山車模型的改良 ( ) t10P(_)!(1)!CkCCkAblockedGoS GradeofserviceAAACCk( )PrtlblockedAtErlang C

17、的圖形7 過(guò)山車模型的改良統(tǒng)計(jì)得出的隊(duì)列長(zhǎng)度，以及仿真得出的實(shí)踐隊(duì)列長(zhǎng)度闡明可以用統(tǒng)計(jì)曲線作安排前往時(shí)間的根據(jù)7 過(guò)山車模型的改良7 過(guò)山車模型的改良7 過(guò)山車模型的改良但是：能夠一切的顧客都被安排到同一個(gè)隊(duì)列長(zhǎng)度短的時(shí)段了假設(shè)思索Standby隊(duì)列？7 過(guò)山車模型的改良運(yùn)用邊沿成效函數(shù)(Marginal Utility Function)的思想：FastPass隊(duì)列中每添加一個(gè)人，會(huì)對(duì)Standby隊(duì)列中的人呵斥目的函數(shù)的損失v運(yùn)用IC卡門票，記錄顧客的特點(diǎn)，數(shù)據(jù)集中在中心數(shù)據(jù)庫(kù)v給顧客提供估計(jì)的當(dāng)天實(shí)時(shí)隊(duì)列長(zhǎng)度表，顧客可本人選擇前往時(shí)間，選擇t1,t2時(shí)間的長(zhǎng)度v他的更好的方法？8 未來(lái)的任務(wù)：設(shè)計(jì)更好的FastPass系統(tǒng)v怎樣寫數(shù)學(xué)建模論文？v怎樣求解沒(méi)有顯式表達(dá)的式子？v如何模擬離散隨機(jī)時(shí)間？v如何經(jīng)過(guò)仿真的結(jié)果求參數(shù)的優(yōu)化v運(yùn)用數(shù)學(xué)軟件，仿真的過(guò)程中經(jīng)常也會(huì)的到新的想法與結(jié)論v靈敏自創(chuàng)其他學(xué)科中的方法：如Queueing theory(排隊(duì)論), Trunking Theory(復(fù)用論), Greedy Algorithm