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 ticketed contexts, since this will be useful for the many airlines that refuse to abandon assigned seats. We further will only consider zone-based boarding 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 process, 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 passenger 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. Passenger 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 applied 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 practical 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 passenger 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. Randomness prevents us from determining the occurrence or duration of these dependencies 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 exact 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 passenger 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. Queuing 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 passenger 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 system 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 conditions 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