《数学建模》美赛优秀论文：2007 B O Novel Approaches to Airplane Boarding

In the zone Novel Approaches to Airplane boarding Team 205 uary Abstract Despite the increased pressure on airlines to increase productivity in recent times, a largely overlooked inefficiency in air travel is the board- ing and unloading process. The typical airline uses a zone system, where passengers board the plane from back to front in several groups. The ef- ficiency of the zone system has come into question with the introduction of the open-seating policy of Southwest Airlines. Despite conventional wisdom, Southwest is able to turnaround planes at an uncanny rate with heir innovative methods. Hence, the optimality of the entire boarding process has come into question We propose a stochastic agent-based simulation of the boarding process in order to explore the effectiveness of novel boarding techniques. Our model organizes the aircraft into discrete units called processors. 'Each processor corresponds to a physical row of the aircraft. Passengers enter the plane and are moved through the aircraft based on the functionality of these processors. During each cycle of our simulation each row (pro- cessor) can execute a single operation. Operations accomplish functions such as moving passengers to the next row, stowing luggage or seating passengers. The processor model tells us, from an initial ordering of pas- sengers in a queue, how long the plane will take to board, and produces a grid detailing the chronology of passenger seating We extend our processor model with a genetic algorithm, which we use to search the space of possible passenger configurations for innovative and effective patterns. This algorithm employs the biological techniques of crossover to se imal solutions to th enger boarding problem. We create a variant of this algorithm which is optimize a priori boarding patterns We also integrate a Markov chain model of passenger preference with our cessor model. We use this preference mod Southwest-style boarding, where seats are not assigned but are chosen by individuals based on environmental constraints(such as seat availability)

In the Zone: Novel Approaches to Airplane Boarding Team 2056 February 12, 2007 Abstract Despite the increased pressure on airlines to increase productivity in recent times, a largely overlooked inefficiency in air travel is the board￾ing and unloading process. The typical airline uses a zone system, where passengers board the plane from back to front in several groups. The ef- ficiency of the zone system has come into question with the introduction of the open-seating policy of Southwest Airlines. Despite conventional wisdom, Southwest is able to turnaround planes at an uncanny rate with their innovative methods. Hence, the optimality of the entire boarding process has come into question. We propose a stochastic agent-based simulation of the boarding process in order to explore the effectiveness of novel boarding techniques. Our model organizes the aircraft into discrete units called ‘processors.’ Each processor corresponds to a physical row of the aircraft. Passengers enter the plane and are moved through the aircraft based on the functionality of these processors. During each cycle of our simulation each row (pro￾cessor) can execute a single operation. Operations accomplish functions such as moving passengers to the next row, stowing luggage or seating passengers. The processor model tells us, from an initial ordering of pas￾sengers in a queue, how long the plane will take to board, and produces a grid detailing the chronology of passenger seating. We extend our processor model with a genetic algorithm, which we use to search the space of possible passenger configurations for innovative and effective patterns. This algorithm employs the biological techniques of mutation and crossover to seek out locally optimal solutions to the pas￾senger boarding problem. We create a variant of this algorithm which is designed to optimize a priori boarding patterns. We also integrate a Markov chain model of passenger preference with our processor model. We use this preference model to produce a simulation of Southwest-style boarding, where seats are not assigned but are chosen by individuals based on environmental constraints (such as seat availability). 1

Team 2056 Page 2 of 50 We validated our model using tests for rigor in both robustness and sen sitivity. We find that in robustness test cases that our model makes pre- dictions that correlate well with empirical evidence We simulate many different a priori configurations, such as back to front window to aisle and alternate half-rows When normalized to a random boarding sequence, we found that window to aisle, the best performing pattern, improved efficiency by 36% on average. Even more surprising he most common technique, zone boarding, performed even worse than random. We compare these techniques to novel boarding sequences de- veloped using our genetic algorithm Based on the output of our genetic algorithm, we recommend a hybrid boarding process: a combination of window to aisle and alternate half- ows. This technique is a three-zone process, like window to aisle, but it allows family units to board first, simultaneously with window seat

