《数学建模》美赛优秀论文：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