QuickPass系統(tǒng)

排隊(duì)問(wèn)題/sundae_meng排隊(duì)常常是件很令人惱火的事情……

尤其是在我們這樣的人口大國(guó)

電話亭－1978年在北京15%的電話要在1小時(shí)后才能接通。在電報(bào)大樓打電話的人還要帶著午飯去排隊(duì)

銀行窗口，ATM醫(yī)院、理發(fā)、火車售票…游樂(lè)場(chǎng)的游樂(lè)項(xiàng)目?/sundae_meng在游樂(lè)園中的頻頻排隊(duì)會(huì)極為掃興……DisneyLand中的FastPass(QuickPass)系統(tǒng)就是想解決這個(gè)問(wèn)題的/sundae_mengWhatisQuickPass?工作原理：到達(dá)的顧客將自己的票插入FastPass的slot中FastPass計(jì)算出建議顧客返回的時(shí)間間隔（timeinterval）或時(shí)間點(diǎn)或時(shí)間窗（timewindow）顧客無(wú)需排隊(duì)，在指定的時(shí)間返回就可持票進(jìn)入/sundae_meng怎樣縮短排隊(duì)的等待時(shí)間？銀行的排隊(duì)叫號(hào)機(jī)只是有序的組織了顧客，并沒(méi)有減少等待時(shí)間如果能實(shí)現(xiàn)知道輪到自己需要等待多少時(shí)間，再選擇合適的時(shí)間來(lái)，豈不很好？

/sundae_mengFastPass存在的問(wèn)題：預(yù)知的返回時(shí)間間隔存在誤差－－按時(shí)返回卻仍需要排隊(duì)建議的返回時(shí)間間隔太長(zhǎng)－－如果告訴你4小時(shí)以后再回來(lái)呢？顧客可能不會(huì)完全按照安排的時(shí)間返回如果新來(lái)的顧客不想使用FastPass系統(tǒng)？現(xiàn)有的FastPass真的那么好用嗎？/sundae_meng我們的目的就是對(duì)FastPass系統(tǒng)建立

合理的離散統(tǒng)計(jì)模型（DistributedStatisticalModel），求出最優(yōu)的顧客返回時(shí)間。

建模的一般步驟以及：*模型的改進(jìn)*啟發(fā)與待解決的問(wèn)題/sundae_meng1模型的假設(shè)游樂(lè)園開(kāi)放時(shí)間為8:00-18:00,一天中不同時(shí)間的顧客流量不同，比如上午10:00和下午3:00的顧客流量是最大的。顧客的到達(dá)時(shí)間符合非時(shí)間齊次泊松過(guò)程(NonhomogeneousPossionProcess)，到達(dá)速率是/sundae_mengPoissonProcess/sundae_mengPoissonProcess/sundae_meng分析1：能否得到準(zhǔn)確的返回時(shí)間？

2在我們開(kāi)始動(dòng)手建模之前，

先要問(wèn)幾個(gè)問(wèn)題：/sundae_meng分析2：使用FastPass后排隊(duì)是不是可以避免的？FastPass給出的返回時(shí)間只是期望值，而非確定值假設(shè)所有的顧客都使用FastPass,但需考慮有的顧客可能會(huì)不遵守FastPass給出的返回時(shí)間

2在我們開(kāi)始動(dòng)手建模之前，

先要問(wèn)幾個(gè)問(wèn)題：/sundae_meng分析3：我們優(yōu)化的目標(biāo)函數(shù)（或costfunction）是什么？是排隊(duì)時(shí)間嗎？

2在我們開(kāi)始動(dòng)手建模之前，

先要問(wèn)幾個(gè)問(wèn)題：/sundae_meng優(yōu)化問(wèn)題的目標(biāo)函數(shù)為：

3模型的建立（1）－目標(biāo)函數(shù)/sundae_meng

