haihongyuan.com

# 2007美国大学生数学建模竞赛B题特等奖论文

American Airlines' Next Top Model

Sara J. Beck

Spencer D. K'Burg

Alex B. Twist

University of Puget Sound

Tacoma, WA

Summary

We design a simulation that replicates the behavior of passengers boarding airplanes of different sizes according to procedures currently implemented, as well as a plan not currently in use. Variables in our model are deterministic or stochastic and include walking time, stowage time, and seating time. Boarding delays are measured as the sum of these variables. We physically model and observe common interactions to accurately reflect boarding time.

We run 500 simulations for various combinations of airplane sizes and boarding plans. We analyze the sensitivity of each boarding algorithm, as well as the passenger movement algorithm, for a wide range of plane sizes and configurations. We use the simulation results to compare the effectiveness of the boarding plans. We find that for all plane sizes, the novel boarding plan Roller Coaster is the most efficient. The Roller Coaster algorithm essentially modifies the outside-in boarding method. The passengers line up before they board the plane and then board the plane by letter group. This allows most interferences to be avoided. It loads a small plane 67% faster than the next best option, a midsize plane 37% faster than the next best option, and a large plane 35% faster than the next best option.

Introduction

The objectives in our study are:

To board (and deboard) various sizes of plane as quickly as possible.

"* To find a boarding plan that is both efficient (fast) and simple for the passengers.

With this in mind:

"* We investigate the time for a passenger to stow their luggage and clear the aisle.

"* We investigate the time for a passenger to clear the aisle when another passenger is seated between them and their seat.

* We review the current boarding techniques used by airlines.

* We study the floor layout of planes of three different sizes to compare any difference between the efficiency of a given boarding plan as plane size increases and layouts vary.

"* We construct a simulator that mimics typical passenger behavior during the boarding processes under different techniques.

"* We realize that there is not very much time savings possible in deboarding while maintaining customer satisfaction.

"* We calculate the time elapsed for a given plane to load under a given boarding plan by tracking and penalizing the different types of interferences that occur during the simulations.

"* As an alternative to the boarding techniques currently employed, we suggest an alternative plan and

assess it using our simulator.

"* We make recommendations regarding the algorithms that proved most efficient for small, midsize, and large planes.

Interferences and Delays for Boarding

There are two basic causes for interference-someone blocking a passenger,in an aisle and someone blocking a passenger in a row. Aisle interference is caused when the passenger ahead of you has stopped moving and is preventing you from continuing down the aisle towards the row with your seat. Row interference is

caused when you have reached the correct row but already-seated passengers between the aisle and your seat are preventing you from immediately taking your seat. A major cause of aisle interference is a passenger experiencing row

interference.

We conducted experiments, using lined-up rows of chairs to simulate rows in an airplane and a team

member with outstretched arms to act as an overhead compartment, to estimate parameters for the delays cause by these actions. The times that we found through our experimentation are given in Table 1.

We use these times in our simulation to model the speed at which a plane can be boarded. We model separately the delays caused by aisle interference and row interference. Both are simulated using a mixed distribution definedas follows:

Y = min{2, X},

where X is a normally distributed random variable whose mean and standard deviation are fixed in our experiments. We opt for the distribution being partially normal with a minimum of 2 after reasoning that other alternative and common distributions (such as the exponential) are too prone to throw a small value, which is unrealistic. We find that the average row interference time is approximately 4 s with a standard deviation of 2 s, while the average aisle interference time is approximately 7 s with a standard deviation of 4 s. These values are slightly adjusted based on our team's cumulative experience on airplanes.

Typical Plane Configurations

Essential to our model are industry standards regarding common layouts of passenger aircraft of varied sizes. We use an Airbus 320 plane to model a small plane (85-210 passengers) and the Boeing 747 for a midsize plane (210-330 passengers). Because of the lack of large planes available on the market, we modify the Boeing 747 by eliminating the first-class section and extending the coach section to fill the entire plane. This puts the Boeing 747 close to its maximum capacity. This modified Boeing 747 has 55 rows, all with the same dimensions as the coach section in the standard Boeing 747. Airbus is in the process of designing planes that can hold up to 800 passengers. The Airbus A380 is a double-decker with occupancy of 555 people in three different classes; but we exclude double-decker models from our simulation because it is the larger, bottom deck that is the limiting factor, not the smaller upper deck.

Current Boarding Techniques

