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

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

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

3、 返回時(shí)間。 建模的一般步驟 以及： * 模型的改進(jìn) * 啟發(fā)與待解決的問(wèn)題 1 模型的假設(shè) v游樂(lè)園開(kāi)放時(shí)間為8:00-18:00,一天中不同時(shí) 間的顧客流量不同，比方上午10:00和下午 3:00的顧客流量是最大的。 v顧客的到達(dá)時(shí)間符合非時(shí)間齊次泊松過(guò)程 (Nonhomogeneous Possion Process)，到達(dá) 速率是 （t） Poisson Process iii ( ( ) ) ,0,1,2. ! kt t te k k 整數(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

4、+t)-N(t)=k= Poisson Process exp() i t it i 顧客到達(dá)時(shí)間間隔（t）exp( (t)t) T顧客 接受服務(wù)的時(shí)間 （t）和 的確定都將在后面仿真的 部分給出 分析1：能否得到準(zhǔn)確的返回時(shí)間？ (1. ), 1 im m ii 1,m+1ii 1,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 在我們開(kāi)始動(dòng)手建模之前， 先要問(wèn)幾個(gè)問(wèn)題： 分析2：使用FastPass后排隊(duì)是不是可以防止的？ Fast

5、Pass給出的返回時(shí)間只是期望值，而非確定值 假設(shè)所有的顧客都使用FastPass,但需考慮有的顧客可 能會(huì)不遵守FastPass給出的返回時(shí)間 2 在我們開(kāi)始動(dòng)手建模之前， 先要問(wèn)幾個(gè)問(wèn)題： FastPass 2,m+1 結(jié)論：使用后顧客仍需排隊(duì)，但是排隊(duì)的時(shí)間會(huì)大大減少。 并設(shè)第m+1個(gè)顧客排隊(duì)的時(shí)間是t 分析3：我們優(yōu)化的目標(biāo)函數(shù)或cost function是什么？是排隊(duì)時(shí)間嗎？ 2 在我們開(kāi)始動(dòng)手建模之前， 先要問(wèn)幾個(gè)問(wèn)題： 1.FastPass 1,i w 2,i 給 出 的 顧 客 i的 等 待 時(shí) 間 t太 長(zhǎng) ,同 樣 會(huì) 引 來(lái) 抱 怨 ,并 且 不 能 超 過(guò) 公 園 的

6、開(kāi) 放 時(shí) 間 T 2.排 隊(duì) 的 時(shí) 間 t也 要 考 慮 但 是 后 者 引 來(lái) 的 抱 怨 更 大 ； 而 且 等 待 的 時(shí) 間 越 長(zhǎng) ， 抱 怨 越 多 . 結(jié) 論 ： 目 標(biāo) 函 數(shù) 應(yīng) 該 是 兩 者 的 時(shí) 變 加 權(quán) 和 （ time-variant weighted average） 優(yōu)化問(wèn)題的目標(biāo)函數(shù)為： 1122 1, 1 1,11,1 min ( )( ) . . i jiw j iii w zE Uc t tc t t ttT s t ttt T 公園一天的開(kāi)放時(shí)間 3 模型的建立1目標(biāo)函數(shù) 3 模型的建立1目標(biāo)函數(shù) v根據(jù)排隊(duì)論queueing theory的分

7、類(lèi)規(guī)那么,X/Y/Z/A 代表一類(lèi)排隊(duì)的規(guī)那么，其中 v X:顧客流到達(dá)所符合的分布 v Y:顧客接受效勞的時(shí)間所服從的分布 a v Z:效勞臺(tái)的個(gè)數(shù) v A:效勞臺(tái)一次可效勞的顧客數(shù)量系統(tǒng)的容量 v針對(duì)各個(gè)游樂(lè)工程的特點(diǎn)，我們主要討論兩種排隊(duì)系統(tǒng): 模型的建立2 排隊(duì)模型的分類(lèi) /1/ / / % M M M M c ac 電話(huà)亭（phonebooth）的隊(duì)列模型和 過(guò)山車(chē)（scenic railway）的隊(duì)列模型 v特點(diǎn)：系統(tǒng)容量為1，顧客的到達(dá)是Poisson流，效 勞時(shí)間服從指數(shù)分布，只有一條隊(duì)列 模型的建立3 亭模型 v參加QuickPass系統(tǒng)以后的Poisson排隊(duì)模型 模型的建

