《数学建模》美赛优秀论文：2007 B O Boarding at the Speed of Flight

Team 2053 1of30 Boarding at the Speed of Flight Team 2053 February 12, 2007 Executive Summary After mathematically analyzing the aircraft boarding problem, our modeling group would like to present our conclusions, strategies, and recommendations We examined the mathematical effects of waiting in line to board. sending in different groupings of seat assignments, and the interaction between various components of the boarding process to determine the time required to board an aircraft. We developed a detailed simulation methodology to test our ideas and to quantify the differences between boarding strategies. Our simulation models all of the critical factors at play in a boarding scenario, and is easily modified to support different plane dimensions and interior configurations as well any as- sortment of passenger characteristics depending on average demographics and other statistics. We believe that further collaboration with your company and access to your internal business data would provide us with the capability to more accurately determine results and to tune our parameters specific to your airline Our analysis began by determining what factors impact boarding speed the most across all boarding algorithms. Our conclusions are presented in the list below along with strategies that can be implemented to mitigate their impact Passenger entry speed: The faster passengers enter the plane, the faster boards. This means fight check-in procedure(ticket checking )should be optimized to ensure the correct number of gate agents are present. This is particularly important on large planes with multiple aisles or levels. Flight attendants should be stationed at critical junctions(such as entrances to aisles in a multi-aisle plane) to direct each passenger to the correct row and thereby maintain throughput Baggage stowage time: The faster passengers put their bags away and sit down, the faster the plane boards. The impact of storage time can be mitigated by changing or enforcing carry-on baggage limits and by having fight attendants assist passengers with particularly large bags that they cannot easily lift. Another possibility to consider is a redesign of the overhead bins to make them more easy to load For airlines interested in further decreasing average boarding time we have fur

Team 2053 1 of 30 Boarding at the Speed of Flight Team 2053 February 12, 2007 Executive Summary After mathematically analyzing the aircraft boarding problem, our modeling group would like to present our conclusions, strategies, and recommendations to the airline industry. We examined the mathematical effects of waiting in line to board, sending in different groupings of seat assignments, and the interaction between various components of the boarding process to determine the time required to board an aircraft. We developed a detailed simulation methodology to test our ideas and to quantify the differences between boarding strategies. Our simulation models all of the critical factors at play in a boarding scenario, and is easily modified to support different plane dimensions and interior configurations as well any as￾sortment of passenger characteristics depending on average demographics and other statistics. We believe that further collaboration with your company and access to your internal business data would provide us with the capability to more accurately determine results and to tune our parameters specific to your airline. Our analysis began by determining what factors impact boarding speed the most across all boarding algorithms. Our conclusions are presented in the list below along with strategies that can be implemented to mitigate their impact: • Passenger entry speed: The faster passengers enter the plane, the faster it boards. This means flight check-in procedure (ticket checking) should be optimized to ensure the correct number of gate agents are present. This is particularly important on large planes with multiple aisles or levels. Flight attendants should be stationed at critical junctions (such as entrances to aisles in a multi-aisle plane) to direct each passenger to the correct row and thereby maintain throughput. • Baggage stowage time: The faster passengers put their bags away and sit down, the faster the plane boards. The impact of storage time can be mitigated by changing or enforcing carry-on baggage limits and by having flight attendants assist passengers with particularly large bags that they cannot easily lift. Another possibility to consider is a redesign of the overhead bins to make them more easy to load. For airlines interested in further decreasing average boarding time we have fur- 1

Team 2053 ther analyzed the merits of different boarding algorithms. Through our simula tions we have developed a generic classification of boarding methods: Best No assigned seats Better Outside in boarding Mediocre back to front We understand that the proposition of no assigned seats may be problematic from a customer service perspective. If this is the case outside in boarding(win dow seats first, in towards the aisle) provides significant advantages over back to front, particularly when our previously mentioned optimizations are incorpo- rated into the system. The exact numbers depend on the aircraft dimensions and other factors, but in general outside in boarding provides a 10-30% advan- tage over back to front. Similarly, foregoing assigned seats results in a 10-30% age over outside in. We know that for m es, this magnitude of aprovement could provide the margin necessary for an extra run in the course of a day, resulting in additional revenue. However, our analysis does not stop at determining mere speed increases; we also analyzed the reliability of each boarding method in order to determine the deviation between the longest and hortest possible delays for each boarding algorithm. In order to schedule an extra flight, you have to be sure the tightened timetable will always be met, not t most of the time. We found that the faster methods are also considerably more reliable: outside in has a time deviation range 50% smaller than back to front. For more specific numbers, examples on varying sizes of planes, and in general a more complete description of our work, please refer to our in-depth re- ort, attached. With our insights and your business expertise, we can cooperate to benefit the customer, your business, and your shareholders

