Performance of Multiple Cabin Optimization Methods in Airline Revenue Management by Pierre-Olivier Lepage B.Eng., Industrial Engineering, E´cole Polytechnique de Montr´eal, 2010 Submitted to the Department of Civil and Environmental Engineering and Sloan School of Management in partial fulfillment of the requirements for the degrees of Master of Science in Transportation and Master of Science in Operations Research at the Massachusetts Institute of Technology June 2013 (cid:13)c 2013 Massachusetts Institute of Technology All Rights Reserved. Signature of Author: Department of Civil and Environmental Engineering and Sloan School of Management May 10, 2013 Certified by: Peter P. Belobaba Principal Research Scientist, Aeronautics and Astronautics Thesis Supervisor Certified by: Cynthia Barnhart Ford Professor, Civil and Environmental Engineering and Engineering Systems Associate Dean, School of Engineering Thesis Reader Accepted by: Heidi Nepf Chair, Department Committee for Graduate Students Accepted by: Patrick Jaillet Dugald C. Jackson Professor, Electrical Engineering and Computer Science Co-Director, Operations Research Center 2 Performance of Multiple Cabin Optimization Methods in Airline Revenue Management by Pierre-Olivier Lepage Submitted to the Department of Civil and Environmental Engineering and Sloan School of Management on May 10, 2013, in partial fulfillment of the requirements for the degrees of Master of Science in Transportation and Master of Science in Operations Research Abstract Althoughmanyairlinesofferseatsinmultiplecabins(economyvs. premiumclasses) with different service quality, previous work on airline revenue management has focused on treating the cabins separately. In this thesis, we develop several single-leg multiple cabin revenue management optimization algorithms. We extend two different single-leg separate cabin dynamic programming algorithms to the multiple cabin case, and also present three Expected Marginal Seat Revenue (EMSR) based heuristics and a dynamic programming decom- position heuristic. We then evaluate the revenue and passenger mix performance of the different algorithms using the Passenger Origin-Destination Simulator (PODS) which simulates competitive markets with passenger choice of fare options and cabin. We first testthemethodsinasimplesinglemarketnetworkandtheninamorerealisticcomplex network. We find that multiple cabin methods do not lead to a systematic revenue increase. Indeed, simulation results show that the performance of the different methods ranges from a decrease of 9.6% to an increase of 2.4% in revenues. The discrepancies in performance between the different methods are explained by the trade-off between rev- enue gains from additional economy bookings and the losses from displaced premium passengers. Further, we observe that successful methods lead to a revenue increase by accepting additional bookings in top economy classes rather than in low economy classes. Finally, the poor performance of the dynamic programming methods tested is due to a misalignment between the underlying assumptions of the algorithms and the reality of the booking and passenger choice process. Thesis Supervisor: Peter P. Belobaba Title: Principal Research Scientist, Aeronautics and Astronautics Thesis Reader: Cynthia Barnhart Title: Ford Professor, Civil and Environmental Engineering and Engineering Systems, Associate Dean, School of Engineering 3 4 Acknowledgments This thesis marks the end of my three-year MIT journey. I feel extremely privileged to become an MIT alumni, and I believe it would not have been possible without the help and support of many people. I would like to thank some of them more specifically. First, I would like to acknowledge my thesis supervisor Dr. Peter P. Belobaba for his insightful comments and thoughtful advice. Working with Peter has been a great pleasure and an outstanding learning experience. I would like to thank Professor Cynthia Barnhart for providing helpful feedback on this thesis. I would also like to thank Professor Amedeo R. Odoni for his advice on my career path. I would like to thank the MIT PODS consortium member airlines who supported me financially and whose input increased the practicality of my work. More specifi- cally, thanks to Thomas Fiig, Stefan Poelt, and Craig Hopperstad for their help with developing the different algorithms presented in this thesis. Thanks to my colleagues and friends who made my MIT experience a lot more enjoyable. Thanks to my fellow PODS students Claire Cizaire, Himanshu Jain, Aly- ona Michel, Vincent Surges, and Michael Abramovich for the discussions and the fun. Thanks to my friends at the Consulting Club at MIT for helping me improve on my business skills. Thanks to my friends involved in the Sidney-Pacific Graduate Commu- nity who definitely made me feel home away from home. A special thank to George H. Chen, Jennifer Jarvis, Steve Morgan, and Stephanie Nam for our awesome year serving on SPEC. Thanks also to Professor Roger G. Mark, to his wife Dorothy, to Professor Annette Kim, and her husband Roland Tang for helping me grow both personally and professionally. Finally, I want to recognize the contribution of those who, directly or indirectly, gave me the opportunities I needed to end up at the Institute. Thanks to the Province of Quebec for giving me an affordable and high quality education. Thanks to Professor Michel Gamache of E´cole Polytechinique de Montr´eal for introducing me to Opera- tions Research. Thanks to Jean-Fran¸cois Pag´e at Air Canada for giving me my first opportunity in the airline industry. Finalement, j’aimerais d´edier ce m´emoire `a ma m`ere, mon p`ere et ma soeur. Merci pour les fous rires, merci de vous assurer que je garde toujours les deux pieds sur terre, merci de faire de mon monde un endroit ou` il fait bon vivre. 5 6 Contents Abstract 3 Acknowledgments 4 List of Figures 9 List of Tables 11 1 Introduction 13 1.1 Airline revenue management concepts . . . . . . . . . . . . . . . . . . . 13 1.1.1 Differential pricing . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.1.2 Revenue management . . . . . . . . . . . . . . . . . . . . . . . . 16 1.2 Problem definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.2.1 Separate vs multiple cabin . . . . . . . . . . . . . . . . . . . . . . 18 1.2.2 Passenger decision process . . . . . . . . . . . . . . . . . . . . . . 19 1.2.3 Airline decision process . . . . . . . . . . . . . . . . . . . . . . . 20 1.3 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.4 Structure of the thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2 Literature Review 23 2.1 Separate cabin revenue management problem . . . . . . . . . . . . . . . 23 2.1.1 Lautenbacher-Stidham dynamic programming . . . . . . . . . . . 23 2.1.2 Higher demand variance in dynamic programming . . . . . . . . 25 2.1.3 Expected Marginal Seat Revenue (EMSR) . . . . . . . . . . . . . 27 2.2 Multiple cabin revenue management problem . . . . . . . . . . . . . . . 28 2.2.1 Multiple product upgrades . . . . . . . . . . . . . . . . . . . . . 28 2.2.2 Shared nesting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.3 Chapter summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3 Dynamic Formulations and Heuristics 31 3.1 Multiple cabin dynamic programming (DP) formulations . . . . . . . . . 31 3.1.1 Multiple cabin DP . . . . . . . . . . . . . . . . . . . . . . . . . . 31 7 8 CONTENTS 3.1.2 Multiple Cabin DP with Variance . . . . . . . . . . . . . . . . . 33 3.2 Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.2.1 Shared nesting with EMSR . . . . . . . . . . . . . . . . . . . . . 34 3.2.2 Multiple cabin DP heuristic . . . . . . . . . . . . . . . . . . . . . 39 3.3 Chapter summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4 Simulation and Results 41 4.1 Simulator description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.1.1 Passenger Choice Model . . . . . . . . . . . . . . . . . . . . . . . 43 4.1.2 Revenue Management System . . . . . . . . . . . . . . . . . . . . 44 4.2 Performance indicators . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.3 Results. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 4.3.1 Network and fare structure . . . . . . . . . . . . . . . . . . . . . 47 4.3.2 Base case scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.3.3 Performance evaluation . . . . . . . . . . . . . . . . . . . . . . . 58 4.4 Chapter summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 5 Conclusion 81 5.1 Contribution and findings . . . . . . . . . . . . . . . . . . . . . . . . . . 81 5.2 Directions for further research . . . . . . . . . . . . . . . . . . . . . . . . 82 Bibliography 85 List of Figures 1.1 Potential revenue with a single fare (A) and multiple fares (differential pricing) (B) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.2 Nested booking limits [1]. . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.3 Airline operation planning process [5] . . . . . . . . . . . . . . . . . . . 17 1.4 Passenger itinerary choice . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.5 Airline information structure . . . . . . . . . . . . . . . . . . . . . . . . 20 3.1 Cabin EMSR values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.2 Three different separate cabin DP problems . . . . . . . . . . . . . . . . 40 4.1 PODS Architecture representation [4] . . . . . . . . . . . . . . . . . . . 42 4.2 Passenger arrival curves . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.3 Airline 1 class closure rates in single market scenario at low demand . . 52 4.4 Airline 1 class closure rates in single market scenario at medium demand 53 4.5 Airline 1 class closure rates in single market scenario at high demand . . 53 4.6 Airline 1 class closure rates in realistic network scenario at low demand 56 4.7 Airline1classclosureratesinrealisticnetworkscenarioatmediumdemand 57 4.8 Airline 1 class closure rates in realistic network scenario at high demand 57 4.9 Relative revenue change over base case in single market scenario at low demand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.10 Relative revenue change over base case in single market scenario at medium demand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.11 Relative revenue change over base case in single market scenario at high demand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.12 Load factors in single market scenario at low demand . . . . . . . . . . 60 4.13 Load factors in single market scenario at medium demand . . . . . . . . 61 4.14 Load factors in single market scenario at high demand . . . . . . . . . . 61 4.15 Cabin load factors in single market scenario at low demand . . . . . . . 62 4.16 Cabin load factors in single market scenario at medium demand . . . . . 63 4.17 Cabin load factors in single market scenario at high demand . . . . . . . 63 4.18 Fare class mix in single market scenario at low demand . . . . . . . . . 64 9 10 LISTOFFIGURES 4.19 Fare class mix in single market scenario at medium demand . . . . . . . 64 4.20 Fare class mix in single market scenario at high demand . . . . . . . . . 65 4.21 Closure rates in single market scenario at low demand . . . . . . . . . . 66 4.22 Closure rates in single market scenario at medium demand . . . . . . . 66 4.23 Closure rates in single market scenario at high demand . . . . . . . . . . 67 4.24 Relative revenue change over base case in realistic network scenario at low demand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 4.25 Relative revenue change over base case in realistic network scenario at medium demand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 4.26 Relative revenue change over base case in realistic network scenario at high demand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 4.27 Load factor in realistic network scenario at low demand . . . . . . . . . 71 4.28 Load factor in realistic network scenario at medium demand . . . . . . . 71 4.29 Load factor in realistic network scenario at high demand . . . . . . . . . 72 4.30 Cabin load factor in realistic network scenario at low demand . . . . . . 72 4.31 Cabin load factor in realistic network scenario at medium demand . . . 73 4.32 Cabin load factor in realistic network scenario at high demand . . . . . 73 4.33 Fare class mix in realistic network scenario at low demand . . . . . . . . 74 4.34 Fare class mix in realistic network scenario at medium demand . . . . . 75 4.35 Fare class mix in realistic network scenario at high demand . . . . . . . 75 4.36 Closure rates in realistic network scenario at low demand . . . . . . . . 76 4.37 Closure rates in realistic network scenario at medium demand . . . . . . 76 4.38 Closure rates in realistic network scenario at high demand . . . . . . . . 77