美赛建模论文 英文版.doc

For office use onlyT1_T2_T3_T4_Team Control Number46Problem ChosenCFor office use onlyF1_F2_F3_F4_2003 Mathematical Contest in Modeling (MCM) Summary Sheet (Attach a copy of this page to each copy of your solution paper.) Type a summary of your results on this page. Do not includethe name of your school, advisor, or team members on this page. SummaryNew laws will soon mandate 100% screening of all checked bags at the 429 airports throughout the United States by explosive detection systems (EDSs). Under this condition, we are tasked to determine the number of EDSs needed and the strategy to schedule the flights. Moreover, the necessity of the supplements with explosive trace detection (ETD) machines should be studied.We consider tasks 1 and 3 as a major problem and a model of queue service system could represent it. By studying a general queue service system, we obtain the relationship between number of passengers and devices required. Furthermore, criteria for evaluating the queue service system are developed. Security of flight, expenditure of airport and average time for passengers waiting are primary factors that determine the quality of service.Adapting the conclusions obtained to Airports A & B, we develop a feasible strategy to schedule the flights. Using both theoretical method and dynamical computer simulation, we obtain that 41 EDSs are required in Airport A and the average time spent on waiting is 14.865 minutes per passenger; 44 EDSs are required in Airport B and the average time spent on waiting is 14.473 minutes per passenger.Based on the analysis of the conclusions and results obtained, to accomplish task 2, 4, and 6, we write a position paper on security-related objectives, a recommendation about the screening process and a memo explaining how to adapt our models to other airports and flights.To fulfil task 7, performances of both EDSs and ETDs are concentrated. We find that ETDs have higher accuracy while costing more money. It is not economical to use only ETDs for screening, but they could be a helpful supplement for EDSs.Finally, we discuss the way to best fund future scientific research.To Screen or Not?电子科技大学蒋华孙立鸥邓长顺Problem restatement and analysisTransportation Security Administration (TSA) will soon begin screening 100% of checked baggage at all 429 commercial airports across the United States. It uses two kinds of screening systems: explosive detection system (EDS) and explosive trace detection (ETD). EDS create three-dimensional images of a bag by x-rays, showing the density of each item. But it cost nearly $1 million to purchase and thousands of dollars to install. Because of the high cost and limited number available, we need to do a detailed analysis to best utilize EDS. ETD is another kind of screening systems with higher accuracy but higher labor cost. Each system has its advantages and disadvantages. Our objective is to develop a method to best use of them synthetically. Basic Assumptions1. Airport fact book 1 shows that busy airports such as Los Angeles Airport and Chicago OHare Airport can reach an annual aircraft movements of 800,000. Because Airports A & B is the largest ones in the Midwest Region, it is reasonable to assume that the data given in Appendix A is during exactly one hour of the busy time. We assume that it is between 2pm and 3pm.2. Flights depart every 5 minutes.3. The number of flights departing within 5 minutes is not greater than 4.4. Check-in process begins 90 minutes and ends 30 minutes before departure.5. Only when all passengers have checked in can a flight depart and if the examinations could not be finished 30 minutes prior the departure time, the flight will delay.Variables and NotationsDevice accuracy Device error probability Types of flights Length of queue Time on waiting The interference degree from queue waiting for flight to queue waiting for flight. Flight of type departing at time Seat occupation of flight Number of seats on flight Speed of screeningModel I: Screening with EDSsMathematic Model of One-Counter ServiceAs a basic model, we consider that there is only one check counter and all the passengers discussed in this model would depart at the same time. To investigate a general regulation, suppose that passengers arrive at the airport between times and . Considering the bags come at the same time, we assume that arrival time of bags is a random variable whose probability density function is and probability distribution function is. Let be the total number of bags arriving, and be the number of bags arriving we have: (1)The bags arriving trend is illustrated in figure 1. Figure 1. Probability distribution function If check-in process begins at time , and the bag-checking speed of EDS is a constant: (2)Then the maximum number of checked bags (3)Between and is a constant other is 0, so is a segment showed in figure 2. Set time point after which there would be no queue up to checking ending time (Suppose that there are enough EDS so we have ). If passengers queue all the time between and (which is illustrated in figure 3), that is the length of queue has no zero point between and .Figure 2. Bags arriving and checking quantity trend figure Then the length of queue could be computed using following function: (4)Figure 3. Queue length changing trend figureSet to be the average wait time for every passenger: (5)Set to be the maximum wait time for some passenger: (6)Another CaseA special case is illustrated in figure 4 below that queue length has zero points between and . In this case, the length of queue is a complicated discontinues function that is showed in figure 4. Figure 4. Number of arriving Figure 5. Queue length functionin bags increasing figure for special case. for special case.We find that under this case, few passengers arrive at the airport early, which delays is to and would cause them late for their flight. Actually, we could avoid this situation by suggesting passengers arrive earlier by manual or other ways. So we will ignore this case in our models. Determination of Flight Schedule and Number of EDSInterference between passenger flowsIn order to develop our scheduling method, a model considering the interference of people in same queue while waiting for different flights is needed first. According our method, there is no interference among queues using different checking desks. But there might be interference among people that use the same checking desk.Most passengers arrive at the airport within a time interval, and the arriving time of bags is a random variable. Suppose that arriving time satisfy normal distribution. We consider two passenger flows interference. Carefully set coordinate system to make and with their probability density function are and . Figure 6. Interference of two different queuesIn order to analyze interference of queues, we introduce interference degree below: (7)Later passenger flow would interfere an earlier one, but an earlier flow has no interference to later one. Interference is controlled by time interval of two departure times. Derivate with respect of , we have: (8)Since , we can conclude that interference degree decreases when the time intervalincreases. When , passengers typically arrive for their flight between departure times, thus we estimate , which could make sure 99.7% passengers arrive during forty-five minutes and two hours prior to their scheduled in probability. Thus the interference could be calculated: (9)There might be a queue 113 bags long, so the amount of passengers who are interfered might be. Few passengers are interfered, thus we could ignore the interference when time distance is 1 hour.l Number of EDSs Required by A Single FlightThe screening speed is a constant . Set the number of bags needed screening is , screen time length is , the number of EDSs needed: (10)l Grouping The FlightsOur goal is to minimize the expenditure of airports and the risk of explosions as well as average time on waiting. In fact, many factors such as density of passenger flow and the number of runways could affect the ways to schedule the departure of different types of flights within the peak hour. Different airports use different methods to assign service counters to flights. A typical method is to assign one or more counters to one individual flight. In the case, passengers for same flight queue at the same counters assigned. Another commonly used method is to divide the service counters into several groups and each group is assigned to several different flights. The two methods both have advantages and disadvantages. If the EDS of a service counter does not work, it is easy for the group method to transfer passengers to other counters of the same group. However, because passengers for different flight wait in the same queue, there will be a disorder of priority. For example, the flight which Passenger A will take is going to depart in 30 minutes, but several passengers prior to him is going to take flight departing in 90 minute, later than that of A.To utilize the advantages and meanwhile avoid the disadvantages, we also use the group method but each group is assigned to flights with the same departure time. Therefore, the advantages remain while the disorder of priority is negligible.From assumption 2 and 3, we need to divide the flights in each airport into 12 groups and each group has at most 4 flights. Then we have the minimum number of EDS needed: (11)and the restricts: (12) (13) (14)where denotes the number of flights of type and scheduled to take off at and rounds the elements of to the nearest integers towards infinity. We wrote a MATLAB program to solve this integer program problem, adapting both conservative and economical methods to both airports.See appendix I to review our objectives and constrains in modeling.l Conservative schedule methodTo minimize the flight delay due to luggage screening, suppose that all flights fly with 100% of seats occupied, and each EDS examine 160 bags per hour. Thus=100%, (15) minutes per bag (16):00:05:10:15:20:25:30:35:40:45:50:55M1(34)1111111111M2(46)112M3(85)111M4(128)111M5(142)11111133322M6(194)11111M7(215)1M8(350)1Total430437464455455455428460460460446446EDSs444444444444Table 1. Schedule of conservative method for airport A:00:05:10:15:20:25:30:35:40:45:50:55M1(34)2111111M2(46)111111M3(85)1111111M4(128)1112M5(142)111111111M6(194)111121111M7(215)11M8(350)1Total560455453416455519550505467467467467EDSs544445554444Table 2. Schedule of conservative method for airport Bl Economical methodProbably the flights would not fly with 100% of their seats occupied. Suppose that the flights fly with mean seat occupations and EDSs have mean rate of examination. Thus (17) minutes per bag (18):00:05:10:15:20:25:30:35:40:45:50:55M1(34)1111111111M2(46)121M3(85)111M4(128)111M5(142)11111133322M6(194)11111M7(215)1M8(350)1Total364353370370370347337369369369358358EDSs333333333333Table 3. Schedule of economical method for airport A:00:05:10:15:20:25:30:35:40:45:50:55M1(34)2111111M2(46)21111M3(85)1111111M4(128) 1112M5(142)111111111M6(194)111121111M7(215)11M8(350)1Total393364387370370380380442400400399380EDSs333333343333Table 4. Schedule of economical method for airport Bl Syntheses methodThe conservative method costs too much and the economical method makes passengers wait for too long. Synthetically considering both advantages and disadvantages of each method above, we developed new schedule based on the conservative method. Some EDSs being reduced, there is a compromise between airport expenditure and efficiency.:00:05:10:15:20:25:30:35:40:45:50:55M1(34)1111111111M2(46)112M3(85)111M4(128)111M5(142)11111133322M6(194)11111M7(215)1M8(350)1Total430437464455455455428460460460446446EDSs334343344433Table 5. Schedule of syntheses method for airport A:00:05:10:15:20:25:30:35:40:45:50:55M1(34)2111111M2(46)111111M3(85)1111111M4(128)1112M5(142)111111111M6(194)111121111M7(215)11M8(350)1Total560455453416455519550505467467467467EDSs544344443333Table 6. Schedule of syntheses method for airport BA memo on number of EDS determination and flight scheduling is available. See appendix II.Evaluation of Model Il Theoretical MethodSuppose bag arrival time satisfies normal distribution, and then the distribution parameters could be estimated. Passengers arrive at the airport between two hours and 45 minutes prior their schedule, suppose most passengers arrive at the airport between those time intervals. Set two hour prior their schedule to be the origin of coordinate system, then we have and . The probability density function : (19)The probability distribution function (20)Then the length of queue could be computed using following function: (21) Figure 7. Plot of length of queueAverage waiting time is (22)Maximum waiting time is (23)To get a more comfort expression we ignore the fact that is discontinues but we consider it as continues temporarily. Derivate with respect of , and set (24)That is (25)i.e. (26)Figure 8. plot showing roots of equation (26)Actually, we expect to deduce the cost, and then we must set , then there must be two roots, but the bigger root is which we are interested in. it is easy to confer that .Then we have: (27)Departure TimeAmount of EDS Average Longest Queue Time (minutes)Average Length of Longest Queue (bags)Average Maximum Wait (minutes)Average Wait (minutes)A4849.870.522.917.9B5249.769.622.616.0Table 7. Evaluation data obtained in theoryWe write MATLAB programs to calculate the evaluation data using numerical method (see table 7). In order to see the worst status, we suppose that rates of seats occupied are 100% for all flight.l Computer SimulationNow that the flight schedule, the distribution of passenger flow and the regulation of check-in process are determined, we can simulate the check-in process using computer program. In computer simulation, we concentrate on average and maximum time spent on waiting for checking in. We wrote a MATLAB program to simulate both conservative and economical schedule strategies adapting to both airports. We simulate each case for 1,000 times to make the results statistically significant (algorithms and programs see appendix). The results of the simulation are shown below:EDSs neededAverage time on waiting (min/passenger)Maximum time on waiting (min/passenger)Average delayed time (min/flight)Airport A, con4811.340215.91510Airport B, con5211.165915.76820Airport A, eco3618.413627.34420.5584Airport B, eco3719.632929.52141.4614Airport A, syn4114.865321.56710.1245Airport B, syn4414.473220.89630.1098Table 8. Computer simulation results for our schedule(con: conservative; eco: economical; syn: syntheses)See appendix IV to check the algorithms and programs of computer simulation.Recommendation about checked baggage screeningDuring the peak hour, at least 46 flights depart at each airport, carrying up to 5,800 passengers. To follow the mandate of 100% screening of all checked bags while minimizing expenditure on purchasing and installing EDSs, we have several strategies.l Conservative StrategyIf funds enough, we recommend to adopt