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