Team 2056 Page 2 of 50 We validated our model using tests for rigor in both robustness and sen￾sitivity. We find that in robustness test cases that our model makes pre￾dictions that correlate well with empirical evidence. We simulate many different a priori configurations, such as back to front, window to aisle and alternate half-rows. When normalized to a random boarding sequence, we found that window to aisle, the best performing pattern, improved efficiency by 36% on average. Even more surprising, the most common technique, zone boarding, performed even worse than random. We compare these techniques to novel boarding sequences de￾veloped using our genetic algorithm. Based on the output of our genetic algorithm, we recommend a hybrid boarding process; a combination of window to aisle and alternate half￾rows. This technique is a three-zone process, like window to aisle, but it allows family units to board first, simultaneously with window seat passengers

Team 2056 Page 3 of 50 Contents 1 Introduction 1.1 Restatement of the Problem 1.2 Survey of Previous Research 1.2.1 Discrete Random process 566 1.2.2 Other Simulation Studies 2 Model overview 3 Details of the model 799 3.1 Basic model 3.2 Extended Model 3.2.1 Seat assignment 3.2.2 Seat collision 3.2.3 Baggage 3.2.4 Queue size 3.2.5 Planes with multiple aisles B45678 3.2.6 Deplaning 3.3 Boarding time optimization using a genetic algorithm 19 3.3.1 Mutation and Crossover 3.2 Population 1g 3.4 The Southwest Model: integrating passenger prefer ence to our processor-based model 23 3.4.1 Model Overview 23 3.4.2 Assumptions made in Section 4 Boarding Patterns 4. 1 Random Boarding Process 4.3 Alternating Half-Rows boarding process Zone boarding pr 4.5 Reverse Pyramid Process 31 5 Results 5.1 Window to Aisle 5.2 Alternate half-Row 5.3 Back to Front 5.5 Southwest Passenger Preference

Team 2056 Page 3 of 50 Contents 1 Introduction 5 1.1 Restatement of the Problem . . . . . . . . . . . . . . 5 1.2 Survey of Previous Research . . . . . . . . . . . . . . 6 1.2.1 Discrete Random Process . . . . . . . . . . . 6 1.2.2 Other Simulation Studies . . . . . . . . . . . . 7 2 Model Overview 7 3 Details of the Model 9 3.1 Basic Model . . . . . . . . . . . . . . . . . . . . . . . 9 3.2 Extended Model . . . . . . . . . . . . . . . . . . . . . 13 3.2.1 Seat assignment . . . . . . . . . . . . . . . . . 13 3.2.2 Seat collisions . . . . . . . . . . . . . . . . . . 14 3.2.3 Baggage . . . . . . . . . . . . . . . . . . . . . 15 3.2.4 Queue size . . . . . . . . . . . . . . . . . . . . 16 3.2.5 Planes with multiple aisles . . . . . . . . . . . 17 3.2.6 Deplaning . . . . . . . . . . . . . . . . . . . . 18 3.3 Boarding time optimization using a genetic algorithm 19 3.3.1 Mutation and Crossover . . . . . . . . . . . . 20 3.3.2 Population seeding . . . . . . . . . . . . . . . 23 3.4 The Southwest Model: integrating passenger prefer￾ence to our processor-based model . . . . . . . . . . . 23 3.4.1 Model Overview . . . . . . . . . . . . . . . . . 23 3.4.2 Assumptions made in Section . . . . . . . . . 26 4 Boarding Patterns 27 4.1 Random Boarding Process . . . . . . . . . . . . . . . 27 4.2 Window to Aisle Boarding Process . . . . . . . . . . 28 4.3 Alternating Half-Rows Boarding Process . . . . . . . 29 4.4 Zone Boarding Process . . . . . . . . . . . . . . . . . 29 4.5 Reverse Pyramid Process . . . . . . . . . . . . . . . . 31 5 Results 31 5.1 Window to Aisle . . . . . . . . . . . . . . . . . . . . 32 5.2 Alternate Half-Rows . . . . . . . . . . . . . . . . . . 32 5.3 Back to Front . . . . . . . . . . . . . . . . . . . . . . 33 5.4 Reverse Pyramid . . . . . . . . . . . . . . . . . . . . 34 5.5 Southwest Passenger Preference . . . . . . . . . . . . 34

