数学建模――排队问题

QuickPass系统排队问题谢瑶03/03/[e-mail]电子工程与信息科学系PB00006排队常常是件很令人恼火的事情……尤其是在我们这样的人口大国电话亭－1978年在北京15%的电话要在1小时后才能接通。在电报大楼打电话的人还要带着午饭去排队银行窗口，ATM医院、理发、火车售票…游乐场的游乐项目?在游乐园中的频频排队会极为扫兴……DisneyLand中的FastPass(QuickPass)系统就是想解决这个问题的WhatisQuickPass?工作原理：1.到达的顾客将自己的票插入FastPass的slot中2.FastPass计算出建议顾客返回的时间间隔（timeinterval）或时间点或时间窗（timewindow）3.顾客无需排队，在指定的时间返回就可持票进入怎样缩短排队的等待时间？银行的排队叫号机只是有序的组织了顾客，并没有减少等待时间如果能实现知道轮到自己需要等待多少时间，再选择合适的时间来，岂不很好？FastPass存在的问题：预知的返回时间间隔存在误差－－按时返回却仍需要排队建议的返回时间间隔太长－－如果告诉你4小时以后再回来呢？顾客可能不会完全按照安排的时间返回如果新来的顾客不想使用FastPass系统？现有的FastPass真的那么好用吗？我们的目的就是对FastPass系统建立合理的离散统计模型（DistributedStatisticalModel），求出最优的顾客返回时间。建模的一般步骤以及：*模型的改进*启发与待解决的问题问题的假设与分析模型的建立模型的求解与仿真模型稳健性、优缺点分析1模型的假设游乐园开放时间为8:00-18:00,一天中不同时间的顾客流量不同，比如上午10:00和下午3:00的顾客流量是最大的。顾客的到达时间符合非时间齐次泊松过程(NonhomogeneousPossionProcess)，到达速率是（t）PoissonProcessiii(()),0,1,2......!ktttekk整数值的随机过程{N(t),t0}是强度为的Poisson过程，如果（i）N(0)=0,(ii)N(t)是独立增量过程，（）t0,s0,P{N(s+t)-N(t)=k}=PoissonProcess~exp()ititi顾客到达时间间隔～（t）exp((t)t)T顾客接受服务的时间（t）和的确定都将在后面仿真的部分给出分析1：能否得到准确的返回时间？(1...),1immii~1,m+1ii~1,m+1如果能够准确得知前面所有顾客的到达时间间隔t和接受服务的时间T当然可以知道第个顾客到达就可以马上接受服务的时间隔t......可现在t和T都是随机变量，我们只能用随机过程的方法，求出t期望值。2在我们开始动手建模之前，先要问几个问题：分析2：使用FastPass后排队是不是可以避免的？FastPass给出的返回时间只是期望值，而非确定值假设所有的顾客都使用FastPass,但需考虑有的顾客可能会不遵守FastPass给出的返回时间2在我们开始动手建模之前，先要问几个问题：FastPass2,m+1结论：使用后顾客仍需排队，但是排队的时间会大大减少。并设第m+1个顾客排队的时间是t分析3：我们优化的目标函数（或costfunction）是什么？是排队时间吗？2在我们开始动手建模之前，先要问几个问题：1.FastPass~1,iw2,i给出的顾客i的等待时间t太长,同样会引来抱怨,并且不能超过公园的开放时间T2.排队的时间t也要考虑但是后者引来的抱怨更大；而且等待的时间越长，抱怨越多......结论：目标函数应该是两者的时变加权和（time-variantweightedaverage）优化问题的目标函数为：~1122~1,1~~1,11,1min{{()()}}..ijiwjiiiwzEUcttcttttTsttttT公园一天的开放时间3模型的建立（1）－目标函数3模型的建立（1）－目标函数根据排队论（queueingtheory）的分类规则,（X/Y/Z/A）代表一类排队的规则，其中X:顾客流到达所符合的分布Y:顾客接受服务的时间所服从的分布aZ:服务台的个数A:服务台一次可服务的顾客数量（系统的容量）针对各个游乐项目的特点，我们主要讨论两种排队系统:模型的建立（2）－排队模型的分类//1////%MMMMcac电话亭（phonebooth）的队列模型和过山车（scenicrailway）的队列模型特点：系统容量为1，顾客的到达是Poisson流，服务时间服从指数分布，只有一条队列模型的建立（3）－电话亭模型加入QuickPass系统以后的Poisson排队模型模型的建立（3）－电话亭模型t1t2t3t4t5T4T5T1t1t2t3t4t5T2T3T4T5T1E2E3t3,2t3,1求出这类系统的代价函数表达式模型的建立（3）－电话亭模型12,(,)1()*nnkkiniktEPA*,0;()0,0.xxxx~1,1nnnnjkiAttEP第n个顾客的返回时间：是第k个顾客可以接受服务的时刻是队列中的顾客i仍会停留的时间（包括使用系统的时间）近似将总的优化目标函数等效为对顾客i的目标函数：模型的建立（3）－电话亭模型~11,22,1~11,2,2,(,)0,min{{()()}}min{{}}()nnnnnnknkknkzEUcttcttcEtcQtQPnk其中，顾客前有个顾客在排队,111,2212,1111111,1,1,1,1,11(()(......),,,(1),(),(0)kkknkkkknkskskksnkkkkkkkkkkkikikikikkkiniQPEPAQPEPPAQPEPPAAAEPEEPAEPQQQQQPAE下面求出状态转换平衡状态方程：）且模型的建立（3）－电话亭模型如果简化c1,c2为常数，并计算第二个人的无需等待返回时间的期望值，得用MatLab能够作出的函数，并从图中得出结果模型的求解（4）－电话亭模型~~~211,22121,221,2()(1())UctcPttNtt22wTtT0()1,0xtxtNxedtex~21,2()Ut模型的求解（4）－电话亭模型Averagecalltime(min*10’)U2t2508.051617.08023.051632.5第三个人的无需等待返回时间的期望值，同理可以算出，并用图解法求出模型的求解（4）－电话亭模型~~2,3231,31231,3231,321,231,31,21,2231,321,2231,312231,321,2231,312231,3(1())()()(()(1())()(1())(1())()(1())(1())()tNtttPtttNtttNttNttttPttNttGtttPPtttNttGtttPPttt但是第4个人，第5个人……呢？这种方法太繁琐，似乎不好用可否有近似的算法？与前一个模型的区别在于：系统容量是c1,服务时间固定，顾客的到达仍然是Poisson流。服务系统数量是1模型的建立（5）－过山车模型还要考虑：实际的FastPass系统有两条队列：FastPass和Standby队列不考虑standby队列，将得到Greedyalgorithm模型考虑standby队列，将得到效用函数模型模型的建立（5）－过山车最简单的情况：只有一条队列，即所有的人都只用FastPass系统为了防止前面的人等的时间太长，过山车只要载满一定数量的人后就开车，假设为80％c。用贪心算法（greedyalgorithm),将每个顾客尽量安排在离顾客到达时间最近的，且还没有安排满人的一班车上。假设被安排的顾客按照Beta分布到达所被安排的时间段内模型的建立（5）－过山车模型贪心算法模型的建立（5）－过山车模型Shift1Shift2Shift3很容易想到，全局优化的目标变量1.如果开车的时间不固定，则a%是多少最优？就是说顾客坐满多少就开车？2.如果开车的时间间隔是固定的，则多长时间开一次是最优的？衡量的标准：目标函数模型的建立（5）－过山车模型一个区间内的顾客返回示意图：目标函数：模型的建立（5）－过山车模型121121,,1,2,1,22,2212121212,,,,,..()()()()()(()kjjiijkkkkkjkjkjkkkjkkkjjkjkkkkkhhhbbbttzzEctctEctctcEEtcbEccEctcbccctcj-1i2,iii个人{}被安排在中的一班车设i个人的返回时间是则t121)()jjkkkbEccctk常数，由决定，222%,jjjjkjjcacbcbckb，如果开车时坐满的人数固定如果开车的时间间隔固定则＝常数模型的建立（5）－过山车模型怎样求解最优的a%c和最优的开车间隔？－－对于这类复杂的问题，离散仿真是最好的方法了仿真：用计算机生成一些符合某种分布的随机数据点，模拟离散时间的发生这里的仿真用MatLab6.5完成：步骤：1.生成Poisson顾客流（模拟到达时间）2.给定不同的a%c,开车时间间隔不定，计算代价函数，画出代价函数性能曲线3.开车时间固定，给出不同的开车时间间隔，计算画出代价函数性能曲线4.得出最优的结论模型的仿真（5）－过山车模型过山车模型的仿真（5.1）－得到在第j天的某一固定时刻i采集样本,i=1…m,j=1…100形成样本空间的矩阵11121,10021222,100,1,2,100................................................mmmlllllllll()t过山车模型的仿真（5.1）用列向量的均值估计参数样本的更新用时间序列的方法（timeserialanalysis）,计算列向量的Eucilid距离dthreshold就更新一次()it,1,2,100{[,...]}Tiiimeanlll'21()mkkkdll对某一个或一组变量x(t)进行观察测量，将在一系列时刻t1,t2,…,tn(t为自变量且t1t2…tn)所得到的离散数字组成序列集合x(t1),x(t2),…,x(tn)，我们称之为时间序列，这种有时间意义的序列也称为动态数据。时间序列分析是根据系统观测得到的时间序列数据，通过曲线拟合和参数估计来建立数学模型的理论和方法时间序列分析（timeserialanalysis）过山车模型的仿真（5.1）启发：有没有别的方法判别样本如何更新？如：求样本矩阵的秩，求样本向量的相关系数生成的样本空间过山车模型的仿真（5.1）实用的一种模拟Poisson流的方法：某个区间个顾客到达时间~Uniform()tPoisson流顾客到达时间过山车模型的仿真（5.2）按照贪心算法指定的顾客乘坐的过山车的班次两种a%c的情况下顾客等待时间过山车模型的仿真（5.3）a%c的性能曲线：可见a%c=70最优过山车模型的仿真（5.3）开车间隔的优化：可是costfunction是间隔的单调函数？怎么办？过山车模型的仿真（5.4）解决：考虑开车的成本：开车的时间间隔越短，次数愈多，运行成本越大－－找平衡点4.67min最优过山车模型的仿真（5.4）123456789100.511.522.53x104cycle