quickpass系統(tǒng)排隊問題 （中科大，謝瑤）

1、QuickPass系統(tǒng)排隊問題,謝瑤03/03/2004xieyao@mail.ustc.edu.cn電子工程與信息科學(xué)系PB00006,排隊常常是件很令人惱火的事情……尤其是在我們這樣的人口大國?,電話亭－1978年在北京15%的電話要在1小時后才能接通。在電報大樓打電話的人還要帶著午飯去排隊 銀行窗口，ATM醫(yī)院、理發(fā)、火車售票…游樂場的游樂項目,,?,在游樂園中的頻頻排隊會極為掃興……DisneyLand中的

2、FastPass(QuickPass)系統(tǒng)就是想解決這個問題的,What is QuickPass?,工作原理：到達的顧客將自己的票插入FastPass的slot中FastPass計算出建議顧客返回的時間間隔（time interval）或時間點或時間窗（time window）顧客無需排隊，在指定的時間返回就可持票進入,怎樣縮短排隊的等待時間？,銀行的排隊叫號機 只是有序的組織了顧客，并沒有減少等待時間如果能實現(xiàn)知

3、道輪到自己需要等待多少時間，再選擇合適的時間來，豈不很好？?,FastPass存在的問題：,預(yù)知的返回時間間隔存在誤差－－按時返回卻仍需要排隊建議的返回時間間隔太長－－如果告訴你4小時以后再回來呢？顧客可能不會完全按照安排的時間返回如果新來的顧客不想使用FastPass系統(tǒng)？,現(xiàn)有的Fast Pass真的那么好用嗎？,我們的目的就是對FastPass系統(tǒng)建立合理的離散統(tǒng)計模型（Distributed Statistical

4、Model），求出最優(yōu)的顧客返回時間。,建模的一般步驟以及：* 模型的改進* 啟發(fā)與待解決的問題,1 模型的假設(shè),游樂園開放時間為8:00-18:00,一天中不同時間的顧客流量不同，比如上午10:00和下午3:00的顧客流量是最大的。顧客的到達時間符合非時間齊次泊松過程(Nonhomogeneous Possion Process)，到達速率是,Poisson Process,Poisson Process,分析1：能否

5、得到準(zhǔn)確的返回時間？,2 在我們開始動手建模之前，先要問幾個問題：,分析2：使用FastPass后排隊是不是可以避免的？FastPass給出的返回時間只是期望值，而非確定值假設(shè)所有的顧客都使用FastPass,但需考慮有的顧客可能會不遵守FastPass給出的返回時間,2 在我們開始動手建模之前，先要問幾個問題：,分析3：我們優(yōu)化的目標(biāo)函數(shù)（或cost function）是什么？是排隊時間嗎？,2 在我們開始動手建模之前，先要

6、問幾個問題：,優(yōu)化問題的目標(biāo)函數(shù)為：,3 模型的建立（1）－目標(biāo)函數(shù),,,3 模型的建立（1）－目標(biāo)函數(shù),,根據(jù)排隊論（queueing theory）的分類規(guī)則,（X/Y/Z/A）代表一類排隊的規(guī)則，其中 X:顧客流到達所符合的分布 Y:顧客接受服務(wù)的時間所服從的分布 a Z:服務(wù)臺的個數(shù) A:服務(wù)臺一次可服務(wù)的顧客數(shù)量（系統(tǒng)的容量）針對各個游樂項目的特點，我們主要

7、討論兩種排隊系統(tǒng):,模型的建立（2）－ 排隊模型的分類,,特點：系統(tǒng)容量為1，顧客的到達是Poisson流，服務(wù)時間服從指數(shù)分布，只有一條隊列,模型的建立（3）－ 電話亭模型,,加入QuickPass系統(tǒng)以后的Poisson排隊模型,模型的建立（3）－電話亭模型,,求出這類系統(tǒng)的代價函數(shù)表達式,模型的建立（3）－電話亭模型,,,,,近似將總的優(yōu)化目標(biāo)函數(shù)等效為對顧客i的目標(biāo)函數(shù)：,模型的建立（3）－電話亭模型,,模型的建立（3）－電話亭