Team 2053 2 of 30 ther analyzed the merits of different boarding algorithms. Through our simula￾tions we have developed a generic classification of boarding methods: • Best No assigned seats • Better Outside in boarding • Mediocre Back to front We understand that the proposition of no assigned seats may be problematic from a customer service perspective. If this is the case outside in boarding (win￾dow seats first, in towards the aisle) provides significant advantages over back to front, particularly when our previously mentioned optimizations are incorpo￾rated into the system. The exact numbers depend on the aircraft dimensions and other factors, but in general outside in boarding provides a 10-30% advan￾tage over back to front. Similarly, foregoing assigned seats results in a 10-30% advantage over outside in. We know that for many routes, this magnitude of improvement could provide the margin necessary for an extra run in the course of a day, resulting in additional revenue. However, our analysis does not stop at determining mere speed increases; we also analyzed the reliability of each boarding method in order to determine the deviation between the longest and shortest possible delays for each boarding algorithm. In order to schedule an extra flight, you have to be sure the tightened timetable will always be met, not just most of the time. We found that the faster methods are also considerably more reliable: outside in has a time deviation range 50% smaller than back to front. For more specific numbers, examples on varying sizes of planes, and in general a more complete description of our work, please refer to our in-depth re￾port, attached. With our insights and your business expertise, we can cooperate to benefit the customer, your business, and your shareholders. 2

Team 2053 3of30 1 ntroduction Short of a single minor detail the airplane boarding problem would be easily solved using a very simple algorithm. Given his performance in the summer blockbuster" Snakes on a Plane we know Samuel L. Jackson is an optima de-boarder of snakes from planes [1]. Assuming that he maintains equal effe tiveness with people, simply invert his role and you have an optimal passenger oarding algorithm. We could then simply model people as snakes and play the film in reverse and determine the effective boarding time. The only potential challenge would be scaling our results from the boeing 747 used in the movie to planes of varying sizes. Ignoring the only detail that there is only one Samuel L Jackson(maybe cloning could help here), the idea of an airplane boarding problem is still an ambiguous oncept. After all, people want to board the plane quickly and the geometry of the plane is fixed. How much is there to modify that could potentially lead to any speedup in boarding time? Upon first observation, it is not obvious the true multitude of factors that mesh to determine airplane boarding time. However, after a closer look the true num- ber of degrees of freedom appear. Then the problem becomes one of determining ich factors significantly contribute to the problem. The complexity required for this analysis is daunting and in many cases the problem would be relegated into the category of“ not worth the time.” However, like many problems orphaned into this category, it is often the market economy that comes to the rescue. The competitive nature of the marketplace continually redefines the differential that determines what is within the bounds of a marginal gain. For the airlines this marginal difference of even a few minutes per flight can represent millions of dollars in revenue over a fiscal year. Consid- ering the number of airlines currently operating under bankruptcy protectio with federal subsidies, this is no small matter. It is this demand for revenue that has thrust the airplane boarding problem into the forefront of modern in- dustrial problem capable of being solved with mathematics. With this in mind we embark on our journey to tackle the airplane boarding problem with Samuel L Jackson as our inspiration 2 Problem restatement We start our journey by concretely stating what we wish to examine. We would ke to finish by having an efficient method for boarding a commercial airplane that accommodates for editable human behavior and a framework that allows us to compare and contrast between different procedures. In the process we would like to gain a"deeper"understanding into the fundamental issues of airline boarding, both to understand the reasons why certain procedures behave