We examine the following industry boarding procedures:

* random-order

* outside-in

* back-to-front (for several group sizes)

Additionally, we explore this innovative technique not currently used by airlines:

* "Roller Coaster" boarding: Passengers are put in order before they board the plane in a style much like those used by theme parks in filling roller coasters.Passengers are ordered from back of the plane to front, and they board in seatletter groups. This is a modified outside-in technique, the difference being that passengers in the same group are ordered before boarding. Figure 1 shows how this ordering could take place. By doing this, most interferences

are avoided.

Current Deboarding Techniques

Planes are currently deboarded in an aisle-to-window and front-to-back order. This deboarding method comes out of the passengers' desire to be off the plane as quickly as possible. Any modification of this technique could lead

to customer dissatisfaction, since passengers may be forced to wait while others seated behind them on the

plane are deboarding.

Boarding Simulation

We search for the optimal boarding technique by designing a simulation that models the boarding process and running the simulation under different plane configurations and sizes along with different boarding algorithms. We then compare which algorithms yielded the most efficient boarding process.

Assumptions

The environment within a plane during the boarding process is far too unpredictable to be modeled accurately. To make our model more tractable,we make the following simplifying assumptions:

"* There is no first-class or special-needs seating. Because the standard industry practice is to board these passengers first, and because they generally make up a small portion of the overall plane capacity, any changes in the overall boarding technique will not apply to these passengers.

"* All passengers board when their boarding group is called. No passengers arrive late or try to board the plane early.

"* Passengers do not pass each other in the aisles; the aisles are too narrow.

"* There are no gaps between boarding groups. Airline staff call a new boarding group before the previous boarding group has finished boarding the plane.

"* Passengers do not travel in groups. Often, airlines allow passengers boarding with groups, especially with younger children, to board in a manner convenient for them rather than in accordance with the boarding plan. These events are too unpredictable to model precisely.

"* The plane is full. A full plane would typically cause the most passenger interferences, allowing us to view the worst-case scenario in our model.

"* Every row contains the same number of seats. In reality, the number of seats in a row varies due to engineering reasons or to accommodate luxury-class passengers.

Implementation

We formulate the boarding process as follows:

"* The layout of a plane is represented by a matrix, with the rows representing rows of seats, and each column describing whether a row is next to the window, aisle, etc. The specific dimensions vary with each plane type. Integer parameters track which columns are aisles.

"* The line of passengers waiting to board is represented by an ordered array of integers that shrinks appropriately as they board the plane.

"* The boarding technique is modeled in a matrix identical in size to the matrix representing the layout of the plane. This matrix is full of positive integers, one for each passenger, assigned to a specific submatrix, representing each passenger's boarding group location. Within each of these submatrices, seating is

assigned randomly torepresent the random order in which passengers line up when their boarding groups are called.

"* Interferences are counted in every location where they occur within the matrix representing the plane layout. These interferences are then cast into our probability distribution defined above, which gives a

measurement of time delay.

"* Passengers wait for interferences around them before moving closer to their assigned seats; if an interference is found, the passenger will wait until the time delay has finished counting down to 0.

"* The simulation ends when all delays caused by interferences have counted down to 0 and all passengers have taken their assigned seats.

Strengths and Weaknesses of the Model

Strengths

"* It is robust for all plane configurations and sizes. The boarding algorithms that we design can be

implemented on a wide variety of planes with minimal effort. Furthermore, the model yields reasonable results as we adjust the

parameters of the plane; for example, larger planes require more time to board, while planes with more aisles can load more quickly than similarlysized planes with fewer aisles.

"* It allows for reasonable amounts of variance in passenger behavior. While with more thorough

experimentation a superior stochastic distribution describing the delays associated with interferences could be found, our simulation

"* It is simple. We made an effort to minimize the complexity of our simulation, allowing us to run more simulations during a greater time period and mini mizing the risk of exceptions and errors occurring.

"* It is fairly realistic. Watching the model execute, we can observe passengers boarding the plane, bumping into each other, taking time to load their baggage, and waiting around as passengers in front of them move out of the

way. Its ability to incorporate such complex behavior and reduce it are key to completing our objective.

Weaknesses

"* It does not account for passengers other than economy-class passengers.

"* It cannot simulate structural differences in the boarding gates which could

possibly speed up the boarding process. For instance, some airlines in Europe

board planes from two different entrances at once.

