QuickPassQuickPass系统系统排队问题排队问题docin/sundae_meng排队常常是件很令人恼火的事排队常常是件很令人恼火的事情情尤其是在我们这样的人口大国尤其是在我们这样的人口大国 v电话亭1978年在北京15%的电话要在1小时后才能接通。在电报大楼打电话的人还要带着午饭去排队 v银行窗口，ATMv医院、理发、火车售票v游乐场的游乐项目?docin/sundae_mengv在游乐园中的频频排队v会极为扫兴vDisneyLand中v的FastPassv(QuickPass)系统v就是想解决这v个问题的docin/sundae_mengWhat is QuickPass?v工作原理：v到达的顾客将自己的票插入FastPass的slot中vFastPass计算出建议顾客返回的时间间隔time interval或时间点或时间窗time window）v顾客无需排队，在指定的时间返回就可持票进入docin/sundae_meng怎样缩短排队的等待时间？v银行的排队叫号机v 只是有序的组织了顾客，并没有减少等待时间v如果能实现知道轮到自己需要等待多少时间，再选择合适的时间来，岂不很好？docin/sundae_mengFastPass存在的问题：v预知的返回时间间隔存在误差v按时返回却仍需要排队v建议的返回时间间隔太长v如果告诉你4小时以后再回来呢？v顾客可能不会完全按照安排的时间返回v如果新来的顾客不想使用FastPass系统？现有的Fast Pass真的那么好用吗？docin/sundae_meng我们的目的就是对FastPass系统建立合理的离散统计模型Distributed Statistical Model），求出最优的顾客返回时间。 建模的一般步骤以及：* 模型的改进* 启发与待解决的问题docin/sundae_meng1 模型的假设v游乐园开放时间为8:00-18:00,一天中不同时间的顾客流量不同，比如上午10:00和下午3:00的顾客流量是最大的。v顾客的到达时间符合非时间齐次泊松过程(Nonhomogeneous Possion Process)，到达速率是 docin/sundae_mengPoisson Processdocin/sundae_mengPoisson Processdocin/sundae_meng 分析1：能否得到准确的返回时间？ 2 在我们开始动手建模之前，先要问几个问题：docin/sundae_meng 分析2：使用FastPass后排队是不是可以避免的？FastPass给出的返回时间只是期望值，而非确定值假设所有的顾客都使用FastPass,但需考虑有的顾客可能会不遵守FastPass给出的返回时间 2 在我们开始动手建模之前，先要问几个问题：docin/sundae_meng 分析3：我们优化的目标函数或cost function是什么？是排队时间吗？ 2 在我们开始动手建模之前，先要问几个问题：docin/sundae_meng 优化问题的目标函数为： 3 模型的建立1）目标函数docin/sundae_meng 3 模型的建立1）目标函数docin/sundae_mengv根据排队论queueing theory的分类规则,（X/Y/Z/A代表一类排队的规则，其中v X:顾客流到达所符合的分布 v Y:顾客接受服务的时间所服从的分布 av Z:服务台的个数 v A:服务台一次可服务的顾客数量系统的容量）v针对各个游乐项目的特点，我们主要讨论两种排队系统:模型的建立2） 排队模型的分类docin/sundae_mengv特点：系统容量为1，顾客的到达是Poisson流，服务时间服从指数分布，只有一条队列模型的建立3） 电话亭模型docin/sundae_mengv加入QuickPass系统以后的Poisson排队模型模型的建立3）电话亭模型docin/sundae_mengv求出这类系统的代价函数表达式模型的建立3）电话亭模型docin/sundae_mengv近似将总的优化目标函数等效为对顾客i的目标函数：模型的建立3）电话亭模型docin/sundae_meng模型的建立3）电话亭模型docin/sundae_mengv如果简化c1,c2为常数，并计算第二个人的无需等待返回时间的期望值，得v用MatLab能够作出 的函数，并从图中得出结果模型的求解4）电话亭模型docin/sundae_meng模型的求解4）电话亭模型Average call time(min*10) U2 t2508.051617.08023.051632.5docin/sundae_mengv第三个人的无需等待返回时间的期望值，同理可以算出，并用图解法求出模型的求解4）电话亭模型但是第4个人，第5个人呢？这种方法太繁琐，似乎不好用可否有近似的算法？docin/sundae_mengv与前一个模型的区别在于：系统容量是c1,服务时间固定，顾客的到达仍然是Poisson流。服务系统数量是1模型的建立5） 过山车模型docin/sundae_meng还要考虑：实际的FastPass 系统有两条队列：FastPass 和Standby队列不考虑standby队列，将得到Greedy algorithm模型考虑standby队列，将得到效用函数模型模型的建立5）过山车docin/sundae_meng最简单的情况：最简单的情况：只有一条队列，即所有的人都只用只有一条队列，即所有的人都只用FastPassFastPass系统系统为了防止前面的人等的时间太长，过山车只要载满一为了防止前面的人等的时间太长，过山车只要载满一定数量的人后就开车，假设为定数量的人后就开车，假设为8080c c。用贪心算法用贪心算法greedy algorithm),greedy algorithm),将每个顾客尽量安排将每个顾客尽量安排在离顾客到达时间最近的，且还没有安排满人的一在离顾客到达时间最近的，且还没有安排满人的一班车上。班车上。假设被安排的顾客按照假设被安排的顾客按照BetaBeta分布到达所被安排的时间分布到达所被安排的时间段内段内模型的建立5）过山车模型docin/sundae_meng贪心算法模型的建立5）过山车模型docin/sundae_mengv很容易想到，全局优化的目标变量vv1. 如果开车的时间不固定，则a%是多少最优？就是说顾客坐满多少就开车？v 2.如果开车的时间间隔是固定的，则多长时间开一次是最优的？v衡量的标准：目标函数模型的建立5）过山车模型docin/sundae_meng一个区间内的顾客返回示意图：docin/sundae_meng目标函数：模型的建立5）过山车模型docin/sundae_meng模型的建立5）过山车模型怎样求解最优的a%c和最优的开车间隔？对于这类复杂的问题，离散仿真是最好的方法了docin/sundae_mengv仿真：用计算机生成一些符合某种分布的随机数据点，模拟离散时间的发生v这里的仿真用MatLab6.5完成：v步骤：1.生成Poisson顾客流模拟到达时间）v 2.给定不同的a%c, 开车时间间隔不定，计算代价函数，画出代价函数性能曲线v 3.开车时间固定，给出不同的开车时间间隔，计算画出代价函数性能曲线v 4.得出最优的结论v 模型的仿真5）过山车模型docin/sundae_meng 过山车模型的仿真5.1）得到v在第j天的某一固v定时刻 i 采集样本,vi=1m,vj=1100v形成样本空间的v矩阵docin/sundae_meng 过山车模型的仿真5.1）v 用列向量的均值v估计参数v样本的更新用时间序列的方法time serial analysis）,计算列向量的Eucilid距离vdthreshold就更新一次docin/sundae_mengv 对某一个或一组变量x(t)进行观察测量，将在一系列时刻t1, t2, , tn (t为自变量且t1t2 tn ) 所得到的离散数字组成序列集合x(t1), x(t2), , x(tn)，我们称之为时间序列，这种有时间意义的序列也称为动态数据。时间序列分析是根据系统观测得到的时间序列数据，通过曲线拟合和参数估计来建立数学模型的理论和方法 时间序列分析time serial analysis）docin/sundae_meng 过山车模型的仿真5.1）启发：有没有别的方法判别样本如何更新？如：求样本矩阵的秩， 求样本向量的相关系数docin/sundae_meng生成的样本空间过山车模型的仿真5.1）实用的一种模拟Poisson流的方法：某个区间 个顾客到达时间Uniformdocin/sundae_mengPoisson流顾客到达时间过山车模型的仿真5.2）按照贪心算法指定的顾客乘坐的过山车的班次docin/sundae_meng两种a%c的情况下顾客等待时间过山车模型的仿真5.3）docin/sundae_menga%c的性能曲线：可见a%c=70最优过山车模型的仿真5.3）docin/sundae_meng开车间隔的优化：可是cost function是间隔的单调函数？怎么办？过山车模型的仿真5.4）docin/sundae_meng处置：考虑开车的成本：开车的时间间隔越短，次数愈多，运行成本越大找平衡点 4.67min最优过山车模型的仿真5.4）docin/sundae_meng6 模型的稳健性与优缺点v电话亭模型较精确，虽可行但复杂v过山车模型的贪心算法，简单，但不是最优quasi-optimal）（为什么不是最优?）vStandby队列会有什么影响？v每个人的c1和c2可能不同docin/sundae_mengv将顾客的到达看成是顾客流(traffic),用Trunking Theory中的Erlang C公式，能够得出阻塞概率P(Block)，系统容量C，顾客流的强度A（ ）三者的关系v平均队列长度为：v可将顾客安排在一天之内平均队列短的时刻7 过山车模型的改进 docin/sundae_mengErlang C的图形7 过山车模型的改进docin/sundae_meng统计得出的队列长度，以及仿真得出的实际队列长度说明可以用统计曲线作安排返回时间的根据7 过山车模型的改进docin/sundae_meng改进算法的效果7 过山车模型的改进docin/sundae_meng7 过山车模型的改进统计队列长度曲线应该实时更新！但是：可能所有的顾客都被安排到同一个队列长度短的时段了docin/sundae_meng如果考虑Standby队列？7 过山车模型的改进使用边际效用函数(Marginal Utility Function)的思想：FastPass队列中每增加一个人，会对Standby队列中的人造成目标函数的损失docin/sundae_mengv使用IC卡门票，记录顾客的特点，数据集中在中心数据库v给顾客提供预计的当天实时队列长度表，顾客可自己选择返回时间，选择t1,t2时间的长度v你的更好的办法？8 将来的工作：设计更好的FastPass系统docin/sundae_mengv怎样写数学建模论文？v怎样求解没有显式表达的式子？v如何模拟离散随机时间？v如何通过仿真的结果求参数的优化v使用数学软件，仿真的过程中常常也会的到新的想法与结论v灵活借鉴其他学科中的方法：如Queueing theory(排队论), Trunking Theory(复用论), Greedy Algorithm贪心算法）, Marginal Utility Function(边际效用函数)9 启发与收获docin/sundae_meng这是一类OpenEnd ProblemvHomework: 相似的问题比如ICM2019 C题，v To Screen or not to screen? 飞机场的调度以及安全检查问题v你将如何安排？ Its upto you! docin/sundae_meng感激Acknowledgement）v本次讲座内容来自MCM2019#team624的paper,感谢全体成员的辛勤工作！以及杨老师的指导与支持。v paper下载：mail.ustc.edu/xieyao/MCM2019_B.pdfdocin/sundae_meng