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

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