排队,过山车

QuickPass系统 排队问题谢瑶 03/03/2004 xieyao@http://www.77cn.com.cn 电子工程与信息科学系PB00006

排队常常是件很令人恼火的事情……尤其是在我们这样的人口大国

电话亭-1978年在北京15%的电话要在1小时后才能接通。

在电报大楼打电话的人还要带着午饭去排队

银行窗口，ATM 医院、理发、火车售票… 游乐场的游乐项目

?

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

What is QuickPass? 1.

2.

3.

工作原理： 到达的顾客将自己的票插 入FastPass的slot中 FastPass计算出建议顾客 返回的时间间隔(time interval)或时间点或时间 窗(time window) 顾客无需排队，在指定的 时间返回就可持票进入

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

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

我们的目的就是对FastPass系统建立合理的离散统计模型(Distributed Statistical Model),求出最优的顾客返回时间。建模的一般步骤问题的假设与分析

模型的建立

以及： * 模型的改进 * 启发与待解决的问题

模型的求解与仿真

模型稳健性、优缺点 分析

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)是 独立增量过程，(iii) t>0,s 0, ( (t )t ) k e t P{N(s+t)-N(t)=k}= , k 0,1, 2...... k!

Poisson Process

ti 顾客到达时间间隔~(t)exp( (t)t) Ti顾客i接受服务的时间 ~ exp( t )

(t)和 的确定都将在后面仿真的部分给出

2 在我们开始动手建模之前， 先要问几个问题： 分析1:能否得到准确的返回时间？如果能够准确得知前面所有顾客的到达时间间 隔ti和接受服务的时间Ti (i 1...m),当然可以知道 第m 1个顾客到达就可以马上接受服务的时间隔 t1,m+1 ......可现在ti和Ti都是随机变量，我们只 能用随机过程的方法，求出t1,m+1 期望值。~ ~

2 在我们开始动手建模之前， 先要问几个问题：分

析2:使用FastPass后排队是不是可以避免的？ FastPass给出的返回时间只是期望值，而非确定 值 假设所有的顾客都使用FastPass,但需考虑有的顾 客可能会不遵守FastPass给出的返回时间

结论：使用FastPass后顾客仍需排队，但是排队的时间会大大减少。 并设第m+1个顾客排队的时间是t2,m+1

2 在我们开始动手建模之前， 先要问几个问题： 分析3:我们优化的目标函数(或cost function)是什么？是排队时间吗？1.FastPass给出的顾客i的等待时间t1,i 太长,同样会引 来抱怨,并且不能超过公园的开放时间Tw 2.排队的时间t2,i也要考虑 但是后者引来的抱怨更大；而且等待的时间越长，抱 怨越多...... 结论：目标函数应该是两者的时变加权和(time-variant weighted average)~

3 模型的建立(1)-目标函数 优化问题的目标函数为：

z min{E{U c1 (t ) t1 c2 (t )t2 }}~ i t j t1,i Tw j 1 s.t. ~ ~ t1,i ti 1 t1,i 1 Tw公园一天的开放时间

~

3 模型的建立(1)-目标函数

模型的建立(2)- 排队模型的分类

根据排队论(queueing theory)的分类规则,(X/Y/Z/A)代 表一类排队的规则，其中 X:顾客流到达所符合的分布 Y:顾客接受服务的时间所服从的分布 a Z:服务台的个数 A:服务台一次可服务的顾客数量(系统的容量) 针对各个游乐项目的特点，我们主要讨论两种排队系统:

电话亭(phonebooth)的M / M /1/ 队列模型和 过山车(scenic railway)的M / M / c / a% c队列模型

模型的建立(3)- 电话亭模型

特点：系统容量为1,顾客的到达是Poisson流，服 务时间服从指数分布，只有一条队列

模型的建立(3)-电话亭模型

加入QuickPass系统以后的Poisson排队模型T5 t3,1 t3,2 T3 T4

T1 t1 t2 E2

T2 t3 E3 t4 t5

模型的建立(3)-电话亭模型

求出这类系统的代价函数表达式第n个顾客的返回时间：An tn t 1,nj 1 n ~

Ek 是第k个顾客可以接受服务的时刻 Pi是队列中的顾客i仍会停留的时间( 包括使用系统的时间)t2,( n ,k ) ( Ek

i k 1

n 1

Pi An ) *

x, x 0; ( x) 0, x 0.*

本文来源：https://www.bwwdw.com/article/w7hi.html