Team 2056 Page 4 of 50 5.6 Genetic Algorithm Applied to a Random Seating Ar- rangement 5.7 Seeded Genetic Algorithm 5.8 Deplaning 5.9 Sensitivity and Robustness Testing 5.9.1 Baggage 5.9.2 Seat collision 5.9.3 Queuing 6 Discussion and conclusions 6. 1 Executive Summary 6. 1.1 Boarding Sequences and Results 6.1.2 Further Optimization 6.1.3 Organizational Change Management and Cus- tomer Relationship management 6.2 Strengths and Weaknesses 6.3 Future Work 7 Appendices 7.1 Appendix A: Past Work 7.2 Appendix B: Preliminary Model 7.3 Appendix C: Definitions and Computations

Team 2056 Page 4 of 50 5.6 Genetic Algorithm Applied to a Random Seating Ar￾rangement . . . . . . . . . . . . . . . . . . . . . . . . 36 5.7 Seeded Genetic Algorithm . . . . . . . . . . . . . . . 37 5.8 Deplaning . . . . . . . . . . . . . . . . . . . . . . . . 37 5.9 Sensitivity and Robustness Testing . . . . . . . . . . 38 5.9.1 Baggage . . . . . . . . . . . . . . . . . . . . . 38 5.9.2 Seat collisions . . . . . . . . . . . . . . . . . . 39 5.9.3 Queuing . . . . . . . . . . . . . . . . . . . . . 39 6 Discussion and Conclusions 39 6.1 Executive Summary . . . . . . . . . . . . . . . . . . . 39 6.1.1 Boarding Sequences and Results . . . . . . . . 40 6.1.2 Further Optimization . . . . . . . . . . . . . . 41 6.1.3 Organizational Change Management and Cus￾tomer Relationship Management . . . . . . . 42 6.2 Strengths and Weaknesses . . . . . . . . . . . . . . . 42 6.3 Future Work . . . . . . . . . . . . . . . . . . . . . . . 43 7 Appendices 45 7.1 Appendix A: Past Work . . . . . . . . . . . . . . . . 45 7.2 Appendix B: Preliminary Model . . . . . . . . . . . . 47 7.3 Appendix C: Definitions and Computations . . . . . 48

Team 2056 Page 5 of 50 1 Introduction Flight technology has come a long way since the glider flown by Orville and Wilbur during the autumn of 1903. Unlike aircraft so- phistication however, passenger boarding techniques have seen lit tle evolution much to the dismay of frequent fiers who have to wade through the narrow aisles of airplanes and wait for granny to stow away gifts for each of her 20 grandchildren. As the ti- tle of a New York Times article emphatically suggests, ' Loadin an Airliner is Rocket Science. Boarding time not only determines airplane productivity but also impacts customer satisfaction. Pro- longed boarding markedly reduces passengers' perception of quality and considerably increases total airplane turnaround time. The lat- ter is particularly critical over short flights where a few additional minutes spent boarding can throw off the day' s schedule. This pa- per simulates different patterns of boarding sequences to determine the optimal method of plane boarding 1.1 Restatement of the problem The truth about the airline industry is that passengers have place to be and people to see; airlines have planes to fly and dollars to dry In a utopia founded on world peace, sated bellies and zero boarding or deplaning times, it is difficult to imagine passengers and airlines having anything to whine about. But utopian dreams are but fan- tasies. Unfortunately, passengers and airlines have to contend with the frustration of waiting when boarding and deplaning. Both pas- sengers and airlines thus have vested interests in the development of boarding and deplaning patterns that minimize waiting times. This is particularly true for the airlines, where the benefit of short board- ing and deplaning times is two-fold higher airplane productivity and greater customer satisfaction. However, given the constraints that airlines operate under- the structure of planes and the infras- tructure of airports- the only mechanisms for minimizing waiting times at the airlines' disposal are the boarding and deplaning se- quences When passengers board a plane, congestion builds in aisles as pas- sengers stumble through the aisles or attempt to stow their luggage in the overhead compartments. Congestion also results due to seat

