中国科学技术大学：QuickPass系统的排队问题（PPT讲座，谢瑶）

QuickPass系统 排队问题 谢瑶 03/03/2004 xieyao@mail,ustc.edu.cn 电子工程与信息科学系PB0006

QuickPass系统 排队问题 谢瑶 03/03/2004 xieyao@mail.ustc.edu.cn 电子工程与信息科学系PB00006

排队常常是件很令人恼火的事情 尤其是在我们这样的人囗大国⊙ 今电话亭-1978年在北京15%的电话要在1小时后才能接通 在电报大楼打电话的人还要带着午饭去排队 今银行窗口,ATM 医院、理发、火车售票. 今游乐场的游乐项目

排队常常是件很令人恼火的事情…… 尤其是在我们这样的人口大国 ❖ 电话亭－1978年在北京15%的电话要在1小时后才能接通。 在电报大楼打电话的人还要带着午饭去排队 ❖ 银行窗口，ATM ❖ 医院、理发、火车售票… ❖ 游乐场的游乐项目 ?

4在游乐园中的频频排队 会极为扫兴 Disney Land中 的 FastPass ( QuickPass)系统 就是想解决这 个问题的

❖ 在游乐园中的频频排队 会极为扫兴…… ❖ DisneyLand中 的FastPass (QuickPass)系统 就是想解决这 个问题的

What is QuickPass? 今工作原理: 1.到达的顾客将自己的票插 入 FastPass的sot中 2. FastPass计算出建议顾客 返回的时间间隔(tme interval)或时间点或时间 窗( time window) 3.顾客无需排队,在指定的 时间返回就可持票进入

What is QuickPass? ❖ 工作原理： 1. 到达的顾客将自己的票插 入FastPass的slot中 2. FastPass计算出建议顾客 返回的时间间隔（time interval）或时间点或时间 窗（time window） 3. 顾客无需排队，在指定的 时间返回就可持票进入

怎样缩短排队的等待时间? 银行的排队叫号机 只是有序的组织了顾客,并没有减少等待时 如果能实现知道轮到自己需要等待多少时间, 再选择合适的时间来,岂不很好?

怎样缩短排队的等待时间？ ❖ 银行的排队叫号机 只是有序的组织了顾客，并没有减少等待时 间 ❖ 如果能实现知道轮到自己需要等待多少时间， 再选择合适的时间来，岂不很好？☺

FastPass存在的问题 预知的返回时间间隔在在差 按时返回却仍冒 现有的 Fast Pass 真的那么好用吗? 建议的返回时义义 如果告诉你4小 人呢 今顾客可能不会完全按照安排的时间返回 如果新来的顾客不想使用 FastPass系统?

FastPass存在的问题： ❖ 预知的返回时间间隔存在误差 －－按时返回却仍需要排队 ❖ 建议的返回时间间隔太长 －－如果告诉你4小时以后再回来呢？ ❖ 顾客可能不会完全按照安排的时间返回 ❖ 如果新来的顾客不想使用FastPass系统？ 现有的Fast Pass 真的那么好用吗？

我们的目的就是对 FastPass系建立 合理的离散统计模型( Distributed statistical Mode),求出最优的顾客返回时间。 建模的一般步骤 问题的假设与分析 模型的建立 以及: 模型的改进 模型的求解与仿真 米启发与待解决的问题 模型稳健性、优缺点 分析

我们的目的就是对FastPass系统建立 合理的离散统计模型（Distributed Statistical Model），求出最优的顾客返回时间。 建模的一般步骤 以及： * 模型的改进 * 启发与待解决的问题 问题的假设与分析 模型的建立 模型的求解与仿真 模型稳健性、优缺点 分析

1模型的假设 游乐园开放时间为8:00-18:00,一天中不同时 间的顾客流量不同,比如上午10:00和下午 3:0的顾客流量是最大的 顾客的到达时间符合非时间齐次泊松过程 Nonhomogeneous Possion Process),到达 速率是t)

1 模型的假设 ❖ 游乐园开放时间为8:00-18:00,一天中不同时 间的顾客流量不同，比如上午10:00和下午 3:00的顾客流量是最大的。 ❖ 顾客的到达时间符合非时间齐次泊松过程 (Nonhomogeneous Possion Process)，到达 速率是 （t）

Poisson process 整数值的随机过程{N(t),t≥0}是强度为的 Poisson过程,如果(i)N(0=0,(ii)N(t是 独立增量过程,(ⅲ)Ⅴt>0,s≥0, PIN(S+t)N(t)=kh ((t))e k=0.1.2 k!

Poisson Process iii ( ( ) ) , 0,1,2...... ! k t t t e k k    −    = 整数值的随机过程{N(t),t 0}是强度为 的 Poisson过程，如果（i）N(0)=0,(ii)N(t)是 独立增量过程，（ ） t>0,s 0, P{N(s+t)-N(t)=k}=

Poisson process T5 T4 T3 T2 T1 t2 t3 t4 t5 1顾客到达时间间隔~(t)exp((t)t) T顾客接受服务的时间~exp() (t)和的确定都将在后面仿真的 部分给出

Poisson Process ~ exp( ) i t i t       i 顾客到达时间间隔～（t）exp( (t)t) T顾客 接受服务的时间 （t）和 的确定都将在后面仿真的 部分给出