3模型的建立（1）－目標(biāo)函數(shù)/sundae_meng根據(jù)排隊(duì)論（queueingtheory）的分類規(guī)則,（X/Y/Z/A）代表一類排隊(duì)的規(guī)則，其中X:顧客流到達(dá)所符合的分布Y:顧客接受服務(wù)的時(shí)間所服從的分布aZ:服務(wù)臺(tái)的個(gè)數(shù)A:服務(wù)臺(tái)一次可服務(wù)的顧客數(shù)量（系統(tǒng)的容量）針對(duì)各個(gè)游樂(lè)項(xiàng)目的特點(diǎn)，我們主要討論兩種排隊(duì)系統(tǒng):模型的建立（2）－排隊(duì)模型的分類/sundae_meng特點(diǎn)：系統(tǒng)容量為1，顧客的到達(dá)是Poisson流，服務(wù)時(shí)間服從指數(shù)分布，只有一條隊(duì)列模型的建立（3）－電話亭模型/sundae_meng加入QuickPass系統(tǒng)以后的Poisson排隊(duì)模型模型的建立（3）－電話亭模型/sundae_meng求出這類系統(tǒng)的代價(jià)函數(shù)表達(dá)式模型的建立（3）－電話亭模型/sundae_meng近似將總的優(yōu)化目標(biāo)函數(shù)等效為對(duì)顧客i的目標(biāo)函數(shù)：模型的建立（3）－電話亭模型/sundae_meng模型的建立（3）－電話亭模型/sundae_meng如果簡(jiǎn)化c1,c2為常數(shù)，并計(jì)算第二個(gè)人的無(wú)需等待返回時(shí)間的期望值，得用MatLab能夠作出的函數(shù)，并從圖中得出結(jié)果模型的求解（4）－電話亭模型/sundae_meng模型的求解（4）－電話亭模型Averagecalltime(min*10’)U2t2508.051617.08023.051632.5/sundae_meng第三個(gè)人的無(wú)需等待返回時(shí)間的期望值，同理可以算出，并用圖解法求出模型的求解（4）－電話亭模型但是第4個(gè)人，第5個(gè)人……呢？這種方法太繁瑣，似乎不好用可否有近似的算法？/sundae_meng與前一個(gè)模型的區(qū)別在于：系統(tǒng)容量是c>1,服務(wù)時(shí)間固定，顧客的到達(dá)仍然是Poisson流。服務(wù)系統(tǒng)數(shù)量是1模型的建立（5）－過(guò)山車模型/sundae_meng還要考慮：實(shí)際的FastPass系統(tǒng)有兩條隊(duì)列：FastPass和Standby隊(duì)列不考慮standby隊(duì)列，將得到Greedyalgorithm模型考慮standby隊(duì)列，將得到效用函數(shù)模型模型的建立（5）－過(guò)山車/sundae_meng最簡(jiǎn)單的情況：只有一條隊(duì)列，即所有的人都只用FastPass系統(tǒng)為了防止前面的人等的時(shí)間太長(zhǎng)，過(guò)山車只要載滿一定數(shù)量的人后就開(kāi)車，假設(shè)為80％c。用貪心算法（greedyalgorithm),將每個(gè)顧客盡量安排在離顧客到達(dá)時(shí)間最近的，且還沒(méi)有安排滿人的一班車上。假設(shè)被安排的顧客按照Beta分布到達(dá)所被安排的時(shí)間段內(nèi)模型的建立（5）－過(guò)山車模型/sundae_meng貪心算法模型的建立（5）－過(guò)山車模型/sundae_meng很容易想到，全局優(yōu)化的目標(biāo)變量

1.如果開(kāi)車的時(shí)間不固定，則a%是多少最優(yōu)？就是說(shuō)顧客坐滿多少就開(kāi)車？

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

2.給定不同的a%c,開(kāi)車時(shí)間間隔不定，計(jì)算代價(jià)函數(shù)，畫(huà)出代價(jià)函數(shù)性能曲線

3.開(kāi)車時(shí)間固定，給出不同的開(kāi)車時(shí)間間隔，計(jì)算畫(huà)出代價(jià)函數(shù)性能曲線

4.得出最優(yōu)的結(jié)論

模型的仿真（5）－過(guò)山車模型/sundae_meng

過(guò)山車模型的仿真（5.1）－得到在第j天的某一固定時(shí)刻i采集樣本,i=1…m,j=1…100形成樣本空間的矩陣/sundae_meng

