QuickPass系統(tǒng)

排隊(duì)問題謝瑤03/03/xieyao@電子工程與信息科學(xué)系PB00006第1頁排隊(duì)經(jīng)常是件很令人惱火事情……

尤其是在我們這么人口大國

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

銀行窗口，ATM醫(yī)院、剪發(fā)、火車售票…游樂場(chǎng)游樂項(xiàng)目?第2頁在游樂園中頻頻排隊(duì)會(huì)極為掃興……DisneyLand中FastPass(QuickPass)系統(tǒng)就是想處理這個(gè)問題第3頁WhatisQuickPass?工作原理：抵達(dá)用戶將自己票插入FastPassslot中FastPass計(jì)算出提議用戶返回時(shí)間間隔（timeinterval）或時(shí)間點(diǎn)或時(shí)間窗（timewindow）用戶無需排隊(duì)，在指定時(shí)間返回就可持票進(jìn)入第4頁怎樣縮短排隊(duì)等候時(shí)間？銀行排隊(duì)叫號(hào)機(jī)只是有序組織了用戶，并沒有降低等候時(shí)間假如能實(shí)現(xiàn)知道輪到自己需要等候多少時(shí)間，再選擇適當(dāng)時(shí)間來，豈不很好？

第5頁FastPass存在問題：預(yù)知返回時(shí)間間隔存在誤差－－按時(shí)返回卻仍需要排隊(duì)提議返回時(shí)間間隔太長－－假如告訴你4小時(shí)以后再回來呢？用戶可能不會(huì)完全按照安排時(shí)間返回假如新來用戶不想使用FastPass系統(tǒng)？現(xiàn)有FastPass真那么好用嗎？第6頁我們目標(biāo)就是對(duì)FastPass系統(tǒng)建立

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

建模普通步驟以及：*模型改進(jìn)*啟發(fā)與待處理問題第7頁1模型假設(shè)游樂園開放時(shí)間為8:00-18:00,一天中不一樣時(shí)間用戶流量不一樣，比如早晨10:00和下午3:00用戶流量是最大。用戶抵達(dá)時(shí)間符合非時(shí)間齊次泊松過程(NonhomogeneousPossionProcess)，抵達(dá)速率是第8頁P(yáng)oissonProcess第9頁P(yáng)oissonProcess第10頁分析1：能否得到準(zhǔn)確返回時(shí)間？

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

先要問幾個(gè)問題：第11頁分析2：使用FastPass后排隊(duì)是不是能夠防止？FastPass給出返回時(shí)間只是期望值，而非確定值假設(shè)全部用戶都使用FastPass,但需考慮有用戶可能會(huì)不恪守FastPass給出返回時(shí)間

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

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

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

先要問幾個(gè)問題：第13頁優(yōu)化問題目標(biāo)函數(shù)為：

3模型建立（1）－目標(biāo)函數(shù)第14頁

3模型建立（1）－目標(biāo)函數(shù)第15頁依據(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è)游樂項(xiàng)目標(biāo)特點(diǎn)，我們主要討論兩種排隊(duì)系統(tǒng):模型建立（2）－排隊(duì)模型分類第16頁特點(diǎn)：系統(tǒng)容量為1，用戶抵達(dá)是Poisson流，服務(wù)時(shí)間服從指數(shù)分布，只有一條隊(duì)列模型建立（3）－電話亭模型第17頁加入QuickPass系統(tǒng)以后Poisson排隊(duì)模型模型建立（3）－電話亭模型第18頁求出這類系統(tǒng)代價(jià)函數(shù)表示式模型建立（3）－電話亭模型第19頁近似將總優(yōu)化目標(biāo)函數(shù)等效為對(duì)用戶i目標(biāo)函數(shù)：模型建立（3）－電話亭模型第20頁模型建立（3）－電話亭模型第21頁假如簡(jiǎn)化c1,c2為常數(shù)，并計(jì)算第二個(gè)人無需等候返回時(shí)間期望值，得用MatLab能夠作出函數(shù)，并從圖中得出結(jié)果模型求解（4）－電話亭模型第22頁模型求解（4）－電話亭模型Averagecalltime(min*10’)U2t2508.051617.08023.051632.5第23頁第三個(gè)人無需等候返回時(shí)間期望值，同理能夠算出，并用圖解法求出模型求解（4）－電話亭模型不過第4個(gè)人，第5個(gè)人……呢？這種方法太繁瑣，似乎不好用可否有近似算法？第24頁與前一個(gè)模型區(qū)分在于：系統(tǒng)容量是c>1,服務(wù)時(shí)間固定，用戶抵達(dá)依然是Poisson流。服務(wù)系統(tǒng)數(shù)量是1模型建立（5）－過山車模型第25頁還要考慮：實(shí)際FastPass系統(tǒng)有兩條隊(duì)列：FastPass和Standby隊(duì)列不考慮standby隊(duì)列，將得到Greedyalgorithm模型考慮standby隊(duì)列，將得到效用函數(shù)模型模型建立（5）－過山車第26頁最簡(jiǎn)單情況：只有一條隊(duì)列，即全部人都只用FastPass系統(tǒng)為了預(yù)防前面人等時(shí)間太長，過山車只要載滿一定數(shù)量人后就開車，假設(shè)為80％c。用貪心算法（greedyalgorithm),將每個(gè)用戶盡可能安排在離用戶抵達(dá)時(shí)間最近，且還沒有安排滿人一班車上。假設(shè)被安排用戶按照Beta分布抵達(dá)所被安排時(shí)間段內(nèi)模型建立（5）－過山車模型第27頁貪心算法模型建立（5）－過山車模型第28頁很輕易想到，全局優(yōu)化目標(biāo)變量

1.假如開車時(shí)間不固定，則a%是多少最優(yōu)？就是說用戶坐滿多少就開車？

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

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

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

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

模型仿真（5）－過山車模型第33頁

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

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

時(shí)間序列分析（timeserialanalysis）第36頁

過山車模型仿真（5.1）啟發(fā)：有沒有別方法判別樣本怎樣更新？如：求樣本矩陣秩，求樣本向量相關(guān)系數(shù)第37頁生成樣本空間過山車模型仿真（5.1）實(shí)用一個(gè)模擬Poisson流方法：某個(gè)區(qū)間個(gè)用戶抵達(dá)時(shí)間~Uniform第38頁P(yáng)oisson流用戶抵達(dá)時(shí)間過山車模型仿真（5.2）按照貪心算法指定用戶乘坐過山車班次第39頁兩種a%c情況下用戶等候時(shí)間過山車模型仿真（5.3）第40頁a%c性能曲線：可見a%c=70最優(yōu)過山車模型仿真（5.3）第41頁開車間隔優(yōu)化：可是costfunction是間隔單調(diào)函數(shù)？怎么辦？過山車模型仿真（5.4）第42頁處理：考慮開車成本：開車時(shí)間間隔越短，次數(shù)愈多，運(yùn)行成本越大－－找平衡點(diǎn)

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

－說明能夠用

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

排返回時(shí)間

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