Team 2056 Page 5 of 50 1 Introduction Flight technology has come a long way since the glider flown by Orville and Wilbur during the autumn of 1903. Unlike aircraft so￾phistication however, passenger boarding techniques have seen lit￾tle evolution – much to the dismay of frequent fliers who have to wade through the narrow aisles of airplanes and wait for granny to stow away gifts for each of her 20 grandchildren. As the ti￾tle of a New York Times article emphatically suggests, ’Loading an Airliner is Rocket Science.’ Boarding time not only determines airplane productivity but also impacts customer satisfaction. Pro￾longed boarding markedly reduces passengers’ perception of quality and considerably increases total airplane turnaround time. The lat￾ter is particularly critical over short flights where a few additional minutes spent boarding can throw off the day’s schedule. This pa￾per simulates different patterns of boarding sequences to determine the optimal method of plane boarding. 1.1 Restatement of the Problem The truth about the airline industry is that passengers have places to be and people to see; airlines have planes to fly and dollars to dry. In a utopia founded on world peace, sated bellies and zero boarding or deplaning times, it is difficult to imagine passengers and airlines having anything to whine about. But utopian dreams are but fan￾tasies. Unfortunately, passengers and airlines have to contend with the frustration of waiting when boarding and deplaning. Both pas￾sengers and airlines thus have vested interests in the development of boarding and deplaning patterns that minimize waiting times. This is particularly true for the airlines, where the benefit of short board￾ing and deplaning times is two-fold – higher airplane productivity and greater customer satisfaction. However, given the constraints that airlines operate under – the structure of planes and the infras￾tructure of airports – the only mechanisms for minimizing waiting times at the airlines’ disposal are the boarding and deplaning se￾quences. When passengers board a plane, congestion builds in aisles as pas￾sengers stumble through the aisles or attempt to stow their luggage in the overhead compartments. Congestion also results due to seat

Team 2056 Page 6 of 50 collisions where passengers have to leave their seats to make way for passengers assigned seats closer to the windows. Ultimately, con- gestion disrupts the smooth How of passengers to their seats and prolongs boarding Successful boarding sequences not only minimize congestion but also llow passengers access to different parts of the plane in parallel that many passengers can stow their luggage and find their seats at the same time. In addition, these sequences must also be sufficiently robust to accommodate stochastic variability in boarding While it is not difficult to develop solutions that specify the boarding and deplaning sequence of each passenger, such solutions are difficult to implement. Appropriate treatment of the problem calls for careful and balanced analyses that weigh the practicality of implementa- tion, performance and variability 1.2 Survey of Previous Research 1.2.1 Discrete Random process In an article by Bachmat et al., the group proposed a discrete ing process in which passengers are assigned seats before boar The input to the process is an index for the position of each passen- ger in the queue and a seat assignment for each passenger. Addi- tionally, the researchers defined the aisle space that each passenger occupies, the time it takes to clear the aisle once the designated row is reached. and the distance between consecutive rows The former two parameters were sampled from distributions defined by the re- searcher The model considers the travel path of each passenger. The pas- senger moves as far down the aisle as they can until they reach obstacle, which is either the back of a queue or a person who is preparing to sit in their row. Passengers who arrive at their row clear the aisle after a delay time. The passengers behind them con tinue on their journey down the aisle once this delay time is over An important component of this process is that passengers may have to wait for other passengers to stow away luggage before being free to progress to their own seats. It follows that passengers can block other passengers, thus resulting in the formation of a queue