8、模型,,如果簡化c1,c2為常數(shù)，并計算第二個人的無需等待返回時間的期望值，得用MatLab能夠作出 的函數(shù)，并從圖中得出結(jié)果,模型的求解（4）－電話亭模型,,,,,模型的求解（4）－電話亭模型,,,第三個人的無需等待返回時間的期望值，同理可以算出，并用圖解法求出,模型的求解（4）－電話亭模型,,但是第4個人，第5個人……呢？這種方法太繁瑣，似乎不好用可否有近似的算法？,,與前一個模型的區(qū)別在于：系統(tǒng)容量是

9、c>1,服務(wù)時間固定，顧客的到達仍然是Poisson流。服務(wù)系統(tǒng)數(shù)量是1,模型的建立（5）－ 過山車模型,,還要考慮：實際的FastPass 系統(tǒng)有兩條隊列：FastPass 和Standby隊列不考慮standby隊列，將得到Greedy algorithm模型考慮standby隊列，將得到效用函數(shù)模型,模型的建立（5）－過山車,,最簡單的情況：只有一條隊列，即所有的人都只用FastPass系統(tǒng)為了防

10、止前面的人等的時間太長，過山車只要載滿一定數(shù)量的人后就開車，假設(shè)為80％c。用貪心算法（greedy algorithm),將每個顧客盡量安排在離顧客到達時間最近的，且還沒有安排滿人的一班車上。假設(shè)被安排的顧客按照Beta分布到達所被安排的時間段內(nèi),模型的建立（5）－過山車模型,,貪心算法,模型的建立（5）－過山車模型,,很容易想到，全局優(yōu)化的目標(biāo)變量1. 如果開車的時間不固定，則a%是多少最優(yōu)？就是說顧客坐滿多少就開

11、車？ 2.如果開車的時間間隔是固定的，則多長時間開一次是最優(yōu)的？衡量的標(biāo)準(zhǔn)：目標(biāo)函數(shù),模型的建立（5）－過山車模型,一個區(qū)間內(nèi)的顧客返回示意圖,：,目標(biāo)函數(shù)：,模型的建立（5）－過山車模型,,模型的建立（5）－過山車模型,,怎樣求解最優(yōu)的a%c和最優(yōu)的開車間隔？－－對于這類復(fù)雜的問題，離散仿真是最好的方法了,,仿真：用計算機生成一些符合某種分布的隨機數(shù)據(jù)點，模擬離散時間的發(fā)生這里的仿真用MatLab6.5完成：

12、步驟：1.生成Poisson顧客流（模擬到達時間） 2.給定不同的a%c, 開車時間間隔不定，計算代價函數(shù)，畫出代價函數(shù)性能曲線 3.開車時間固定，給出不同的開車時間間隔，計算畫出代價函數(shù)性能曲線 4.得出最優(yōu)的結(jié)論,模型的仿真（5）－過山車模型,,,過山車模型的仿真（5.1）－得到,在第j天的某一固定時刻 i 采集樣本,i=1…m,j=1…100形成樣

13、本空間的矩陣,,,過山車模型的仿真（5.1）,用列向量的均值估計參數(shù)樣本的更新用時間序列的方法（time serial analysis）,計算列向量的Eucilid距離d>threshold就更新一次,,對某一個或一組變量x(t)進行觀察測量，將在一系列時刻t1, t2, …, tn (t為自變量且t1<t2<…< tn ) 所得到的離散數(shù)字組成序列集合x(t1), x(t2), …, x(tn

14、)，我們稱之為時間序列，這種有時間意義的序列也稱為動態(tài)數(shù)據(jù)。時間序列分析是根據(jù)系統(tǒng)觀測得到的時間序列數(shù)據(jù)，通過曲線擬合和參數(shù)估計來建立數(shù)學(xué)模型的理論和方法,時間序列分析（time serial analysis）,,,過山車模型的仿真（5.1）,啟發(fā)：有沒有別的方法判別樣本如何更新？,如：求樣本矩陣的秩， 求樣本向量的相關(guān)系數(shù),生成的樣本空間,過山車模型的仿真（5.1）,實用的一種模擬Poisson流的方法：某個區(qū)間