Team 2053 3 of 30 1 Introduction Short of a single minor detail the airplane boarding problem would be easily solved using a very simple algorithm. Given his performance in the summer “blockbuster” Snakes on a Plane we know Samuel L. Jackson is an optimal de-boarder of snakes from planes [1]. Assuming that he maintains equal effec￾tiveness with people, simply invert his role and you have an optimal passenger boarding algorithm. We could then simply model people as snakes and play the film in reverse and determine the effective boarding time. The only potential challenge would be scaling our results from the Boeing 747 used in the movie to planes of varying sizes. Ignoring the only detail that there is only one Samuel L. Jackson (maybe cloning could help here), the idea of an airplane boarding problem is still an ambiguous concept. After all, people want to board the plane quickly and the geometry of the plane is fixed. How much is there to modify that could potentially lead to any speedup in boarding time? Upon first observation, it is not obvious the true multitude of factors that mesh to determine airplane boarding time. However, after a closer look the true num￾ber of degrees of freedom appear. Then the problem becomes one of determining which factors significantly contribute to the problem. The complexity required for this analysis is daunting and in many cases the problem would be relegated into the category of “not worth the time.” However, like many problems orphaned into this category, it is often the market economy that comes to the rescue. The competitive nature of the marketplace continually redefines the differential that determines what is within the bounds of a marginal gain. For the airlines this marginal difference of even a few minutes per flight can represent millions of dollars in revenue over a fiscal year. Consid￾ering the number of airlines currently operating under bankruptcy protection with federal subsidies, this is no small matter. It is this demand for revenue that has thrust the airplane boarding problem into the forefront of modern in￾dustrial problem capable of being solved with mathematics. With this in mind we embark on our journey to tackle the airplane boarding problem with Samuel L. Jackson as our inspiration. 2 Problem Restatement We start our journey by concretely stating what we wish to examine. We would like to finish by having an efficient method for boarding a commercial airplane that accommodates for unpredictable human behavior and a framework that allows us to compare and contrast between different procedures. In the process, we would like to gain a “deeper” understanding into the fundamental issues of airline boarding, both to understand the reasons why certain procedures behave 3

Team 2053 differently, but also to make well-informed and theoretically-justified recommen- dations to our industry patrons We approached the problem by first mathematically analyzing different factors that contribute to delays in airplane boarding. Mathematical analysis of blocks which prohibit smooth flow was carried out using techniques from stochastic processes We also developed a computer simulation which modeled the airplane boarding process while accounting for different boarding methods and individual variation of passengers. We also used our simulation to learn an ideal boarding proce- dure, which we refer to as Parabola for the parabola-like zone assignments that it uses. We then pitted our boarding scheme against other standard boarding schemes to see how it fared 3 Conventions This section defines the basic terms used in this paper 3.1 Terminology Passenger: A passenger is an individual traveling on the plane who is not part of the crew Boarding Scheme: a boarding scheme refers to an assignments of zones or groups according to which passengers board the plane. Depending on the modeling options, it could be exactly deterministic or the general assignment before random mixings Interference An interference is an in which a passenger cannot progress towards their seat because ther passenger blocking their way. Variables efine the following variables here as they are used widely throughout Additional variables may be defined later, but will be confined to particular section C refers to the number of columns in the plane which is also the number of seats in a row R refers to the number of rows in the plane. For the most part we ignore or treat in a different manner distinctions between classes. for details see section 4

Team 2053 4 of 30 differently, but also to make well-informed and theoretically-justified recommen￾dations to our industry patrons. We approached the problem by first mathematically analyzing different factors that contribute to delays in airplane boarding. Mathematical analysis of blocks which prohibit smooth flow was carried out using techniques from stochastic processes. We also developed a computer simulation which modeled the airplane boarding process while accounting for different boarding methods and individual variation of passengers. We also used our simulation to learn an ideal boarding proce￾dure, which we refer to as Parabola for the parabola-like zone assignments that it uses. We then pitted our boarding scheme against other standard boarding schemes to see how it fared. 3 Conventions This section defines the basic terms used in this paper. 3.1 Terminology • Passenger: A passenger is an individual traveling on the plane who is not part of the crew. • Boarding Scheme: A boarding scheme refers to an assignments of zones or groups according to which passengers board the plane. Depending on the modeling assumptions, it could be exactly deterministic or the general assignment before random mixings. • Interference: An interference is an event in which a passenger cannot progress towards their seat because of another passenger blocking their way. 3.2 Variables We will define the following variables here as they are used widely throughout our paper. Additional variables may be defined later, but will be confined to a particular section. • C refers to the number of columns in the plane which is also the number of seats in a row. • R refers to the number of rows in the plane. For the most part we ignore or treat in a different manner distinctions between classes, for details see section 4. 4

