D2017年美国大学生数学建模竞赛O奖论文67316

For office use only T1 T2 T3 T4 Team Control Number 67316 Problem Chosen D For office use only F1 F2 F3 F4 2017 MCM ICM Summary Sheet Your team s 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 Summary Bottlenecks 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 quantifi ed and their impacts on the models discussed We divided the security check process into two phases and regard the entire as two queueing models in series By analyzing the given data the document check is found to be a Poisson queueing in Kendall notation and Erlangian process is concerned in the scan check process Numeric solution of is introduced using simulation tech nique Assumed that arrivals of passengers for a fl ight obey normal distribution the varying passenger fl ow in a period of time can be generated from the real data and used for our sim ulation We also believe that the mean and the variance of the distribution is culture re lated We also fi nd that the passenger fl 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 fl 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 denote the acceptability of strict priority discipline And the examples of diff erent 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 workfl ow Weaknesses and further work that is not implemented in our essay are also pointed out 更多数学建模资料请关注微店店铺 数学建模学习交流 Team 67316 Page 1 of 20 Time Counts Less Waiting 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 time s sensitivity to changes on numbers of parallel servers in the two phases respectively the bottlenecks of the workfl ow can be spotted To solve problem 2 considering the infl uential factors of a queueing process modifi cations will be put forward to optimize and avoid congestions 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 fl ight obey normal distribution and in a small time interval the arrivals of all passengers for all fl ights obey an exponential distribution We will modify the arrival recommendation strat egy to infl uence passengers arrival behavior Another direction to improve the current process is to provide more robust security check service with greater capacity A few suggestions and their verifi cation or explanation will be given Team 67316 Page 2 of 20 Besides the performance justifi ability also counts Virtual queueing under other disciplines Zhao et al 2016 will be a good practice Queueing discipline modifi cation 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 modifi cations where service pattern concerns the service rate and number of servers Assumptions 1 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 fl ight obey normal distribution 5 TSA Pre check won t contribute much to the congestion compared with the normal one 6 Almost everyone would arrive at the airport for at least half an hour See 4 1 Security Check Process Overview and 4 3 Queueing Model Specifi cation for de tailed interpretation and assumptions of the given datasheet Symbols and Notations Symbol or Notation Specifi cation Kendall notation where and denote the inter arrival time distribution the service time distribution the number of parallel servers Team 67316 Page 3 of 20 queueing discipline restriction on system capacity and the source of the arrival usually infi nity 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 document check process Arrival and service rates of the scan check process 1e d 0 2 Normal distribution with mean and variance 2 Queueing Model for Security Check Process 4 1 Security Check Process Overview Figure 2 TSA Security checkpoint The detailed security check process of one single checkpoint given in the diagram above Ac cording to TSA s 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 diff erent types are in essence the same queueing with diff erent 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 Team 67316 Page 4 of 20 Figure 3 Procedure sequence diagram A time waiting for the document check B document checking time C time waiting for sending luggage for X ray scanning D X ray scanning time E other possible luggage checks F time waiting for millimeter wave scan G body scan time H other possible body checks The yellow shaded part is Phase 1 as we introduced in previous paragraphs and the rest Phase 2 The given Excel datasheet contains time records of the airport checkpoints whose diff er 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 diff erences of which are the millimeter wave scanning time shown as G in the diagram timestamps that luggage getting out of the X ray scan diff erences denote E and time to get scanned property 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 specifi ed 4 2 Significance Test on Two TSA Officers The given datasheet involves timing of two diff erent TSA offi cers the signifi cance test here is to verify that individual variability does not contribute much to the service time Suppose that variances of the service time of the two TSA offi cers are equal 1 2 2 2 2 We make the null hypothesis 0 that service time expectations of both offi cers are the same i e 1 2 The combined sample variance of the two offi cers 2 12 927 At 5 level 1 2 1 1 1 2 1 375 0 025 14 2 145 the null hypothesis is not rejected Assume that the document check service time obeys the exponential distribution The pa rameter of the distribution i e service rate is estimated 0 09465 4 3 Queueing Model Specification The two phases of the process can be specifi ed as a series of queues by giving the arrival and service time distribution pattern ABCDE FGH Team 67316 Page 5 of 20 4 3 1 Arrival Figure 4 Frequency histogram of non pre check arrivals Figure 5 Frequency histogram of pre check arrivals According to the histograms above we suppose that the time intervals of both the regular and pre check arrivals obey exponential distribution e Maximum likelihood estimation of the parameter 1 e 1 e 1 ln ln 1 dln d 1 0 Therefore 1 1 and the expectation 1 1 is an unbi ased estimation Thus the arrival rates of the regular and pre check procedures are estimated to be 1 0 077244 and 2 0 10882016 respectively Here a goodness of fi t test is done and each of the procedures are classifi ed into 10 classes Let s take the regular without pre check procedure as an example Class 0 8 8 16 16 24 24 32 32 40 40 48 48 56 56 64 64 72 72 80 True Frequency 21 13 6 3 0 0 1 1 0 1 Predicted Probability 0 461 0 248 0 134 0 072 0 039 0 021 0 011 0 006 0 003 0 002 Predicted Frequency 21 204 11 430 6 161 3 321 1 790 0 965 0 520 0 280 0 151 0 081 Table 1 Regular procedure non pre check true frequencies and predicted frequencies 2 10 1 15 898 0 05 2 9 16 919 Thus we consider the above as an exponential distribution And similarly fi t for the pre check procedure 2 15 599 0 0 with the expectation and variance 2 Parameter and is related with and the service rate Gross et al 1985 1 Fit the distribution for the total service time in Phase 2 time to get scanned property our results are 4 0 0357 Therefore the Kendall notation of Phase 2 queueing is where the input is identical to the output of Phase 1 is an Erlang type 4 0 0357 distribution and the number of parallel servers i e the number of X ray scanners and millimeter wave scanners is depend on specifi c airport queueing does not have a good analytical solution our numerical solution using simulation technique will be introduced later 4 4 Section Summary The airport security check process consists of two phases fi rst of which is an queue ing process and the second is an queueing Arrival rate of the second is the service rate of the fi rst Parameters of the distributions can be estimated using the given data 020406080 0 000 0 005 0 010 0 015 0 020 0 025 0 030 Figure 6 Histogram of the service time in Phase 2 to gether with a PDF plot of an Erlang distribution Team 67316 Page 7 of 20 Queueing Simulation and Bottlenecks Spotting 5 1 Estimating Expenses According to Learn org PayS income of a security offi cer 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 off consumptions The price of an airport X ray baggage scanner is at 20 000 50 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 Ideas A 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 specifi cation Team 67316 Page 8 of 20 Since there is no analytical solution of an 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 people s 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 passenger s 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 The 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 server is assigned 0 09465 and that of one scan check service is 0 0357 Service of Phase 2 is Erlangian type 4 These three parameters are the same to what we have mentioned before Below lists the expectations for total waiting time at diff erent arrival rates Row Original is the total waiting time expectation of process consist of 5 and 5 Row Doc ument Check Added for the case that 4 document check servers are added that is 9 for Phase 1 and 5 for Phase 2 For row Scan Check Added 1 scan check server is added that is 5 and 6 3 247 3 710 4 329 4 478 4 638 4 810 5 194 Original 31349 22632 12781 10807 8988 7391 3668 Document Check Added 31092 21878 11832 10671 8925 7215 3291 Scan Check Added 18258 10643 3045 1680 271 88 24 Table 2 Simulation results of the total waiting time in seconds We fi 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 signifi cantly in creased We can even observe that some divergent queueing cases converge e g 5 194 Team 67316 Page 9 of 20 5 4 Comments Based on the above analysis bottlenecks restricting the queueing capacity and effi ciency 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 off clothes and to take care of their carry on properties contribute much to the next passenger s 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 Phase 2 will be reduced Comments on the Safety Firstly on the stand of the airport any security accident including terrorist attacks hijacking or aircraft destroying if happens will cause unbearable blame from the public opinion which is unacceptable for the airport Thus it does not sound like a good idea to reduce the links in security check procedure to fasten check in and to lower the expenses A fundamental principle of our later discussion is that no procedure in the security check chain is omitted Means like optimizing queueing processes arranging human resources guid ing passengers arrival can be implemented as ways to improve the passenger experience Passenger Arrival Behavior Modeling 7 1 Passenger Flow Generating Flight records of O Hare International Airport on Wednesday Jan 18 2017 were found on Flight Stats including the departure time and information of the plane models Most of the airlines are Boeing 737 800 whose capacity is usually 104 189 passengers To simulate the passenger arrival behavior i e the varying passenger fl ow in a time period we as sume that the capacity of every fl ight is about 189 and the points of the passengers arrival time obey normal distribution Since TSA recommends passen gers to be at the airport 2 hours earlier before the fl ight for domestic departures we model the passen gers arrival time for each fl ight to obey normal dis tribution 2 and let be 2 hours before the departure and 3 be the point in time that there is half an hour remained 0100200300400500600700 300 400 500 600 700 800 900 1000 Figure 8 Varying passenger fl ow in a time period from 6 30 a m to 16 40 p m O Hare International Airport Jan 18 2017 Team 67316 Page 10 of 20 We then add these PDFs together and get the dynamic passenger arrival data The shown plotted graph Figure 8 is such a practice on timespan between 6 30 a m to 16 40 p m We can see a peak at 9 30 a m and at around 11 00 the passenger fl ow get down to a relatively low level this is probably because of massive departures Based on the above passenger fl ow distribution we will simulate the security check queue ing process at a domestic departure checkpoint later 7 2 Arrival Time Recommendation We tend to believe that the passenger arrival behavior can be changed by recommending their arrival time however this is often much more complex due to airport location or cultural norm of a certain nation We calculated the mean waiting time of the passengers by simulating using the varying passenger fl ow introduced in the last subsection at diff erent normal distributions as we men tioned above Only one checkpoint is taken into account in the simulation and the fl ow is generated with domestic departure fl ights When the average arrival of the passengers for a