8、立3 亭模型 v求出這類(lèi)系統(tǒng)的代價(jià)函數(shù)表達(dá)式 模型的建立3 亭模型 1 2,( , ) 1 ()* n n kkin i k tEPA * ,0; ( ) 0,0. x x x x 1, 1 n n nn j k i Att E P 第n個(gè)顧客的返回時(shí)間： 是第k個(gè)顧客可以接受服務(wù)的時(shí)刻 是隊(duì)列中的顧客i仍會(huì)停留的時(shí)間（ 包括使用系統(tǒng)的時(shí)間） v近似將總的優(yōu)化目標(biāo)函數(shù)等效為對(duì)顧客i的目 標(biāo)函數(shù)： 模型的建立3 亭模型 11,22, 1 11,2,2,( , ) 0 , min ( )( ) min () nnn n nn kn k k n k zE Uc t tc t t c E tcQ t

9、QP nk 其中，顧客前有 個(gè)顧客在排隊(duì) ,111 , 2212 ,1 11 1111 ,1 ,1 ,1 ,1 ,1 1 ( () (.) , , (1), (), (0 ) kkkn kkkkn kskskksn kkkk k kkkkk kikikiki k kkin i QPEPA QPEPPA QPEPPA AAEP E EPAEP QQQQ QPAE 下 面 求 出 狀 態(tài) 轉(zhuǎn) 換 平 衡 狀 態(tài) 方 程 ： ） 且 模型的建立3 亭模型 v如果簡(jiǎn)化c1,c2為常數(shù)，并計(jì)算第二個(gè)人的無(wú) 需等待返回時(shí)間的期望值，得 v用MatLab能夠作出 的函數(shù)，并從圖中 得出結(jié)果 模型的求解4 亭

10、模型 21 1,22121,221,2 ()(1()Uc tcPttN tt 22w TtT 0 ( )1,0 x tx t N xedtex 21,2 ()Ut 模型的求解4 亭模型 Average call time(min*10) U2 t2 508.051617.0 8023.051632.5 v第三個(gè)人的無(wú)需等待返回時(shí)間的期望值，同 理可以算出，并用圖解法求出 模型的求解4 亭模型 2,3231,31231,3 231,321,231,31,21,2231,3 21,2231,312231,3 21,2231,312231,3 (1()() ()()(1()() (1()(1()()

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

12、 模型的建立5過(guò)山車(chē)模型 貪心算法 模型的建立5過(guò)山車(chē)模型 v很容易想到，全局優(yōu)化的目標(biāo)變量 v v1. 如果開(kāi)車(chē)的時(shí)間不固定，那么a%是多 少最優(yōu)？就是說(shuō)顧客坐滿(mǎn)多少就開(kāi)車(chē)？ v 2.如果開(kāi)車(chē)的時(shí)間間隔是固定的，那么多長(zhǎng) 時(shí)間開(kāi)一次是最優(yōu)的？ v衡量的標(biāo)準(zhǔn)：目標(biāo)函數(shù) 模型的建立5過(guò)山車(chē)模型 一個(gè)區(qū)間內(nèi)的顧客返回示意圖 ： 目標(biāo)函數(shù)： 模型的建立5過(guò)山車(chē)模型 121 12 1, ,1,2,1,2 2, 221212 1212 , ,. . ()() ()()() () kj j ii j kkkkk jkjkjk kkjkkkj jkjk k kk kh hhbb b tt zzEc tc t

13、E c tc t cEEtc bEccEc tc b ccc tc j-1 i2,ii i 個(gè)人被安排在中的一班車(chē) 設(shè)i個(gè)人的返回時(shí)間是則t 121 ) () j j kk k b Eccc tk 常數(shù)， 由 決定， 2 2 2 % , j j j jk j j cacb c b ckb ，如果開(kāi)車(chē)時(shí)坐滿(mǎn)的人數(shù)固定 如果開(kāi)車(chē)的時(shí)間間隔固定則常數(shù) 模型的建立5過(guò)山車(chē)模型 怎樣求解最優(yōu)的a%c和最優(yōu)的開(kāi)車(chē)間隔？ 對(duì)于這類(lèi)復(fù)雜的問(wèn)題，離散仿真是最好 的方法了 v仿真：用計(jì)算機(jī)生成一些符合某種分布的隨機(jī)數(shù)據(jù) 點(diǎn)，模擬離散時(shí)間的發(fā)生 v這里的仿真用完成： v步驟：1.生成Poisson顧客流模擬到達(dá)時(shí)間

14、 v 2.給定不同的a%c, 開(kāi)車(chē)時(shí)間間隔不定， 計(jì)算代價(jià)函數(shù)，畫(huà)出代價(jià)函數(shù)性能曲線(xiàn) v 3.開(kāi)車(chē)時(shí)間固定，給出不同的開(kāi)車(chē)時(shí)間 間隔，計(jì)算畫(huà)出代價(jià)函數(shù)性能曲線(xiàn) v 4.得出最優(yōu)的結(jié)論 v 模型的仿真5過(guò)山車(chē)模型 過(guò)山車(chē)模型的仿真得到 v在第j天的某一固 定時(shí)刻 i 采集樣本, i=1m, j=1100 形成樣本空間的 矩陣 11121,100 21222,100 ,1,2,100 . . . . . . . . . . mmm lll lll lll ( ) t 過(guò)山車(chē)模型的仿真 v 用列向量的均值 v估計(jì)參數(shù) v樣本的更新用時(shí)間序列 的方法time serial analysis,計(jì)算列向量

15、 的Eucilid距離 vdthreshold就更新一次 ( ) i t ,1,2,100 ,. T iii meanlll 2 1 () m kk k dll 對(duì)某一個(gè)或一組變量x(t)進(jìn)行觀察測(cè)量，將在一系列 時(shí)刻t1, t2, , tn (t為自變量且t1t2 tn ) 所得 到的離散數(shù)字組成序列集合x(chóng)(t1), x(t2), , x(tn)， 我們稱(chēng)之為時(shí)間序列，這種有時(shí)間意義的序列也稱(chēng) 為動(dòng)態(tài)數(shù)據(jù)。時(shí)間序列分析是根據(jù)系統(tǒng)觀測(cè)得到的 時(shí)間序列數(shù)據(jù)，通過(guò)曲線(xiàn)擬合和參數(shù)估計(jì)來(lái)建立數(shù) 學(xué)模型的理論和方法 時(shí)間序列分析time serial analysis 過(guò)山車(chē)模型的仿真 啟發(fā)： 有沒(méi)有別

16、的方法判別樣本如何更 新？ 如：求樣本矩陣的秩， 求樣本向量的相關(guān)系數(shù) 生成的 樣本空 間 過(guò)山車(chē)模型的仿真 實(shí)用的一種模擬Poisson流的方法： 某個(gè)區(qū)間 個(gè)顧客到達(dá)時(shí)間Uniform( ) t Poisson流顧客到達(dá)時(shí)間 過(guò)山車(chē)模型的仿真 按照貪心算法指定的顧客 乘坐的過(guò)山車(chē)的班次 兩種a%c的情況下顧客等待時(shí)間 過(guò)山車(chē)模型的仿真 a%c的性能曲線(xiàn)：可見(jiàn)a%c=70最優(yōu) 過(guò)山車(chē)模型的仿真 開(kāi)車(chē)間隔的優(yōu)化：可是cost function是間隔的 單調(diào)函數(shù)？怎么辦？ 過(guò)山車(chē)模型的仿真 解決：考慮開(kāi)車(chē)的本錢(qián)：開(kāi)車(chē)的時(shí)間間隔越短， 次數(shù)愈多，運(yùn)行本錢(qián)越大找平衡點(diǎn) 最優(yōu) 過(guò)山車(chē)模型的仿真 1 2

17、 3 4 5 6 7 8 9 10 0.511.522.53 x 10 4 cycle interval: min Ecomomic gains of an amusement item: $ average delay economic gain average delay aver 6 模型的穩(wěn)健性與優(yōu)缺點(diǎn) v 亭模型較精確，雖可行但復(fù)雜 v過(guò)山車(chē)模型的貪心算法，簡(jiǎn)單，但不是最優(yōu) quasi-optimal為什么不是最優(yōu)? vStandby隊(duì)列會(huì)有什么影響？ v每個(gè)人的c1和c2可能不同 v將顧客的到達(dá)看成是顧客流(traffic),用Trunking Theory中的Erlang C公式

18、，能夠得出阻塞概率 P(Block)，系統(tǒng)容量C，顧客流的強(qiáng)度A 三 者的關(guān)系 v平均隊(duì)列長(zhǎng)度為： v可將顧客安排在一天之內(nèi)平均隊(duì)列短的時(shí)刻 7 過(guò)山車(chē)模型的改進(jìn) ( ) t 1 0 P(_) !(1) ! C kC C k A blockedGoS Gradeofservice AA AC Ck ( ) Pr t lblockedAt Erlang C的圖形 7 過(guò)山車(chē)模型的改進(jìn) 統(tǒng)計(jì)得出的隊(duì)列長(zhǎng)度，以及仿真得出的 實(shí)際隊(duì)列長(zhǎng)度 說(shuō)明可以用 統(tǒng)計(jì)曲線(xiàn)作安 排返回時(shí)間的 依據(jù) 7 過(guò)山車(chē)模型的改進(jìn) 7 過(guò)山車(chē)模型的改進(jìn) 7 過(guò)山車(chē)模型的改進(jìn) 但是： 可能所有的顧客都被安排 到同一個(gè)隊(duì)列長(zhǎng)度短的時(shí) 段了 如果考慮Standby隊(duì)列？ 7 過(guò)山車(chē)模型的改進(jìn) 使用邊