Team 2053 5of30 B refers to the time it takes for a person to stow their baggage into the overhead bin. B is assumed to be constant for our preliminary mathemat- ical analysis; it is allowed to change in the simulation. Refer to section 7.5 for more information about variation of B v refers to the walking speed of the passengers. It is assumed to be constant throughout the model. See section 4 for an explanation. s refers to the time it takes for an already seated passenger to get up and get out to let another passenger pass. It is assumed to be constant for nathematical analysis but is allowed to vary in the simulation A refers to the rate at which people enter the plane through the main door This value is assumed to be constant as any deviations in time between passengers is mitigated by walking down the jet-bridge to the plane 4 Assumptions We make the following assumptions about airplane boarding process in this Passengers with physical limitations, families with infants, and passengers extremely advanced in years board the plane before other passengers for their own safety and comfort. We assume that these passengers might perhaps with the assistance of fight attendants. The time taken for this pre-boarding is assumed to be a constant overhead that airlines cannot First class passengers are boarded separately. The existence of a first class in our view means that they require first class treatment: a first class section where passengers have to fight through the proletarian masses is antithetical to the very idea of a"first"class. We can either assume a single-class plane, or model the first class separately( see section 11) All passengers boarding the plane during general boarding walk at ap- proximately the same speed. Since we assume passengers of extremely limited mobility are already aboard the plane, this is plausible. Further more, the walking speed is limited more by the environment (aisle size people in the way) than the persons innate maximum physical capacity Passengers board independently and walk independently, that is, we have no groups waiting for each other or slowing in line. For families we might ssume that they are assigned seats next to each other, which satisfies their bonding and closeness desires We confine our analysis to the interior of the plane. That is, we ignore ter minal effects(anything outside the plane door)) beyond requiring that the gate agents can supply us with passengers at a certain(typically constant

Team 2053 5 of 30 • B refers to the time it takes for a person to stow their baggage into the overhead bin. B is assumed to be constant for our preliminary mathemat￾ical analysis; it is allowed to change in the simulation. Refer to section 7.5 for more information about variation of B. • v refers to the walking speed of the passengers. It is assumed to be constant throughout the model. See section 4 for an explanation. • s refers to the time it takes for an already seated passenger to get up and get out to let another passenger pass. It is assumed to be constant for mathematical analysis but is allowed to vary in the simulation. • λ refers to the rate at which people enter the plane through the main door. This value is assumed to be constant as any deviations in time between passengers is mitigated by walking down the jet-bridge to the plane. 4 Assumptions We make the following assumptions about airplane boarding process in this paper. • Passengers with physical limitations, families with infants, and passengers extremely advanced in years board the plane before other passengers for their own safety and comfort. We assume that these passengers might need the plane to be relatively empty to successfully reach their seat, perhaps with the assistance of flight attendants. The time taken for this pre-boarding is assumed to be a constant overhead that airlines cannot avoid. • First class passengers are boarded separately. The existence of a first class in our view means that they require first class treatment: a first class section where passengers have to fight through the proletarian masses is antithetical to the very idea of a “first” class. We can either assume a single-class plane, or model the first class separately (see section 11). • All passengers boarding the plane during general boarding walk at ap￾proximately the same speed. Since we assume passengers of extremely limited mobility are already aboard the plane, this is plausible. Further￾more, the walking speed is limited more by the environment (aisle size, people in the way) than the person’s innate maximum physical capacity. Passengers board independently and walk independently, that is, we have no groups waiting for each other or slowing in line. For families we might assume that they are assigned seats next to each other, which satisfies their bonding and closeness desires. • We confine our analysis to the interior of the plane. That is, we ignore ter￾minal effects (anything outside the plane door)) beyond requiring that the gate agents can supply us with passengers at a certain (typically constant) 5