Team 2056 Page 6 of 50 collisions where passengers have to leave their seats to make way for passengers assigned seats closer to the windows. Ultimately, con￾gestion disrupts the smooth flow of passengers to their seats and prolongs boarding. Successful boarding sequences not only minimize congestion but also allow passengers access to different parts of the plane in parallel, so that many passengers can stow their luggage and find their seats at the same time. In addition, these sequences must also be sufficiently robust to accommodate stochastic variability in boarding. While it is not difficult to develop solutions that specify the boarding and deplaning sequence of each passenger, such solutions are difficult to implement. Appropriate treatment of the problem calls for careful and balanced analyses that weigh the practicality of implementa￾tion, performance and variability. 1.2 Survey of Previous Research 1.2.1 Discrete Random Process In an article by Bachmat et al., the group proposed a discrete board￾ing process in which passengers are assigned seats before boarding. The input to the process is an index for the position of each passen￾ger in the queue and a seat assignment for each passenger. Addi￾tionally, the researchers defined the aisle space that each passenger occupies, the time it takes to clear the aisle once the designated row is reached, and the distance between consecutive rows. The former two parameters were sampled from distributions defined by the re￾searchers. The model considers the travel path of each passenger. The pas￾senger moves as far down the aisle as they can until they reach an obstacle, which is either the back of a queue or a person who is preparing to sit in their row. Passengers who arrive at their row clear the aisle after a delay time. The passengers behind them con￾tinue on their journey down the aisle once this delay time is over. An important component of this process is that passengers may have to wait for other passengers to stow away luggage before being free to progress to their own seats. It follows that passengers can block other passengers, thus resulting in the formation of a queue

Team 2056 Page 7 of 50 The researchers define an ordering relation between passengers. Each passenger can then be assigned a pointer which points to the last passenger that blocked their path. By following the trail of pas- sengers, the longest chain in the ordering ending at any particular passenger can be identified. This identifies the number of rounds that is needed for the simulation 1.2.2 Other Simulation Studies In 'A simulation study of Passenger Boarding Times in Airplanes H Van Landeghem argues emphatically the two-fold benefits of min- imizing total boarding times. Prolonged boarding not only degrades customers' perception of quality but also determines total airplane turnaround time and therefore airline efficiency. In his paper, Lan deghem defines total boarding time as the interval between the point the first passenger enters the plane to the point the last passenger is seated in his/her assigned seat. To determine the ideal boarding procedure, Landeghem simulates different patterns of boarding se- quences in Arena. His simulations are based on an airplane with 132 seats divided into 23 rows with Row 1 and 23 having 3 seats and the others having 6. Through the simulations, the first objective is o reduce total boarding time. The second objective is to augment the quality perception of the passengers by evaluating the average and maximum individual boarding times as seen by the passenger For a further discussion of this model, please see Appendix A 2 Model overview Research into airplane boarding has taken several approaches. Ana lytic approaches to the problem are extremely rare, due to its intrin- sically high parallelism and significant stochastic variability. Most approaches are simulative in nature. Simulation allows for the com- plexity of the problem to be distributed, and hence presents a sim considered a stochastic agent-based approac e model which can be pler formulation. We here present a simulative Our preliminary model (this model is contained in Appendix B) treats the plane as a line, with destinations(seats) at regular dis-

Team 2056 Page 7 of 50 The researchers define an ordering relation between passengers. Each passenger can then be assigned a pointer which points to the last passenger that blocked their path. By following the trail of pas￾sengers, the longest chain in the ordering ending at any particular passenger can be identified. This identifies the number of rounds that is needed for the simulation. 1.2.2 Other Simulation Studies In ’A simulation study of Passenger Boarding Times in Airplanes,’ H. Van Landeghem argues emphatically the two-fold benefits of min￾imizing total boarding times. Prolonged boarding not only degrades customers’ perception of quality but also determines total airplane turnaround time and therefore airline efficiency. In his paper, Lan￾deghem defines total boarding time as the interval between the point the first passenger enters the plane to the point the last passenger is seated in his/her assigned seat. To determine the ideal boarding procedure, Landeghem simulates different patterns of boarding se￾quences in Arena. His simulations are based on an airplane with 132 seats divided into 23 rows with Row 1 and 23 having 3 seats and the others having 6. Through the simulations, the first objective is to reduce total boarding time. The second objective is to augment the quality perception of the passengers by evaluating the average and maximum individual boarding times as seen by the passengers. For a further discussion of this model, please see Appendix A. 2 Model Overview Research into airplane boarding has taken several approaches. Ana￾lytic approaches to the problem are extremely rare, due to its intrin￾sically high parallelism and significant stochastic variability. Most approaches are simulative in nature. Simulation allows for the com￾plexity of the problem to be distributed, and hence presents a sim￾pler formulation. We here present a simulative model which can be considered a stochastic agent-based approach. Our preliminary model (this model is contained in Appendix B) treats the plane as a line, with destinations (seats) at regular dis-