15、 個顧客到達時間~Uniform,,Poisson流顧客到達時間,過山車模型的仿真（5.2）,按照貪心算法指定的顧客乘坐的過山車的班次,兩種a%c的情況下顧客等待時間,過山車模型的仿真（5.3）,,a%c的性能曲線：可見a%c=70最優(yōu),過山車模型的仿真（5.3）,開車間隔的優(yōu)化：可是cost function是間隔的單調(diào)函數(shù)？怎么辦？,過山車模型的仿真（5.4）,,解決：考慮開車的成本：開車的時間間隔越短，次數(shù)愈多，運行成

16、本越大－－找平衡點 4.67min最優(yōu),過山車模型的仿真（5.4）,,6 模型的穩(wěn)健性與優(yōu)缺點,電話亭模型較精確，雖可行但復(fù)雜過山車模型的貪心算法，簡單，但不是最優(yōu)（quasi-optimal）（為什么不是最優(yōu)?）Standby隊列會有什么影響？每個人的c1和c2可能不同,,將顧客的到達看成是顧客流(traffic),用Trunking Theory中的Erlang C公式，能夠得出阻塞概率P(Block)，系統(tǒng)容量C，顧客

17、流的強度A（ ）三者的關(guān)系平均隊列長度為：可將顧客安排在一天之內(nèi)平均隊列短的時刻,7 過山車模型的改進,,,Erlang C的圖形,7 過山車模型的改進,統(tǒng)計得出的隊列長度，以及仿真得出的實際隊列長度－說明可以用統(tǒng)計曲線作安排返回時間的依據(jù),7 過山車模型的改進,改進算法的效果,7 過山車模型的改進,7 過山車模型的改進,統(tǒng)計隊列長度曲線應(yīng)該實時更新！,但是：可能所有的顧客都被安排到同一個隊列長度短的時段

18、了……,如果考慮Standby隊列？,7 過山車模型的改進,使用邊際效用函數(shù)(Marginal Utility Function)的思想：FastPass隊列中每增加一個人，會對Standby隊列中的人造成目標(biāo)函數(shù)的損失……,,使用IC卡門票，記錄顧客的特點，數(shù)據(jù)集中在中心數(shù)據(jù)庫給顧客提供預(yù)計的當(dāng)天實時隊列長度表，顧客可自己選擇返回時間，選擇t1,t2時間的長度你的更好的辦法？,8 將來的工作：設(shè)計更好的FastPass系統(tǒng),,怎

19、樣寫數(shù)學(xué)建模論文？怎樣求解沒有顯式表達的式子？如何模擬離散隨機時間？如何通過仿真的結(jié)果求參數(shù)的優(yōu)化－－使用數(shù)學(xué)軟件，仿真的過程中常常也會的到新的想法與結(jié)論靈活借鑒其他學(xué)科中的方法：如Queueing theory(排隊論), Trunking Theory(復(fù)用論), Greedy Algorithm（貪心算法）, Marginal Utility Function(邊際效用函數(shù)),9 啟發(fā)與收獲,這是一類OpenEnd

20、Problem,Homework: 相似的問題比如ICM2003 C題， To Screen or not to screen? –飛機場的調(diào)度以及安全檢查問題你將如何安排？ Its upto you!,感謝（Acknowledgement）,本次講座內(nèi)容來自MCM2004#team624的paper,感謝全體成員的辛勤工作！以及楊老師的指導(dǎo)與支持。 paper下載：http://mail.ustc.edu.cn/~