Team 2053 rate. If the plane cannot "process"them quickly enough, they queue in the jet-bridge without adverse effects. Additionally, the interior of our planes are generally assumed to be regular and symmetric with all rows All planes fly at maximum capacity and all passengers are present at the time their respective zone is called, which they follow obediently. Empty disobedient ngers can be thought of as equivalent and at worst can be accounted by adding a time overhead once they board the plane. We confine our recommendations and analysis to methods that do not overly alter the status quo. Change is bad, particularly for the airline dustry in this already turmoil-laden time. We will analyze ticketless methods for comparison but seek to find the best boarding method for tick- eted contexts, since this will be useful for the many airlines that refuse to abandon assigned seats. We further will only consider zone-based board- ing calls, assuming that is too heavy-handed and logistically impossible to require passengers to line up in any verifiable order Additional assumptions are made to simplify analysis for individual section nese assumptions will be discussed at the appropriate locations 5 Motivation and Subproblems With the large number of complexities involved in the airplane boarding pro- cess, we begin by analyzing the problem in small, idealized parts. We begin by examining an ideal, best case algorithm that simplifies many issues in its analysis. By looking at the simplifications necessary to make this analysis,w get a better idea of the underlying problems or key issues in the process. In o econd and third sections we rigorously analyze facets of the boarding process to gain insights into the nature of the problem. Ultimately the knowledge we gain will motivate the set of boarding schemes best suited to solving the airplane boarding problem and the factors we will compare in our simulation model 5.1 Best-Case Boarding Algorithm Consider for a moment the case in which all possible variables involving pas- senger boarding could be controlled. Under these circumstances how would it be possible to schedule the boarding of the plane in an optimal manner? After consideration we determined that the best way of boarding a plane with these conditions would be to use a modified version of outside to inside method. pas enger are first ordered by the following set of criteria in descending order of Individual location in row: Window has highest priority, aisle has least

Team 2053 6 of 30 rate. If the plane cannot “process” them quickly enough, they queue in the jet-bridge without adverse effects. Additionally, the interior of our planes are generally assumed to be regular and symmetric with all rows equally-sized. • All planes fly at maximum capacity and all passengers are present at the time their respective zone is called, which they follow obediently. Empty seats would only speed up the process. Late passengers or disobedient passengers can be thought of as equivalent and at worst can be accounted for by adding a time overhead once they board the plane. • We confine our recommendations and analysis to methods that do not overly alter the status quo. Change is bad, particularly for the airline industry in this already turmoil-laden time. We will analyze ticketless methods for comparison but seek to find the best boarding method for tick￾eted contexts, since this will be useful for the many airlines that refuse to abandon assigned seats. We further will only consider zone-based board￾ing calls, assuming that is too heavy-handed and logistically impossible to require passengers to line up in any verifiable order. Additional assumptions are made to simplify analysis for individual sections. These assumptions will be discussed at the appropriate locations. 5 Motivation and Subproblems With the large number of complexities involved in the airplane boarding pro￾cess, we begin by analyzing the problem in small, idealized parts. We begin by examining an ideal, best case algorithm that simplifies many issues in its analysis. By looking at the simplifications necessary to make this analysis, we get a better idea of the underlying problems or key issues in the process. In the second and third sections we rigorously analyze facets of the boarding process to gain insights into the nature of the problem. Ultimately the knowledge we gain will motivate the set of boarding schemes best suited to solving the airplane boarding problem and the factors we will compare in our simulation model. 5.1 Best-Case Boarding Algorithm Consider for a moment the case in which all possible variables involving pas￾senger boarding could be controlled. Under these circumstances how would it be possible to schedule the boarding of the plane in an optimal manner? After consideration we determined that the best way of boarding a plane with these conditions would be to use a modified version of outside to inside method. Pas￾senger are first ordered by the following set of criteria in descending order of priority: • Individual location in row: Window has highest priority, aisle has least 6

Team 2053 7of30 Side of plane: left side of plane has priority over right side Row number: Rows in back have priority over those in front After ordering passengers in this manner the following algorithm could be ap- plied to board the plane optimally: While the ideal boarding algorithm may 吕吕吕日吕日吕日日日日 目目目目日目E目目 卣口 □ 2* Began walk i 品日日日日日日日日 。。。□ □ Hayate 4a Begin Walk In Figure 1: This figure demonstrates the operation of the ideal airplane boarding algorithm. Each group of R people is represented by a number corresponding to the order that group ter. Each group proceeds down the aisle until each person reaches their row(since people are in order they all reach their row simultaneously ). They step into the first seat in their row and then begin storing their carry-on baggage. During this time the next group commences walking down the aisle (they won't be getting married though). Notice the only time when a 2 in which case every ait in the aisle for B-2- seconds. This accounts for the additional term in the second part eem an enticing solution to the passenger boarding problem it is far from prad tical as it is unreasonable to expect people to perfectly order themselves and llow strict commands on what actions to perform in the plane(unless of course ou're boarding a company of United State Marines). Instead we will utilize the the ideal boarding algorithm to place a lower bound on the minimum amount of time required to board an airplane of a given size and shape. The formula

