r FLIGHT TRANSFORTATION LABORATORY ; !f - , f REPORT R 92-3 Airline Network Seat Inventory Control: Methodologies and Revenue Impacts Elizabeth L. Williamson June 1992 ARCHNES Airline Network Seat Inventory Control: Methodologies and Revenue Impacts by Elizabeth Louise Williamson S.B. Massachusetts Institute of Technology (1986) S.M. Massachusetts Institute of Technology (1988) Submitted to the Department of Aeronautics and Astronautics in Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy in Flight Transportation and Operations Research at the Massachusetts Institute of Technology June 1992 @ Massachusetts Institute of Technology 1992 Signature of Author: Department of Aeronautics and Astronautics May 11, 1992 Certified by Peter Belobaba Assistant Professor of Aeronautics and Astronautics Thesis Supervisor Certified by 7 sc-t y - Robert W. Simpson Professor of Aeronautics and Astronautics ,,9irector, Flight Transportation Laboratory Certified by - Arnold Barnett Professor of the Sloan School of Management Accepted by Harold Y. Wachman Professor of Aeronautics and Astronautics Chairman, Departmental Graduate Committee Airline Network Seat Inventory Control: Methodologies and Revenue Impacts by Elizabeth Louise Williamson Submitted to the Department of Aeronautics and Astronautics on May 11, 1992 in partial fulfillment of the requirements for the Degree of Doctor of Philosophy in Flight Transportation and Operations Research Abstract In the airline industry, it is customary for carriers to offer a wide range of fares for any given seat in the same cabin on the same flight. In order to control the number of seats made available in each fare class, airlines practice what is called seat inventory control. Traditionally, airline seat inventory control has been the process of allocating seats among varies fare classes on a flight leg in order to maximize expected revenues. Reservations for travel on a flight leg are accepted based on the availability of a particular fare class on that flight leg. A passenger's ultimate destination, overall itinerary, or total revenue contribution to the airline is not taken into account. The typical route structure of a large airline, however, is built around a complex network of connecting flights. Maximizing revenues on individual flight legs is not the same as maximizing total network revenues. The objective of this dissertation is to address the seat inventory control problem at the network level, taking into account the interaction of flight legs and the flow of traffic across a network. Beginning with the traditional network formulation of the seat inventory control prob- lem, practical approaches for actually controlling seat inventories at the origin-destination and fare class (ODF) level are first discussed. To avoid problems associated with forecast- ing ODF itinerary demand, network methods based on aggregated demand estimates are then presented. Taking the network seat inventory control problem one step closer to fit in with current reservations control capabilities, several leg-based heuristics are introduced. These heuristics take into account information about different ODF passenger demand and traffic flows while optimization and control of seat inventories remains at the flight leg level. In order to effectively measure the revenue potential of the different network seat inven- tory control methods introduced, an integrated optimization/booking process simulation was developed. Specific issues related to realistically modeling the booking process are discussed and the multi-period, computer-based, mathematical simulation described in de- tail. With the use of this integrated optimization/booking process simulation, the revenue impacts of the different network seat inventory control methodologies are then evaluated using real airline data for both a connecting hub network and multiple flight leg networks. Overall performance of each method is examined by comparing the revenue obtained with that of current leg-based control approaches and the maximum revenue potential given perfect information. The performance of the different methods evaluated varies with both the network and the actual demand patterns, however, significant revenue impacts over current seat inven- tory control approaches can be obtained. One approach which consistently performs well is a deterministic network approach in which ODF seat allocations are nested by shadow prices. Depending on the network structure, other leg-based OD control heuristics also perform well. The benefits of network seat inventory control are a function of the load factor across a network. Below an average load factor of about 85%, revenue impacts over effective leg-based control are non-existent. However, as the average load factor increases, revenue impacts on the order of 2-4% are obtainable. Thesis Supervisor: Professor Peter Belobaba Assistant Professor of Aeronautics and Astronautics Acknowledgements I would like to thank my advisor, Professor Peter Belobaba, for all his support during my years as a graduate student at MIT. He has been there from start to finish, helping to develop the direction of this research project, providing guidance along the way, and proof-reading several versions of this manuscript. I would also like to express my gratitude to both my readers, Professor Robert Simpson and Professor Arnold Barnett. They have both contributed a great deal to this research effort with their technical knowledge and helpful suggestions. This research has been partially funded by Air Canada and Northwest Airlines. I would like to particularly acknowledge Yvan Corriveau, Jacques Cherrier, Steve Elkins, and Barry Freedman for technical discussions. I am very grateful to Pat and Brian Dixon for their generosity and love ever since my first term as a freshman at MIT. Also thanks to Lori Martinez and her family for their friendship and encouragement. Thanks to my friends: Tony Lee and Grace Zabat for discussions on their insight into the airline industry, Tom Svrcek for general amusement and Sharon Els for her special friendship. A special thanks to the entire MTL gang for all the good times, especially Joe Lutsky, Kathy Krisch, JP Mattia, Steve Decker, Shujaat Nadeem, Rod Hinman, Gee Rittenhouse, Curtis Tsai, Julie Tsai, Patrice Parris, Andrew Karanicolas, Fritz Herrmann, and Craig Keast. Without my family I would not have made it this far. I sincerely thank them for their love and support throughout my life and for all the special times we have together. Most importantly, I thank my husband, Jeffrey, for always being there. His love and support will always mean the most to me. Lastly, I thank the Lord for giving me the strength and ability to make it this far. Contents 1 Introduction 13 1.1 Goal of Dissertation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.2 Structure of Dissertation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2 Seat Inventory Control 28 2.1 The Seat Inventory Control Problem . . . . . . . . . . . . . . . . . . . . . . 28 2.2 Network Seat Inventory Control . . . . . . . . . . . . . . . . . . . . . . . . . 40 3 Previous Work and Current Practices 47 3.1 Literature Review . . . . . .. . . . . . . . . . . . . . . . . . .. .. .. . 47 3.2 Current Practices in Seat Inventory Control . . . . . . . . . . . . . . . . . . 61 4 Approaches to Network Seat Inventory Control 67 4.1 Network Formulation and Notation . . . .. . . . . . . . . . . . . . .. .. . . 68 4.2 Use of Network Solutions for Control . . . . . . . . . . . . . . . . . . . . . . 73 4.2.1 Partitioned Approaches . . . . . . . . . . . . . . . . . . . . . . . . . 74 4.2.2 Nested Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 4.2.3 Network Bid Prices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 4.3 Aggregated Demand Network Methods . . . . . . . . . . . . . . . . . . . . . 93 4.4 Leg-Based Methodologies for OD Control . . . . . . . . . . . . . . . . . . . 101 4.4.1 Leg-Based Bid Price . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 4.4.2 Combined Leg-Based Bid Price/Booking Limit Approach . . . . . . 109 4.4.3 Virtual Nesting on the "Value Net of Opportunity Cost" . . . . . . . 112 4.4.4 Nested Leg-Based Itinerary Limit . . . . . . . . . . . . . . . . . . . . 118 4.5 Sum m ary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 5 Modeling the Booking Process Through Simulation 128 5.1 Integrated Optimization/Booking Process Simulation . . . . . . . . . . . . . 130 5.2 M odeling Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 6 Analysis and Comparison of Network Seat Inventory Control Approaches 155 6.1 Detailed Analysis and Comparison of Revenue Impacts on Multiple Leg Flights . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 6.1.1 Partitioned Network Methods . . . . . . . . . . . . . . . . . . . . . . 163 6.1.2 Nested Network Heuristics . . . . . . . . . . . . . . . . . . . . . . . . 166 6.1.3 Network Bid Prices . . . . . ........................ . 179 6.1.4 Leg-Based Methodologies for OD Control . . . . . . . . . . . . . . . 197 6.1.5 Summary Comparison of Multiple Flight Leg Revenue Impacts . . . 213 6.2 Comparison of Revenue Impacts on a Hub Network . . . . . . . . . . . . . . 225 6.2.1 Summary Comparison of Hub Network Revenue Impacts . . . . . . 241 l1l11l illlllll li"ni ll i i ei. lIlIi l 6.3 Summary ........ ..................................... 243 7 Conclusion 247 7.1. Summary of Research Findings . . . . . . . . . . . . . . . . . . . . . . . . . 247 7.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 7.3 Future Research Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . 250 Bibliography 254 A Sensitivity Analysis 257 List of Figures 1.1 The Effects of Revenue Management on American Airlines' Profits 1.2 The Effects of Revenue Management on Delta Air Lines' Profits . 1.3 Revenue Management Structural Diagram . . 1.4 Variation in the "Best" Fare Available . . . . 1.5 Computer Reservations System . . . . . . . . 2.1 Revenue Maximization for One Fare Class . . . . . . . . . . . . . . 2.2 Revenue Potential for Four Fare Classes . . . . . . . . . . . . . . 2.3 Over Allocation of Deeply Discount Seats . . . . . . . . . . . . . . 2.4 Under Allocation of Discount Seats . . . . . . . . . . . . . . . . . . 2.5 Advanced Booking Profile . . . . . . . . . . . . . . . . . . . . . . . 2.6 Point-to-Point Network . . . . . . . . . . . . . . . . . . . . . . . . 2.7 Hub-and-Spoke Network . . . . . . . . . . . . . . . . . . . . . . . . 2.8 Simple Multi-Leg Example . . . . . . . . . . . . . . . . . . . . . . . 2.9 Nested Fare Class Structure . . . . . . . . . . . . . . . . . . . . . . 2.10 Partitioned Fare Class Structure . . . . . . . . . . . . . . . . . . . 3.1 Expected Marginal Revenue Curve of an Individual Fare Class 3.2 Slope of an Expected Revenue Function . . . . . . 4.1 Linear Three Leg Example . . . . . . . . . . . . . . . . . . . . . . . . 74 4.2 Estimate of the Probabilistic Shadow Price . . . . . . . . . . . . . . 87 4.3 EMR Curve Based on a Small Standard Deviation . . . . . . . . . . 89 4.4 Small Hub Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 4.5 Expected Marginal Revenue Curve for a Flight Leg . . . . . . . . . . 103 4.6 Virtual Nesting on Fare Value . . . . . . . . . . . . . . . . . . . . . . 113 4.7 Virtual Nesting on the "Value Net of Opportunity Cost" .. . . . . .. 115 4.8 Expected Marginal Revenue Curve for Flight Leg A-B . . . . . . . . 120 4.9 Expected Marginal Revenue Curve for Flight Leg B-C . . . . . . . . 121 4.10 Total Expected Marginal Revenue Curve . . . . ............ 122 4.11 Prorated Expected Marginal Revenue Curve for Itinerary BC . . . . 124 4.12 Total Prorated Expected Marginal Revenue Curve for Itinerary AC . 125 5.1 Multiple Leg Network . . . . . . . . . . . . . . . . . . . . . . . . . . 131 5.2 Small Hub-and-Spoke Network . . . . . . . . . . . . . . . . . . . . . 132 5.3 Time Line of the Booking Process . . . . . . . . . . . . . . . . . . . 133 5.4 Integrated Optimization/Booking Process Simulation . . . . . . . . . 136 5.5 Normal Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 5.6 Gamma Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 5.7 Truncated Normal Distribution . . . . . . . . . . . . . . . . . . . . . 144 5.8 Poisson Distribution . . . . .... . . . . . . . . . .. .. .. .. .. .. 145 5.9 Integrated Multi-Period Booking Profile . . . . . . . . . . . . . . . . 150 6.1 Multi-Leg Flight 31 . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 157 6.2 M ulti-Leg Flight 32.... . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 6.3 M ulti-Leg Flight 2[ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 6.4 M ulti-Leg Flight 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 6.5 Revenue Comparison between EMSR and OBL . . . . . . . . . . . . . . . . 162 6.6 Partitioned Network Methods for Flight 21 . . . . . . . . . . . . . . . . . . 163 6.7 Partitioned Network Methods for Flight 32 . . . . . . . . . . . . . . . . . . 165 6.8 Network Methods Nested by Fare Class for Flight 31 . . . . . . . . . . . . . 167 6.9 Network Methods Nested by Fares for Flight 31 . . . . . . . . . . . . . . . . 168 6.10 Network Methods Nested by Shadow Prices for Flight 31 . . . . . . . . . . . 169 6.11 Nested Deterministic Methods for Flight 32 . . . . . . . . . . . . . . . . . . 171 6.12 Nested Probabilistic Methods for Flight 32 . . . . . . . . . . . . . . . . . . 172 6.13 Network Methods Nested by Shadow Prices for Flight 21 . . . . . . . . . . . 176 6.14 Comparison of Seat Protections for Two Fare Class Example . . . . . . . . 177 6.15 Deterministic Bid Price Approach for Flight 31 . . . . . . . . . . . . . . . . 180 6.16 Probabilistic Bid Price Approach for Flight 31 . . . . . . . . . . . . . . . . 182 6.17 Network Bid Price and Nested by Shadow Price Approaches for Flight 21 . 183 6.18 Example of a Deterministic Bid Price Versus a Probabilistic Bid Price . . . 185 6.19 Network Bid Price Values for Leg B-C of Flight 21 . . . . . . . . . . . . . . 187 6.20 Network Bid Price Values for Leg A-B of Flight 31 . . . . . . . . . . . . . . 188 6.21 Network Bid Price Values for Leg B-C of Flight 31 . . . . . . . . . . . . . . 189 6.22 Network Bid Price Values for Leg C-D of Flight 32 . . . . . . . . . . . . . . 190 6.23 Deterministic Network Revenue Impacts as a Function of Revisions . . . . . 194 6.24 Prorated Leg-Based. Bid Price Approach for Flight 31 . . . . . . . . . . . . 198 6.25 Prorated Leg-Based. Bid Price Approach for Flight 32 . . . . . . . . . . . . 199 6.26 Network and Leg-Based Bid Price Approaches for Flight 32 . . . . . . . . . 200 6.27 Example of a Distinct Versus Nested Bid Price . . . . . . . . . . . . . . . . 202 6.28 Bid Price Values for Leg A-B of Flight 32 . . . . . . . . . . . . . . . . . . . 203 6.29 Bid Price Values for Leg B-C of Flight 32 . . . . . . . . . . . . . . . . . . . 204 6.30 Bid Price Values for Leg C-D of Flight 32 . . . . . . . . . . . . . . . . . . . 205 6.31 Prorated Leg-Based Bid Price/Booking Limit Approach for Flight 31 . . . . 207 6.32 Prorated Virtual Nesting on the "Value Net of Opportunity Cost" Approach for Flight 31 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 6.33 Prorated Nested Leg-Based Itinerary Limit Approach for Flight 31 . . . . . 210 6.34 Prorated Leg-Based OD Control Methodologies for Flight 32 . . . . . . . . 211 6.35 Prorated Leg-Based Methodologies for OD Control on Flight 41 . . . . . . . 212 6.36 Summary Comparison of the Revenue Impacts for Flight 31 . . . . . . . . . 215 6.37 Summary Comparison of the Revenue Impacts for Flight 32 . . . . . . . . . 216 6.38 Summary Comparison of the Revenue Impacts for Flight 21 . . . . . . . . . 217 6.39 Summary Comparison of the Revenue Impacts for Flight 41 . . . . . . . . . 218 6.40 Summary Comparison of the Revenue Impacts for a Two Leg Flight . . . . 221 6.41 Two Leg Flight . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 6.42 Leg-Based OD Control Methodologies for the Two Leg Flight . . . . . . . . 223 6.43 Network Approaches for the Two Leg Flight . . . . . . . . . . . . . . . . . . 224 6.44 Hub-and-Spoke Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 6.45 Deterministic Network Approaches for the Hub Network . . . . . . . . . . . 227 6.46 Aggregated Network Approaches for the Hub Network . . . . . . . . . . . . 230 6.47 Aggregated Nested Deterministic by Shadow Prices Approaches . . . . . . . 232 6.48 Leg-Based OD Control Approaches for the Hub Network . . . . . . . . . . . 235 6.49 ACY Booking Limit versus Y Class Protection . . . . . . . . . . . . . . . . 238 6.50 ACM Booking Limit versus M Class Protection . . . . . . . . . . . . . . . . 240 6.51 Summary Comparison of the Revenue Impacts for the Hub Network . . . . 242 6.52 Summary of Revenue Potentials . . . . . . . . . . . . . . . . . . . . . . . . . 246 A.1 Distributional Assumption Comparison for the NDSP Approach . .5.... 258 A.2 Distributional Assumption Comparison for the DBID Approach . . . . . . . 259 A.3 Distributional Assumption Comparison for the LBID/BL Approach . . . . 260 A.4 Distributional Assumption Comparison for the VNOC Approach ..-. .. . 261 A.5 Distributional Assumption Comparison for the NLBIL Approach . . . . . . 262 A.6 Comparison Between a Poisson, a Normal, and a Gamma Distribution . . 263 A.7 Network Methods Under the Modified Simulation . . . . . . . . . . . . . . . 264 A.8 Network Methods Under the Original Simulation . . . . . . . . . . . . . . . 265 A.9 Leg-Based OD Control Methods Under the Modified Simulation . . . . . . . 266 A.10 Leg-Based OD Control Methods Under the Original Simulation . . . . . . . 267