Team 2056 Page 8 of 50 tances along the line. Each passenger is modeled as an agent, and moves along the line until reaching his seat. Each agent has a speed and is constrained by the slowest person in front of him. This sim plest model is merely a prototype, and is not used to derive experi- mental results Our basic model takes into account the topology of the airplane Each row of the plane is broken into a discrete unit. We call these units'processors' since they determine the rate that an individual moves through the system. Each processor has a queue, a list of people waiting to be processed by it (and hence moved to the next node of the system). Each agent has a particular destination pro- cessor. the row where his seat is assigned The extended model adds additional parameters into the simula- tion. For the first time, there is a one-to-one mapping of passengers to seats. This layer accounts for passengers bringing baggage onto the plane. We call a scenario where a passenger is waiting on an- ger to stow his baggage a baggage collision. W model seat collisions. A seat collision occurs when a passenger is sitting between another passenger and his seat(e. g, the passenger with an assigned window seat must move around a passenger who is sitting next to the aisle) Our next model attempts to optimize boarding time based on the order that passengers enter the plane. This is implemented using a genetic algorithm over the search space of all possible orderings Crossovers and mutations occur. with the restriction that each al teration of seat ordering must preserve the property that every seat is represented Our final model is a Markov chain used to model passenger pref erences in an open seating environment. This model simulates a boarding process such as is used by Southwest airlines We combine our models holistically, and each model interacts benefi cially with the other models described. The extended model is com- bined with the genetic model and the passenger preference model to analyze certain test scenarios. All of our results have the extended

Team 2056 Page 8 of 50 tances along the line. Each passenger is modeled as an agent, and moves along the line until reaching his seat. Each agent has a speed, and is constrained by the slowest person in front of him. This sim￾plest model is merely a prototype, and is not used to derive experi￾mental results. Our basic model takes into account the topology of the airplane. Each row of the plane is broken into a discrete unit. We call these units ‘processors’ since they determine the rate that an individual moves through the system. Each processor has a queue, a list of people waiting to be processed by it (and hence moved to the next node of the system). Each agent has a particular destination pro￾cessor, the row where his seat is assigned. The extended model adds additional parameters into the simula￾tion. For the first time, there is a one-to-one mapping of passengers to seats. This layer accounts for passengers bringing baggage onto the plane. We call a scenario where a passenger is waiting on an￾other passenger to stow his baggage a baggage collision. We also model seat collisions. A seat collision occurs when a passenger is sitting between another passenger and his seat (e.g., the passenger with an assigned window seat must move around a passenger who is sitting next to the aisle). Our next model attempts to optimize boarding time based on the order that passengers enter the plane. This is implemented using a genetic algorithm over the search space of all possible orderings. Crossovers and mutations occur, with the restriction that each al￾teration of seat ordering must preserve the property that every seat is represented. Our final model is a Markov chain used to model passenger pref￾erences in an open seating environment. This model simulates a boarding process such as is used by Southwest Airlines. We combine our models holistically, and each model interacts benefi- cially with the other models described. The extended model is com￾bined with the genetic model and the passenger preference model to analyze certain test scenarios. All of our results have the extended

Team 2056 Page 9 of 50 Fumble Processor Processor Queue Go to seat Go to seat Figure 1: Basic processor based moo model at their heart. This allows us to compare results over dif- ferent test cases. and generate a macroscopic view of the airplane boarding problem 3 Details of the model We will begin with a description of the model, beginning with the basic algorithm and then continuing with its extensions 3.1 Basic model The basic model is the foundation of our experimental results. We model the topology of the plane using a compartment divide the plane into compartments called processors. Each pro- cessor is physically analogous to the space of one row in the plane By using differing layouts of processors, we can model a variety of plane topologies In the basic model, each passenger is randomly assigned to a seat on the plane. These seats are not necessarily unique: they are uni-