Team 2053 7 of 30 • Side of plane: left side of plane has priority over right side • Row number: Rows in back have priority over those in front After ordering passengers in this manner the following algorithm could be ap￾plied to board the plane optimally: While the ideal boarding algorithm may 1 2 3 4 5 6 7 8 9 n−2 n−1 n 1 1 1 1 Time=0 1 1 1 1 1 1’s Begin Walk In 1 2 3 4 5 6 7 8 9 n−2 n−1 n 1 1 1 1 1 1 1 1 1 1 1 1 Time=R/v 2 2 2 2 2 2 2 2 2 1’s Move Into First Seat, Begin Storing Baggage 2’s Begin Walk In 1 2 3 4 5 6 7 8 9 n−2 n−1 n 1 1 1 1 1 1 1 1 1 1 1 1 T=2R/v 2’s Move In First Seat, Begin 3 3 3 3 3 3 3 3 3 Storing Baggage 2 2 2 2 2 2 2 2 2 2 2 2 3’s Begin Walk In 1 2 3 4 5 6 7 8 9 n−2 n−1 n 1 1 1 1 1 1 1 1 1 1 1 1 3 3 3 3 3 3 3 3 3 3 3 3 T=3R/v or 2R/v+B whichever is longer 1’s Sit Down 2 2 2 2 2 2 2 2 2 2 2 2 4 4 4 4 4 4 4 4 4 3’s Move In First Seat, Begin Storing Baggage 4’s Begin Walk In Figure 1: This figure demonstrates the operation of the ideal airplane boarding algorithm. Each group of R people is represented by a number corresponding to the order that groups enter. Each group proceeds down the aisle until each person reaches their row (since people are in order they all reach their row simultaneously). They step into the first seat in their row and then begin storing their carry-on baggage. During this time the next group commences walking down the aisle (they won’t be getting married though). Notice the only time when a group might stall in the aisle is if B is larger than 2R v in which case every other group must wait in the aisle for B-2R seconds. This accounts for the additional term in the second part v of equation (5.1). seem an enticing solution to the passenger boarding problem it is far from prac￾tical as it is unreasonable to expect people to perfectly order themselves and follow strict commands on what actions to perform in the plane (unless of course you’re boarding a company of United State Marines). Instead we will utilize the the ideal boarding algorithm to place a lower bound on the minimum amount of time required to board an airplane of a given size and shape. The formula 7

Team 2053 for computing this time is (5.1) Ideal Boarding Time CE+B B<2 C+B+(-1)(B-2R)B≥ In addition to using the lower bound generated by the ideal boarding algorithm we will also utilize it to recognize several key insights into the problem of passen- r boarding. The following are two key concepts to note about the operation of the algorithm The main aisle is kept continuously busy unless passengers have to wait for people in their row to finish placing their baggage up Passengers are"pipelined" to minimize the blocking effect of placing any luggage in the overhead bins In essence, these two properties of the algorithm are solutions that arise in response to two of the fundamental problems in the passenger boarding problem. nese problems only manifest themselves whenever some order of randomness is introduced into the process; that is, when passengers are not perfectly ordered The introduction of randomness also ultimately leads to the downfall of the ideal algorithm. The fact that randomness, that is, imperfect ordering, is an inherent property of the airline boarding problem(see section 4) forces us to consider the following when determining the best airline boarding algorithm Random Orderings: How out-of-order are people and how does this pact other dependencies in boarding? Flow Rates: How long does it take people to enter the plane and walk down the aisle without blocking the aisle? Baggage: How large is their baggage and how long does it take to place An important observation to be made concerning the above conditions is that they all represent means of introducing dependencies into the system. Randor ness prevents us from determining the occurrence or duration of these depen dencies and therefore forces us to design boarding schemes capable of tolerating their effects. One potential solution would be to remove dependencies by forcing people to continue moving as far back in the plane and over in a row as long as hey dont get blocked. We will return to this"Random Greedy" approach later as it represents the intuitive motivation for our best airplane boarding scheme. However, before introducing any additional schemes, we will determine the ex- act mathematical impact of several different algorithm design parameters. By determining these effects, we can then use them to guide our choice of boarding schemes for testing