"* It cannot account for people being late to the boarding gate.

"* It does not account for passenger preferences or satisfaction.

Results and Data Analysis

For each plane layout and boarding algorithm, we ran 500 boarding simulations,calculating mean time and standard deviation. The latter is important because the reliability of plane loading is important for scheduling flights.

We simulated the back-to-front method for several possible group sizes.Because of the difference in the

number of rows in the planes, not all group size possibilities could be implemented on all planes.

Small Plane

For the small plane, Figure 2 shows that all boarding techniques except for the Roller Coaster slowed the boarding process compared to the random boarding process. As more and more structure is added to the boarding process, while passenger seat assignments continue to be random within each of the boarding groups, passenger interference backs up more and more. When passengers board randomly, gaps are created between passengers as some move to the back while others seat themselves immediately upon entering the plane, preventing any more from stepping off of the gate and onto the plane. These gaps prevent passengers who board early and must travel to the back of the plane from causing interference with many passengers behind them. However, when we implement the Roller Coaster algorithm, seat interference is eliminated, with the only passenger causing aisle interference being the very last one to board

from each group.

Interestingly, the small plane's boarding times for all algorithms are greater than their respective boarding time for the midsize plane! This is because the number of seats per row per aisle is greater in the small plane than in the midsize plane.

Midsize Plane

The results experienced from the simulations of the mid-sized plane are

shown in Figure 3 and are comparable to those experienced by the small plane.

Again, the Roller Coaster method proved the most effective.

Large Plane

Figure 4 shows that the boarding time for a large aircraft, unlike the other plane configurations, drops off when moving from the random boarding algorithm to the outside-in boarding algorithm. Observing the movements by the passengers in the simulation, it is clear that because of the greater number of

passengers in this plane, gaps are more likely to form between passengers in the aisles, allowing passengers to move unimpeded by those already on board.

However, both instances of back-to-front boarding created too much structure to allow these gaps to form again. Again, because of the elimination of row interference it provides for, Roller Coaster proved to be the most effective boarding method.

Overall

The Roller Coaster boarding algorithm is the fastest algorithm for any plane size.Compared to the next

fastest boarding procedure, it is 35% faster for a large plane, 37% faster for a midsize plane, and 67% faster for a small plane. The Roller Coaster boarding procedure also has the added benefit of very low standard deviation, thus allowing airlines a more reliable boarding time. The boarding time for the back-to-front algorithms increases with the number of boarding groups and is always slower than a random boarding procedure.

The idea behind a back-to-front boarding algorithm is that interference at the front of the plane is avoided until passengers in the back sections are already on the plane. A flaw in this procedure is that having

everyone line up in the plane can cause a bottleneck that actually increases the loading time. The outside-in ("Wilma," or window, middle, aisle) algorithm performs better than the random boarding procedure only for the large plane. The benefit of the random procedure is that it evenly distributes interferences throughout theplane, so that they are less likely to impact very many passengers.

Validation and Sensitivity Analysis

We developed a test plane configuration with the sole purpose of implementing our boarding algorithms on planes of all sizes, varying from 24 to 600 passengers with both one or two aisles.

We also examined capacities as low as 70%; the trends that we see at full capacity are reflected at these lower capacities. The back-to-front and outside-in algorithms do start to perform better; but this increase in performance is relatively small, and the Roller Coaster algorithm still substantially outperforms them. Under

all circumstances, the algorithms we test are robust. That is, they assign passenger to seats in accordance with the intention of the boarding plans used by airlines and move passengers in a realistic manner.

Recommendations

We recommend that the Roller Coaster boarding plan be implemented for planes of all sizes and

configurations for boarding non-luxury-class and nonspecial needs passengers. As planes increase in size, its margin of success in comparison to the next best method decreases; but we are confident that the Roller Coaster method will prove robust. We recommend boarding groups that are traveling together before boarding the rest of the plane, as such groups would cause interferences that slow the boarding. Ideally, such groups would be ordered before boarding.

Future Work

It is inevitable that some passengers will arrive late and not board the plane at their scheduled time.

Additionally, we believe that the amount of carry-on baggage permitted would have a larger effect on the boarding time than the specific boarding plan implemented-modeling this would prove insightful.

We also recommend modifying the simulation to reflect groups of people traveling (and boarding) together; this is especially important to the Roller Coaster boarding procedure, and why we recommend boarding groups before boarding the rest of the plane.