過(guò)山車模型的仿真（5.1）用列向量的均值估計(jì)參數(shù)樣本的更新用時(shí)間序列的方法（timeserialanalysis）,計(jì)算列向量的Eucilid距離d>threshold就更新一次/sundae_meng對(duì)某一個(gè)或一組變量x(t)進(jìn)行觀察測(cè)量，將在一系列時(shí)刻t1,t2,…,tn(t為自變量且t1<t2<…<tn)所得到的離散數(shù)字組成序列集合x(chóng)(t1),x(t2),…,x(tn)，我們稱之為時(shí)間序列，這種有時(shí)間意義的序列也稱為動(dòng)態(tài)數(shù)據(jù)。時(shí)間序列分析是根據(jù)系統(tǒng)觀測(cè)得到的時(shí)間序列數(shù)據(jù)，通過(guò)曲線擬合和參數(shù)估計(jì)來(lái)建立數(shù)學(xué)模型的理論和方法

時(shí)間序列分析（timeserialanalysis）/sundae_meng

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

4.67min最優(yōu)過(guò)山車模型的仿真（5.4）/sundae_meng6模型的穩(wěn)健性與優(yōu)缺點(diǎn)電話亭模型較精確，雖可行但復(fù)雜過(guò)山車模型的貪心算法，簡(jiǎn)單，但不是最優(yōu)（quasi-optimal）（為什么不是最優(yōu)?）Standby隊(duì)列會(huì)有什么影響？每個(gè)人的c1和c2可能不同/sundae_meng將顧客的到達(dá)看成是顧客流(traffic),用TrunkingTheory中的ErlangC公式，能夠得出阻塞概率P(Block)，系統(tǒng)容量C，顧客流的強(qiáng)度A（）三者的關(guān)系平均隊(duì)列長(zhǎng)度為：可將顧客安排在一天之內(nèi)平均隊(duì)列短的時(shí)刻7過(guò)山車模型的改進(jìn)/sundae_mengErlangC的圖形7過(guò)山車模型的改進(jìn)/sundae_meng統(tǒng)計(jì)得出的隊(duì)列長(zhǎng)度，以及仿真得出的實(shí)際隊(duì)列長(zhǎng)度

－說(shuō)明可以用

統(tǒng)計(jì)曲線作安

排返回時(shí)間的

依據(jù)7過(guò)山車模型的改進(jìn)/sundae_meng改進(jìn)算法的效果7過(guò)山車模型的改進(jìn)/sundae_meng7過(guò)山車模型的改進(jìn)統(tǒng)計(jì)隊(duì)列長(zhǎng)度曲線應(yīng)該實(shí)時(shí)更新！但是：可能所有的顧客都被安排到同一個(gè)隊(duì)列長(zhǎng)度短的時(shí)段了……/sundae_meng如果考慮Standby隊(duì)列？7過(guò)山車模型的改進(jìn)使用邊際效用函數(shù)(MarginalUtilityFunction)的思想：FastPass隊(duì)列中每增加一個(gè)人，會(huì)對(duì)Standby隊(duì)列中的人造成目標(biāo)函數(shù)的損失……/sundae_meng使用IC卡門票，記錄顧客的特點(diǎn)，數(shù)據(jù)集中在中心數(shù)據(jù)庫(kù)給顧客提供預(yù)計(jì)的當(dāng)天實(shí)時(shí)隊(duì)列長(zhǎng)度表，顧客可自己選擇返回時(shí)間，選擇t1,t2時(shí)間的長(zhǎng)度你的更好的辦法？8將來(lái)的工作：設(shè)計(jì)更好的FastPass系統(tǒng)/sundae_meng怎樣寫數(shù)學(xué)建模論文？怎樣求解沒(méi)有顯式表達(dá)的式子？如何模擬離散隨機(jī)時(shí)間？如何通過(guò)仿真的結(jié)果求參數(shù)的優(yōu)化－－使用數(shù)學(xué)軟件，仿真的過(guò)程中常常也會(huì)的到新的想法與結(jié)論靈活借鑒其他學(xué)科中的方法：如Queueingtheory(排隊(duì)論),TrunkingTheory(復(fù)用論),GreedyAlgorithm（貪心算法）,MarginalUtilityFunction(邊際效用函數(shù))9啟發(fā)與收獲/sundae_me