Team 2056 Page 9 of 50 Figure 1: Basic processor based model model at their heart. This allows us to compare results over dif￾ferent test cases, and generate a macroscopic view of the airplane boarding problem. 3 Details of the Model We will begin with a description of the model, beginning with the basic algorithm and then continuing with its extensions. 3.1 Basic Model The basic model is the foundation of our experimental results. We model the topology of the plane using a compartmental model. We divide the plane into compartments called ‘processors.’ Each pro￾cessor is physically analogous to the space of one row in the plane. By using differing layouts of processors, we can model a variety of plane topologies. In the basic model, each passenger is randomly assigned to a seat on the plane. These seats are not necessarily unique: they are uni-

Team 2056 Page 10 of 50 formly drawn from all seats on the plane. Every seat is represented as a coordinate pair (c, r), where r is a row of the plane and c a specific seat number. In most modern aircraft, the seat number is given a letter name A is usually the leftmost window seat nd'C' the aisle seat). However, for simplicity we retain the use of numerical coordinates Instead of each passenger being assigned a rate of movement through the plane, in this model, the passengers move based on the function of the processors. The processors are in series, with each proces- sor having the next processor as one output(see figure 1). Since movement is performed by processors pushing passengers from one row to the next, each passenger stores only his destination. When a passenger reaches a certain processor, he waits in a queue to be processed. The queue is first in, first out, so that individual waiting time can be minimized.(Furthermore, this is congruent with the obvious physical constraint that people cannot move around each other while in the aisle. )The initial state of the plane is that passengers are queued at the first processor During each iteration of the simulation, each processor is able to perform one computation. This computation looks at the destin tion of the passenger The function performed can be any of the following Pass. The normal behavior for the processor in cases where the passenger's destination is further along the plane is to allow the passenger to pass. When the passenger passes, he moves from the current processor to the end of the queue of the next Fumble. With a certain small probability, the processor will do nothing this cycle. This is the chance that a bag will get the aisle, that a pa that othe time-wasting random event occurs. (Note that a fumble not equivalent to time spent stowing baggage or rearranging passengers. Our basic model only accounts for random time- Sit Down. If this row contains the assigned seat for the pas- senger currently in the processor, the passenger leaves the aisle

Team 2056 Page 10 of 50 formly drawn from all seats on the plane. Every seat is represented as a coordinate pair (c,r), where r is a row of the plane and c is a specific seat number. In most modern aircraft, the seat number is given a letter name (e.g., ‘A’ is usually the leftmost window seat and ‘C’ the aisle seat). However, for simplicity we retain the use of numerical coordinates. Instead of each passenger being assigned a rate of movement through the plane, in this model, the passengers move based on the function of the processors. The processors are in series, with each proces￾sor having the next processor as one output (see figure 1). Since movement is performed by processors pushing passengers from one row to the next, each passenger stores only his destination. When a passenger reaches a certain processor, he waits in a queue to be processed. The queue is first in, first out, so that individual waiting time can be minimized. (Furthermore, this is congruent with the obvious physical constraint that people cannot move around each other while in the aisle.) The initial state of the plane is that all passengers are queued at the first processor. During each iteration of the simulation, each processor is able to perform one computation. This computation looks at the destina￾tion of the passenger. The function performed can be any of the following: • Pass. The normal behavior for the processor in cases where the passenger’s destination is further along the plane is to allow the passenger to pass. When the passenger passes, he moves from the current processor to the end of the queue of the next processor. • Fumble. With a certain small probability, the processor will do nothing this cycle. This is the chance that a bag will get caught in the aisle, that a passenger trips, or that some other time-wasting random event occurs. (Note that a fumble is not equivalent to time spent stowing baggage or rearranging passengers. Our basic model only accounts for random time￾wasting events.) • Sit Down. If this row contains the assigned seat for the pas￾senger currently in the processor, the passenger leaves the aisle