美赛资料汇总2017年美赛D题

For office use onlyT1 T2 T3 T4 Team Control Number67316Problem ChosenDFor office use onlyF1 F2 F3 F4 2017MCM/ICMSummary Sheet(Your teams summary should be included as the first page of your electronic submission.)Type a summary of your results on this page. Do not include the name of your school, advisor, or team members on this page.SummaryBottlenecks that passengers take time to take care of their carry-on properties before X-ray scanning and that the structure of the checkpoints is not satisfying are spotted, and detailed recommendations for the airport security management to raise throughput of the security checkpoints, to improve the passengers satisfaction and to keep the cost relatively low are given with cultural factors quantied and their impacts on the models discussed.在Bottlenecks机场，乘客在经过X光扫描之前，花时间去照看他们随身携带的行李，然而，机场发现他们的安检站的构造并不能满足乘客的需求。于是，一份为安检管理部门提高安检的工作效率，提升乘客的满意度以及保证花费很低的并且考虑到了文化因素的详细的计划书被给出 。(/)(/ /)Poisson queueingin Kendall notation, and Erlangian processis concernedin the scan check process. Numeric solution ofnique.is introduced using simulation tech-We divided the security check process into two phases and regard the entire as two queueing models in series. By analyzing the giv(en /dat/a), the document check is found to be a 我们把安检分为两个阶段并且按照顺序建立了两个排队模型。通过分析给出的数据，我们发现其满足泊松排队论模型（M/M/c），以及爱尔兰排队论模型（M/Ek/C）被考虑用于检查过程中。我们将用仿真技术介绍(M/Ek/c)模型。Assumed that arrivals of passengers for a ight obey normal distribution, the varyingulation. We also believe that the mean and the variance of the distribution is culture-re-passenger ow in a period of time can be generated from the real data and used for our sim-lated. We also nd that the passenger ow can be changed by recommending the passengers their arrivals, and thus better result of the passengers waiting time can be achieved。假设到达的旅客服从正态分布，而其余变化的旅客的流量我们可以根据真实的数据进行仿真得到。我们也相信旅客的流量的中值与方差也会受到文化因素的影响。我们发现客流量会因为到达乘客的建议而改变，因此减少乘客的等待时间的计划是可以实现的。We also suggested several methods to improve the design of the checkpoint, including shortening the distances between identical checkpoints and more rational human resource allocation.我们同样提出了几个建议去改善安检地的设计，包括缩短两个安检站的距离以及理性的人力资源分配。Virtual queueing is recommended as an approach to improve passengers experience, and modify the conventional First In First Service queueing discipline to partial priority queueing discipline as well. A partial priority queueing discipline is put forward to reduce the remaining time variance of the passengers and to decrease the number of passengers that missed their ights, thus better passenger satisfaction is reached.虚拟的排队也被用于提高旅客对排队的体验，并且将传统的先进先出的排队规则修改成了局部的优先化。一个局部优先化的排队规则可以减少其余旅客的工时差异，也可以减少误机的旅客的数量，这样便达到了一个更好的旅客满意度。We also introduced culture-related factors for passenger arrival recommendation and pri- ority queueing discipline. For the latter, an “acceptability factor” named is used to denotethe acceptability of strict priority discipline. And the examples of dierent cultures are given to illustrate this idea. 我们同样介绍了已到达旅客的建议以及部分优先原则考虑到文化因素的影响。对于部分优先原则，一个可以被接受的因素被命名为严格优先级的排队规则。并且，不同的文化示例也在我们的论文中被给出。Validation of each model are made in our essay to make them convincing. We later assess the models and give a complete guide for the security managers to optimize the airport secu- rity check workow. Weaknesses and further work that is not implemented in our essay are also pointed out. 在这篇论文中，我们给出了每个模型的有效性检验。也就是说，我们之后会评价模型并且会给出一个完整的指南为机场的安检部门优化安检站的分布。缺点以及并未实施的工作也在这篇论文中被给出。Team #67316Page 7 of 20Time Counts! Less Waiting & Better AirportsIntroduction1.1 BackgroundAirport security check has been improved ever since the 911 attack. Although enhanced secu- rity means safer ights, however the complicated procedure may also increase the passengers waiting time and add cost to the U.S. Transportation Security Agency (TSA). Under some extreme circumstances, passengers have to wait for hours (and they are often recommended to be earlier for 23 hours, which often lead to confusion). Thus, to shorten the passengers waiting and designing a more ecient security check procedure is vitally important.机场的安检工作变得越来越重要，自从911事件之后。即使加大安检意味着更安全的航班，可是复杂的步骤也会增加乘客的等待时间以及美国运输安全局（TSA）的花费。 在一些极端的环境下，乘客不得不等待几个小时（他们通常会被要求早2到3个小时到达机场，这样经常会造成混乱。）因此，减少旅客的等待时间和设计一个更有效的安检步骤是很重要的。 TSA is now in controversy for causing long queues waiting for security check. We, the Internal Control Management (ICM) team, trying to nd a solution, faces the problems below:1. Identify the bottlenecks of the current security check workow.2. Improve the process with modications, and illustrate how the modications work.3. Find how to allow the modied process to be compatible with dierent culture back- grounds and lower the variance of the passengers waiting time.4. Make suggestions on the policy for the security manager, with concern of the former requirements and corresponding models. 安检中排的长队在TSA引起争议。我们ICM团队，试图为以下问题找到解决方法。1. 为伯克利机场确定正确的排队流程。2. 改善排队流程，并且举例说明如何改善。3. 找出怎样使改善过的模型适应不同的文化背景以及减少不同的旅客的等待时间。4. 基于前者的需求以及建立好的模型，为安检部门指定一定的政策。1.2 Analysis and Approach Overview 分析与方法的综述.For problem 1, we divide the security check process in two parts: Phase 1, document check; and Phase 2, luggage and body scanning. The former is a Poisson queue, while the latter concerns an Erlangian model. Simulation is practiced as a means of solving multi-server Er- langian model. By testing the total waiting times sensitivity to changes on numbers of parallel servers in the two phases respectively, the bottlenecks of the workow can be spotted. 对于问题一我们把安检分为两部分，第一部分是证件检查，第二部分是行李以及随身扫描。前者为泊松排队模型，后者为爱尔兰排队模型。仿真被训练为解决多服务器的爱尔兰模型。通过测试整个排队时间的敏感性去改变各自的同类服务器，伯克利飞机场的工作流程大体就出现了。To solve problem 2, considering the inuential factors of a queueing process, modications will be put forward to optimize and avoid congestions.为了解决问题2，考虑到排队进程因素的影响，模型将会进行最优化以及避免拥塞设计。The current TSA recommended passengers arrival time is used to build a model of the passenger arrival behavior at an airport, and we assume the arrivals in time for one certain ight obey normal distribution, and in a small time interval, the arrivals of all passengers for all ights obey an exponential distribution. We will modify the arrival recommendation strategy to inuence passengers arrival behavior.现在TSA推荐旅客的到达机场时间将会用于建立乘客到达机场的行为，然后，我们假设旅客到达时间遵循正态分布，并且，在一个很短的时间间隔中，到达的旅客以及到达的航班呈现指数分布。我们将会修改对到达者的建议从而影响乘客的到达时间。Another direction to improve the current process is to provide more robust security check service with greater capacity. A few suggestions and their verication or explanation will be given. 还有一个方案去改善当下的排队进程就是在能力允许范围内，提供更健全的安检服务。一些建议和他们的可行性或者说是解释，将会在后面给出。 Besides the performance, justiability also counts. Virtual queueing under other disciplines (Zhao, et al., 2016) will be a good practice. Queueing discipline modication is culture-sensitive, and thus lead to the discussion of the third problem.The following diagram illustrate the above ideas in a more visual way。 除了绩效，他们的合理性也应该进行计算。基于其他规则的虚拟的排队体系如下图所示将会是一个很好的做法。修改排队模型的规则是基于文化敏感性和因此导致的第三方的问题的讨论。 接下来的图标将会以一种更直观的方式解释以上所说内容。Figure 1 Optimizing directions and our modications,where “service pattern” concerns the service rate and number of servers.Assumptions1. Individual variability is not considered for the servers, the checkpoint structures, etc.2. Although the number of lanes opened in the scan check process is dynamic, we assume that the service capability is always at its maximum. That is to say, spare lanes will be open, so long as the arrival exceeds the current capability.3. Assume that every passenger will choose to wait in the queue that minimizes their waiting time at every checkpoint.4. Points in time that passengers arrive at the airport for a certain ight obey normal distribution.5. TSA Pre-check wont contribute much to the congestion compared with the normal one.6. Almost everyone would arrive at the the airport for at least half an hour.See 4.1 Security Check ProcessOverview, and 4.3 Queueing Model Specication for de- tailed interpretation and assumptions of the given datasheet1.假设服务是一视同仁的。2.即使安检的打开的线路是动态的，我们假设安检的服务能力是最大的。也就是说，只要旅客超过当下容量，我们将会打开空余的安检线路。3.假设旅客会选择让他们等待时间最短的安检站。4.为某一个航班到来的旅客的时间点乘正态分布。5.TSA的预检查并不会造成很大的拥塞与之前的比较。6.大家都将提前至少半个小时到达机场。了解4.1节安检方法-综述，以及4.3节 排队模型假设，会详细说明已给数据表的假设以及解释。Symbols and NotationsSymbol or NotationSpeciftcationKendall notation, whereanddenote the inter-arrival-time distribution, the service time distribution, the number of parallel servers,queueing discipline, restriction on system capacity, and the source of the arrival (usually innity) respectively. (Taha, 2014)Denote an exponential distribution for inter-arrival time and service time,i.e. a Poisson distribution for arrival and remove rate. Erlang distribution type .Estimated value of .Arrival and service rates of the scanchec1k process.Normal distribution with mean ,0and variance.Arrival and service rates of the document check process.Queueing Model for Security Check Process为安检站建立的排队模型4.1 Security Check Process-Overview安检站综述Figure 2 TSA Security checkpointThe detailed security check process of one single checkpoint given in the diagram above. Ac- cording to TSAs policy, we classify the security processes in two types (pre-check included and no pre-check concerned process), and divide the each process in two queueing phases. In Phase 1, the passengers identity documents will be checked, after which they enter Phase 2, where luggage and body screening will be accepted. Two dierent types are in essence the same queueing with dierent parameters (number of servers, service time, etc.). And the entire security check process can be seen as two queueing models in series. 一个安检站安检过程的细节用图解的方式表示如上。根据美国运输安全局的政策，我们把安检过程分为两个类型（预安检以及无预安检）,并且把每个过程又分为两个排队阶段。在第一阶段，乘客的证件检查，检查过关后，他们将进入第二阶段，行李以及随身检查。两种类型本质上他们的排队时相同的，只是参数不同。(例如：服务类型，服务时间等). 整个安检流程可以用两个连续的排队论模型表示。为了更好的表示整个过程，我们给出了如下流程图。 To better clarify the whole process, a procedure sequence diagram is given below:Figure 3 排队流程图A: 等待证件检查所需时间 B: 证件检查时间C:：行李检查的等待时间 D: X射线检查时间 E: 其他可能的行李检查时间F：毫米波检测时间 G: 身体扫描时间, H: 其他可能的身体检查时间描黄部分为第一阶段检测时间，其余为第二阶段检查时间。The given Excel datasheet contains time records of the airport checkpoints (whose dier- ences denote the inter-arrival time), time taken of the ID check process of previous checked passenger (i.e. B in the diagram), millimeter wave scan timestamps (dierences of which are the millimeter wave scanning time, shown as G in the diagram), timestamps that luggage getting out of the X-ray scan (dierences denote E), and time to get scanned property (D, E, F, G, H). 给出的EXCEL数据包括机场检查点的时间记录（不同点表示到达间隔时间），检查ID过程的实际时间取决于之前的旅客，比如图中的B。毫米波的时间戳（比如图中的G），行李经过X光的时间（与E不同），去扫描的时间（D,E,F,G,H）。By analyzing the given datasheet, patterns of the airport security check behaviors, such as the distribution of passengers inter-arrival time and service time at each section, can be dis- covered. Therefore a complete queueing model can be specied.通过分析已给数据，机场安检模式的行为，比如：包括旅客到达间隔时间的分布和每个环节的服务时间等。因此，我们可以说明一个完整的排队论模型。4.2 对TSA officers进行显著性检验 已给的数据包括两个不同安检人员的时间此时的显著性检测是为了证明人员的变动并不会对服务时间造成很大的影响。 假设两个人的服务时间的方差是相同的，即 12= 22= 2. 我们使用零假设 H0 用于表示两个人员的服务时间的期望是相同的，即 1=2. 两个样本的协方差，Sw2 =12.927. 在5%的显著水平下，x1-x2 Sw 1n1+1n2=1.375 t0.025(14)=2.145.不拒绝零假设。 假设证件检查服务时间遵守指数分布，那么，参数的分布比如服务比率是可以估计的 ud=0.09465. 4.3 排队论模型的说明。 这两个过程可以通过给出的到达和服务时间建立连续的排队模型3020251520101510550020406080001020304050Figure 4 不进行检查的到达者的频率直方图Figure 5 提前检查的到达者的频率直方图根据以上的频率直方图，我们假设时间间隔都是规律的和接受预检的到达者遵守正态分布 fx=d e-d x.参数的极大似然估计 d ：Ld=i=1nf(xi)=i=1nd e-d xi=dne-d i=1nxi ln L(d)=n ln d-d i=1nxi , dlnL(d)d d= nd - i=1n xi=0 .因此，d = ni=1nxi = 1xi , 期望值： d= 1xi =1(x) = d , 是一个准确的估计值。因此，到达者速率和预检测程序的估计为 1=0.077244 和 2=0.10882016 此时，做了一个好的适应性测试，每个程序被分为10个等级， 于是，我们做了一个正常的过程作为例子。Table 1 Regular procedure, non-pre-check, true frequencies and predicted frequenciesClass0-88-1616-2424-3232-4040-4848-5656-6464-7272-80True Frequency211363001101 Predicted Probability0.4610.2480.1340.0720.0390.0210.0110.0060.0030.002 Predicted Frequency21.20411.4306.1613.3211.7900.9650.5200.2800.1510.0812=i=110Ni-npi n pi =15.898 X0.0529=16.919因此，我们考虑上述分布为指数分布。预检查过程与此类似，此时2=15。599 X0.0529=16.919.因为到达间隔时间，遵守指数分布，到达旅客的数目遵守泊松分布。4.3.2 排队说明 我们同样考虑阶段一的服务时间遵守指数分布，同样用排队论理论对样本做训练以及服务速率结果如下。 d=0.09465 基于以上讨论，阶段一遵守（M/M/c）排队论模型，M为泊松过程，c为服务的数目，到达者速率基于已知的速率，C给于机场安检站的背景。我们假设每个服务的服务速率为一常数 d=0.09465 。4.3.3 阶段2因为两个排队论模型是连续的，于是有 s =d，阶段二是多服务器模型，但是服务过程更加复杂，右侧的频率直方图明显表示不遵守指数分布。 我们将简单介绍爱尔兰模型，安尔兰服务模型广泛使用于服务过程， Team #67316Page 7 of 20Queueing Simulation and Bottlenecks Spotting5.1 Estimating ExpensesAccording to (L; PayS), income of a security ocer is $28,624$58,987 and of an airline security screener is $23,262$54,015. That is the human resource expenses of the security check. Costs of security devices are mostly one-o consumptions. The price of an airport X-ray baggage scanner is at $20,00050,000 and of a millimeter wave full body scanner is at $100,000 (A). And the maintenance cost is mainly from the electricity. Another fact is that one single lane of the scan check process requires 4 security screeners on average. Therefore, we drew a conclusion that the cost of one lane (server) in Phase 2, is about the cost of 4 desks (servers) at Phase 1.5.2 Basic IdeasA MATLAB program is written to simulate the entire security check process. To build up the numeric solution, Markov chains are used for Erlangian queueing. (Zeng, et al., 2011)Figure 7 MATLAB simulation specicationSince there is no analytical solution of an ( /)Team #67316Page 8 of 20(Phase 2) queueing model, a simulation of the entire security check process is put forward, and both Phase 1 and Phase 2 are concerned in the model in series.Given the parameters of each probability distribution at the two phases, we generate series of random variates to simulate the process. First, random variates obeying exponential distri- bution is generated as peoples inter-arrival time. We then calculate and store the arrival timestamps, service time (generated random variables obeying another exponential distribution) and waiting time (worked out with the previous passengers waiting time, service time and the arrival interval) of each passenger in a table. Besides getting results of waiting time spans, the removal rate of Phase 1 is also observed, which is used as the arrival of Phase 2. After working on Phase 1, we do the same on Phase 2, but the new service is Erlangian. Finally, expectations of total waiting time are evaluated.To spot the bottlenecks in the process, we tested the improvements of total waiting time expectations when 4 document check servers are added (row “Document Check Added” in the table below), and 1 scan check server is added (row “Scan Check Added”).5.3 Spot the Bottlenecks!is assigned = 0.09465, and that of one scan check service is = 0.0357. Service of Phase 2 = 4The simulated security process has a changeable arrival rate , and both of the initial numbers of the document check servers and of the scan check servers are assigned 5, as is the case in Figure 2, which is a small scale for an airport. The service rate of one document check serveris Erlangian type. These three parameters are the same to what we have mentionedbefore.ument Check Added” for the case that 4 document check servers are added, that is ( / /9)is the total waiting time expectation of process consist of ( / /5)nd ( /5). Row “Doc-Below lists the expectations for total waiting time at dierent arrival rates. Row “Original”aadded, that is ( / /5) and ( /6).for Phase 1 and ( /5) for Phase 2. For row “Scan Check Added”, 1 scan check server is3.2473.7104.3294.4784.6384.8105.194Original31349226321278110807898873913668Document Check Added31092218781183210671892572153291Scan Check Added1825810643304516802718824Table 2 Simulation results of the total waiting time (in seconds) = 5.194We nd that, the document check process is not the bottleneck of the process, but the scan check. By adding scan check lanes, service capability of the whole system is signicantly in- creased. We can even observe that some divergent queueing cases converge (e.g.).Team #67316Page 19 of 205.4 CommentsBased on the above analysis, bottlenecks restricting the queueing capacity and eciency comes from the scan process Phase 2. From the given data, we see that the X-ray scan time is usually fast and steady, and is not likely to be the bottleneck. However, time taken for the passenger to take o clothes and to take care of their carry-on properties contribute much to the next passengers waiting (time C in Figure 3), especially when someone is heavy with carry-on properties or not experienced in air travelling.We would recommend the airport to allow the passengers to take a bin for their to-be- scanned properties before queueing, and thus waiting time in P