� Team 2053 8 of 30 for computing this time is: R v R C + B B ≤ v 2 (5.1) Ideal Boarding Time = C R v C 2 R + B + v ( − 1)(B − 2R) B ≥ 2 In addition to using the lower bound generated by the ideal boarding algorithm we will also utilize it to recognize several key insights into the problem of passen￾ger boarding. The following are two key concepts to note about the operation of the algorithm: • The main aisle is kept continuously busy unless passengers have to wait for people in their row to finish placing their baggage up. • Passengers are “pipelined” to minimize the blocking effect of placing any luggage in the overhead bins In essence, these two properties of the algorithm are solutions that arise in response to two of the fundamental problems in the passenger boarding problem. These problems only manifest themselves whenever some order of randomness is introduced into the process; that is, when passengers are not perfectly ordered. The introduction of randomness also ultimately leads to the downfall of the ideal algorithm. The fact that randomness, that is, imperfect ordering, is an inherent property of the airline boarding problem (see section 4) forces us to consider the following when determining the best airline boarding algorithm: • Random Orderings: How out-of-order are people and how does this impact other dependencies in boarding? • Flow Rates: How long does it take people to enter the plane and walk down the aisle without blocking the aisle? • Baggage: How large is their baggage and how long does it take to place in the overhead bins? An important observation to be made concerning the above conditions is that they all represent means of introducing dependencies into the system. Random￾ness prevents us from determining the occurrence or duration of these depen￾dencies and therefore forces us to design boarding schemes capable of tolerating their effects. One potential solution would be to remove dependencies by forcing people to continue moving as far back in the plane and over in a row as long as they don’t get blocked. We will return to this “Random Greedy” approach later as it represents the intuitive motivation for our best airplane boarding scheme. However, before introducing any additional schemes, we will determine the ex￾act mathematical impact of several different algorithm design parameters. By determining these effects, we can then use them to guide our choice of boarding schemes for testing. 8

