QuickPass系统排队问题&nbsp

nullQuickPass系统 排队问题QuickPass系统 排队问题谢瑶 03/03/2004 xieyao@mail.ustc.edu.cn 电子工程与信息科学系PB00006排队常常是件很令人恼火的事情…… 尤其是在我们这样的人口大国排队常常是件很令人恼火的事情…… 尤其是在我们这样的人口大国电话亭－1978年在北京15%的电话要在1小时后才能接通。在电报大楼打电话的人还要带着午饭去排队 银行窗口，ATM 医院、理发、火车售票… 游乐场的游乐项目 ?null在游乐园中的频频排队 会极为扫兴…… DisneyLand中 的FastPass (QuickPass)系统 就是想解决这 个问题的What is QuickPass?What is QuickPass?工作原理： 到达的顾客将自己的票插入FastPass的slot中 FastPass计算出 建议 关于小区增设电动车充电建议给教师的建议PDF智慧城市建议书pdf给教师的36条建议下载税则修订调整建议表下载 顾客返回的时间间隔（time interval）或时间点或时间窗（time window） 顾客无需排队，在指定的时间返回就可持票进入怎样缩短排队的等待时间？怎样缩短排队的等待时间？银行的排队叫号机 只是有序的组织了顾客，并没有减少等待时间 如果能实现知道轮到自己需要等待多少时间，再选择合适的时间来，岂不很好？ FastPass存在的问题：FastPass存在的问题：预知的返回时间间隔存在误差 －－按时返回却仍需要排队 建议的返回时间间隔太长 －－如果告诉你4小时以后再回来呢？ 顾客可能不会完全按照安排的时间返回 如果新来的顾客不想使用FastPass系统？ 现有的Fast Pass真的那么好用吗？我们的目的就是对FastPass系统建立 合理的离散统计模型（Distributed Statistical Model），求出最优的顾客返回时间。我们的目的就是对FastPass系统建立 合理的离散统计模型（Distributed Statistical Model），求出最优的顾客返回时间。 建模的一般步骤 以及： * 模型的改进 * 启发与待解决的问题1 模型的假设1 模型的假设游乐园开放时间为8:00-18:00,一天中不同时间的顾客流量不同，比如上午10:00和下午3:00的顾客流量是最大的。 顾客的到达时间符合非时间齐次泊松过程(Nonhomogeneous Possion Process)，到达速率是 Poisson ProcessPoisson ProcessPoisson ProcessPoisson Processnull 分析1：能否得到准确的返回时间？ 2 在我们开始动手建模之前， 先要问几个问题：null 分析2：使用FastPass后排队是不是可以避免的？ FastPass给出的返回时间只是期望值，而非确定值 假设所有的顾客都使用FastPass,但需考虑有的顾客可能会不遵守FastPass给出的返回时间 2 在我们开始动手建模之前， 先要问几个问题：null 分析3：我们优化的目标函数（或cost function）是什么？是排队时间吗？ 2 在我们开始动手建模之前， 先要问几个问题：null 优化问题的目标函数为： 3 模型的建立（1）－目标函数null 3 模型的建立（1）－目标函数null根据排队论（queueing theory）的分类规则,（X/Y/Z/A）代表一类排队的规则，其中 X:顾客流到达所符合的分布 Y:顾客接受服务的时间所服从的分布 a Z:服务台的个数 A:服务台一次可服务的顾客数量（系统的容量） 针对各个游乐项目的特点，我们主要讨论两种排队系统:模型的建立（2）－ 排队模型的分类null特点：系统容量为1，顾客的到达是Poisson流，服务时间服从指数分布，只有一条队列 模型的建立（3）－ 电话亭模型null加入QuickPass系统以后的Poisson排队模型 模型的建立（3）－电话亭模型null求出这类系统的代价函数表达式 模型的建立（3）－电话亭模型null近似将总的优化目标函数等效为对顾客i的目标函数：模型的建立（3）－电话亭模型null模型的建立（3）－电话亭模型null如果简化c1,c2为常数，并计算第二个人的无需等待返回时间的期望值，得 用MatLab能够作出 的函数，并从图中得出结果模型的求解（4）－电话亭模型null模型的求解（4）－电话亭模型null第三个人的无需等待返回时间的期望值，同理可以算出，并用图解法求出 模型的求解（4）－电话亭模型但是第4个人，第5个人……呢？ 这种 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 太繁琐，似乎不好用 可否有近似的算法？ null与前一个模型的区别在于：系统容量是c>1,服务时间固定，顾客的到达仍然是Poisson流。服务系统数量是1模型的建立（5）－ 过山车模型null还要考虑： 实际的FastPass 系统有两条队列：FastPass 和Standby队列 不考虑standby队列， 将得到Greedy algorithm 模型 考虑standby队列， 将得到效用函数模型模型的建立（5）－过山车null最简单的情况： 只有一条队列，即所有的人都只用FastPass系统 为了防止前面的人等的时间太长，过山车只要载满一定数量的人后就开车，假设为80％c。 用贪心算法（greedy algorithm),将每个顾客尽量安排在离顾客到达时间最近的，且还没有安排满人的一班车上。 假设被安排的顾客按照Beta分布到达所被安排的时间段内 模型的建立（5）－过山车模型null贪心算法 模型的建立（5）－过山车模型null很容易想到，全局优化的目标变量 1. 如果开车的时间不固定，则a%是多少最优？就是说顾客坐满多少就开车？ 2.如果开车的时间间隔是固定的，则多长时间开一次是最优的？ 衡量的标准：目标函数 模型的建立（5）－过山车模型一个区间内的顾客返回示意图一个区间内的顾客返回示意图： null 目标函数：模型的建立（5）－过山车模型null模型的建立（5）－过山车模型怎样求解最优的a%c和最优的开车间隔？ －－对于这类复杂的问题，离散仿真是最好 的方法了null仿真：用计算机生成一些符合某种分布的随机数据点，模拟离散时间的发生 这里的仿真用MatLab6.5完成： 步骤：1.生成Poisson顾客流（模拟到达时间） 2.给定不同的a%c, 开车时间间隔不定，计算代价函数，画出代价函数性能曲线 3.开车时间固定，给出不同的开车时间间隔，计算画出代价函数性能曲线 4.得出最优的结论 模型的仿真（5）－过山车模型null 过山车模型的仿真（5.1）－得到在第j天的某一固 定时刻 i 采集样本, i=1…m, j=1…100 形成样本空间的 矩阵 null 过山车模型的仿真（5.1） 用列向量的均值 估计参数 样本的更新用时间序列的方法（time serial analysis）,计算列向量的Eucilid距离 d>threshold就更新一次 null 对某一个或一组变量x(t)进行观察测量，将在一系列时刻t1, t2, …, tn (t为自变量且t1 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 更好的FastPass系统null怎样写数学建模论文？ 怎样求解没有显式表达的式子？ 如何模拟离散随机时间？ 如何通过仿真的结果求参数的优化 －－使用数学软件，仿真的过程中常常也会的到新的想法与结论 灵活借鉴其他学科中的方法：如Queueing theory(排队论), Trunking Theory(复用论), Greedy Algorithm（贪心算法）, Marginal Utility Function(边际效用函数) 9 启发与收获这是一类OpenEnd Problem这是一类OpenEnd ProblemHomework: 相似的问题比如ICM2003 C题， To Screen or not to screen? –飞机场的调度以及安全检查问题 你将如何安排？ Its upto you! 感谢（Acknowledgement）感谢（Acknowledgement）本次讲座内容来自MCM2004#team624的paper,感谢全体成员的辛勤工作！以及杨老师的指导与支持。 paper下载：http://mail.ustc.edu.cn/~xieyao/MCM2004_B.pdf