Team 2053 5.2 Predicting Bottlenecks with Queuing Theory One intuition for modeling the airplane boarding problem is to think of it as a stochastic process. A stochastic process is a collection of random variables that must take on a value at every state, where states are indexed by some parameter (in our case time)2. A simple example of using a stochastic process to model the airline boarding problem would be if we considered each entering passen- ger to be associated with a random variable that described their assigned seat Although this may seem simplistic, it is conceivable to assign every potent parameter in the airplane boarding process a random variable that is associated with time. We determined that this level of detail was prohibitive based on the mount of computation that would be required even for just a few variables Despite this, we can still use several tools associated with stochastic processes to learn about the plane boarding problem To analyze this stochastic process formulation, we use queuing Queu- ing theory deals with analyzing the way that random variables processes interact. Traditionally queuing theory is utilized for de ng the .erage hroughput of a system. While the airplane boarding problem does not possess a quantity directly corresponding to throughput, we will show that we can gain a better understanding of bottlenecks and their effects using this approach We place a"processor"at each row. This processor corresponds to each paes The first step in our analysis is to partition the airplane into a series of quer ger making a decision at this point either to keep walking or to stop and enter their row. Each processor has a queue that stores passengers. Queues have a size of 1 and will stop the processor feeding them if they are full. This would represent people backing up if someone stops in the aisle. a diagram for this layout can be seen in figure 2 ( Figure 2: A Queuing Theory Model of an Airplane In the above diagram uk represents the processing rate of the "processor".We can choose this variable to directly correspond to the average walking speed of people. Each Pk represents some probability at which passengers are diverted into the their rows or continue walking in the aisle. In some cases people will take longer to get into their rows depending upon how long it takes for them

Team 2053 9 of 30 5.2 Predicting Bottlenecks with Queuing Theory One intuition for modeling the airplane boarding problem is to think of it as a stochastic process. A stochastic process is a collection of random variables that must take on a value at every state, where states are indexed by some parameter (in our case time) [2]. A simple example of using a stochastic process to model the airline boarding problem would be if we considered each entering passen￾ger to be associated with a random variable that described their assigned seat. Although this may seem simplistic, it is conceivable to assign every potential parameter in the airplane boarding process a random variable that is associated with time. We determined that this level of detail was prohibitive based on the amount of computation that would be required even for just a few variables. Despite this, we can still use several tools associated with stochastic processes to learn about the plane boarding problem. To analyze this stochastic process formulation, we use queuing theory. Queu￾ing theory deals with analyzing the way that random variables in stochastic processes interact. Traditionally queuing theory is utilized for determining the average throughput of a system. While the airplane boarding problem does not possess a quantity directly corresponding to throughput, we will show that we can gain a better understanding of bottlenecks and their effects using this approach. The first step in our analysis is to partition the airplane into a series of queues. We place a “processor” at each row. This processor corresponds to each passen￾ger making a decision at this point either to keep walking or to stop and enter their row. Each processor has a queue that stores passengers. Queues have a size of 1 and will stop the processor feeding them if they are full. This would represent people backing up if someone stops in the aisle. A diagram for this layout can be seen in figure 2. u_0 u_1 u_2 u_n−1 p_1 p_3 p_2n−1 p_0 p_2 p_2(n−1) Figure 2: A Queuing Theory Model of an Airplane In the above diagram uk represents the processing rate of the “processor”. We can choose this variable to directly correspond to the average walking speed of people. Each pk represents some probability at which passengers are diverted into the their rows or continue walking in the aisle. In some cases people will take longer to get into their rows depending upon how long it takes for them 9

Team 2053 to put their baggage up. The processor associated with that row will then take longer to process that job, causing the flow of people through the aisle to stall One downfall of this particular model is that all passengers must leave the sys- tem and it doesn't always accurately reflect that each row should only ever hold C passengers. It was this fact that ultimately led us to drop the queuing theory odel as our main model. However, we will see that we can gain some useful knowledge concerning bottlenecks in the aisle n order to convert the open system shown in figure 2 to a closed form system that can be solved by Queuing theory we use Jacksons Theorem 6. Jackson's heorem notes that an open system can be represented with a feedback loop if the rate of processing at each processor is augmented proportional to the rate of How prior to that processor. Using this theorem we can redraw our airplane model as seen in figure 3. This closed form now allows us to solve this queuing Figure 3: A Closed Form Queuing Model of an Airplane model to determine the probability of having a given number of passengers at a specific node at a given time. We assume a solution of p(ko, k1, / ldots, kin-1) where p is a function that computes the probability of having ki people in the i position in the aisle. Conceptually this implies that we have an n dimensional tate-space since the number of passengers at each node is potentially different e can now write down some conditions that p must satisfy and use these con ditions to find an actual equation for The first condition that we know p must satisfy is that it must maintain How of passengers into and out of a given state in state-space. This ensures that passengers are never"lost"in the system. This equation can be stated as ∑吗o,k…,A-1) Ap(ko-1,k1,……,kn-1)+pn-1p(ko,…,kn-2,kn-1+1)+ (52)∑p(…k+1,k+1-1,… The fact that all rates are dependent upon po stems from the fact that the rate into the ext queue is dependent upon the output of the previous processor and terms cancel under our assumptions for the value of any pj

� � Team 2053 10 of 30 to put their baggage up. The processor associated with that row will then take longer to process that job, causing the flow of people through the aisle to stall. One downfall of this particular model is that all passengers must leave the sys￾tem and it doesn’t always accurately reflect that each row should only ever hold C passengers. It was this fact that ultimately led us to drop the queuing theory model as our main model. However, we will see that we can gain some useful knowledge concerning bottlenecks in the aisle. In order to convert the open system shown in figure 2 to a closed form system that can be solved by Queuing theory we use Jackson’s Theorem [6]. Jackson’s Theorem notes that an open system can be represented with a feedback loop if the rate of processing at each processor is augmented proportional to the rate of flow prior to that processor. Using this theorem we can redraw our airplane model as seen in figure 31 . This closed form now allows us to solve this queuing u_0p_0 u_1p_0/p_2 u_2p_0/p_4 u_(n−1)p_0/p_2(n−1) Figure 3: A Closed Form Queuing Model of an Airplane model to determine the probability of having a given number of passengers at a specific node at a given time. We assume a solution of ρ(k0, k1, /ldots, kn−1) where ρ is a function that computes the probability of having ki people in the i position in the aisle. Conceptually this implies that we have an n dimensional state-space since the number of passengers at each node is potentially different. We can now write down some conditions that ρ must satisfy and use these con￾ditions to find an actual equation for ρ. The first condition that we know ρ must satisfy is that it must maintain flow of passengers into and out of a given state in state-space. This ensures that passengers are never “lost” in the system. This equation can be stated as ⎛ ⎞ n−1 ⎝λ + µj⎠ ρ(k0, k1, . . . , kn−1) = j=0 λρ(k0 − 1, k1, . . . , kn−1) + µn−1ρ(k0, . . . , kn−2, kn−1 + 1) + n−2 (5.2) µjρ(. . . , kj + 1, kj+1 − 1, . . .) j=0 1 The fact that all rates are dependent upon p0 stems from the fact that the rate into the next queue is dependent upon the output of the previous processor and terms cancel under our assumptions for the value of any pj . 10