History of OR/MS at American Airlines: Revenue Management, Crew Planning, Capacity Planning, and Aircraft Maintenance
American Airlines (AA) was a significant player in the early implementation of operations research in the airline industry. AA initiated OR-based advances in solving a wide variety of airline-specific problems, including revenue management, reservation overbooking, aircraft maintenance, and crew scheduling. When revenue management approaches were first introduced in airlines, the approach had the more obscure name of “yield management.” AA researchers were active in the initial international OR community, sharing their advancements with the larger industry. Systems developed in the 1950s and 1960s became cornerstones of the airline business and launched solutions still in use today.
Consumer demand for air travel skyrocketed after the Second World War. The world was becoming increasingly smaller and the economic boom encouraged an increase in long distance travel. In 1953, the president of American Airlines, C. R. Smith, and R. Blair Smith, a senior sales representative for IBM, met on a cross-country flight from Los Angeles to New York. The two discussed the rapid growth of the airline industry, sparking an idea for a data processing system that could create and manage seat reservations. Over the next five years, American and IBM studied the feasibility of such a system. IBM adapted the Semi-Automatic Ground Environment (SAGE) air-defense project from MIT and developed an automated “passenger name record” or “PNR.” American called this new system the Semi-Automated Business Research Environment (Sabre). Sabre comprised two IBM 7090 mainframe computers in Briarcliff Manor, NY, connected to 1500 terminals across the United States and Canada (Sabre 2015). Sabre Corporation was established as a subsidiary of the airline in 1960. Two years later, AA’s Marvin Rothstein presented a paper on the Sabre concept and how operational research methods were used to “determine the equipment requirements and dimensions of the system” (Operational Research Society 1962b). Active participation in the international community was a way to both share their solutions and gain the other airlines as customers.
At a 1960 meeting of the International Federation of Operational Research Societies (IFORS), several delegates discussed the formation of an airline-focused professional organization. The following year, American Airline’s R. A. Engle took charge of arranging the first ever symposium of the resulting Airline Group of IFORS (AGIFORS) in Spring Valley, New York. Mr. J. Sowers of AA served as the group’s initial Information Officer and four AA employees gave talks on their recent findings (Operational Research Society 1962a):
- R.A. Engle and T. K. Krauze presented a paper on the Sabre seat-sharing problem, which concerned a number of sales agents, each confronted with a queue of customers. Their project determined whether sales agents must have one input device each or can share them without causing over queueing.
- Murray Spitzer presented on the arrangement of airline crew schedules so that the cost of aircrews and stopovers is minimized. To solve the problem, Spitzer developed a new technique called ALGO VII.
- And T.E. Moore presented on methods and reliability analysis in airlines maintenance. He developed an economic model and used the renewal equation to explore the average age of repairs and failures, time removal rates, and premature removal rates.
Since that original meeting, AA has remained an active participant of the AGIFORS community. Three Fellows of AGIFORS are former employees of AA: Thomas Cook, Scott Nason, and Armando Silva. Cook also served as president of AGIFORS, The Institute for Management Science (TIMS) and INFORMS.
In 1982, when Thomas Cook joined the OR group at AA, as Director, the group had 13 people, including several programmers working on building model-based systems in applications such as crew planning and revenue management. Over the next five years, under Cook’s leadership, the group convinced the CEO of AA, Robert L. Crandall of its value to AA and the group expanded to about 75 people. One of the regular Friday visitors at AA during this period was Ellis L. Johnson of IBM. His expertise in integer programming helped AA develop some of its early crew scheduling models. Crandall became a “champion” of the OR group and it transformed itself into American Airlines Decision Technologies (AADT) and it expanded further to about 700 people by 1992. At this time, it also started serving outside clients. Some of its early clients were Qantas Airways, Amtrak, and SNCF (the French rail system). AADT started to introduce its revenue management technology into the hotel, rental car, and sea cruise industries. The work for SNCF, the TGV system in particular, led to winning the Edelman award in 1997. By the late 1990’s the group had expanded further and changed its name to Sabre Technology Solutions. By the time Cook retired in 1999 the group had thousands of people and had hundreds of clients worldwide.
A key dilemma in airline reservations has been finding the balance between over and under-booking flights. This was initially of concern in the 1960s as the rapidly increasing number of passengers and stops became difficult to manage. M.J. Beckman was the first to publish a model for this problem in the late 1950s, minimizing lost revenue due to empty seats and the costs of overbooking (Beckman 1958). The treatments to the problem grew progressively more elaborate, constraining the proportion of overbooking. When Marvin Rothstein joined American as manager of systems analysis in 1960, he identified a discrepancy between some executives who claimed the airline “did not engage in the practice [of deliberate overbooking] at all” and others who recognized it as an industry-wide procedure “everywhere in the system.” By the time Rothstein became the director of all operations research at AA, he collected evidence proving the latter was true (Rothstein 1985). Passenger booking levels were addressed at numerous AGIFORS conferences in the 1960s, as exemplified in papers by Taylor in 1962 and Deetman in 1964. Rothstein and Stone presented the American Airlines implementation of their modified solution at the Seventh AGIFORS Symposium in New York, maximizing passenger revenue (Rothstein & Stone 1967). A slight downside to these public discussions was increased customer awareness of the overbooking practice, one which Rothstein said put passengers “supposedly on notice,” but questioned whether they really understood what was taking place (Rothstein 1985).
As other industry trends were being addressed, American’s yield management strategy was championed in the late 1970s and early 1980s. The airline “launched the revenue management revolution”, employing an approach built upon the fundamental premise that “inventory was perishable, and all customers were not created equal”. They considered airline seats a “perishable resource” and anticipated passenger behavior in order to compete with the low-cost carriers (Spiewak 2017). In an introduction to a special airline edition of Interfaces, American’s Thomas Cook highlighted this strategy, stating “an effective yield management system can generate incremental revenues of five to seven percent (Cook 1989).” Smith, Leimkuhler, and Darrow were awarded the 1991 Franz Edelman Award for American Airlines’ research and implementation of their yield management strategy.
Though Sabre Corporation played an important role in executing OR/MS solutions in the industry, the airline put their efforts in multiple areas. One such example is the American Airlines Decision Technologies (AADT) group, which was established in the 1980s. Armando Silva, took a leading role in applying operations research to customer loyalty, pricing, sales, and revenue management. He eventually became a Managing Director of OR at AA, a position held until his retirement in 2012 (Foster 2017). The planning of an itinerary for a crew by systematic methods came to be called “crew pairing.” The reason was that the time away from home for a crew usually meant the pairing of an outbound sequences of flights with an inbound sequence of flights, with an overnight in between. Crew pairing optimization became a key area for AADT in the late 1980s. Anbil et al. identified crew pairing optimization as “an enormously complex combinatorial problem” because the set of possible pairings is enormous. AA developed the trip reevaluation and improvement program (TRIP), based on an approach in which crew pairings are iteratively improved by generating and solving a series of subproblems. Subsequent enhancements to TRIP, including algorithmic improvements and effective data processing, resulted in savings of over $20 million annually (Anbil et al. 1991).
Around the same time AA researchers worked on the crew optimization problem, others were developing the arrival slot allocation system (ASAS). In the late 1980s/early 1990s, American had the largest fleet of aircraft in the western world, operating out of seven major hubs. In 1988, systems operations control “expressed its need for an automated arrival slot allocation system”, which AADT agreed to develop in a microcomputer environment. The goal in developing ASAS was creating a system that could: (1) efficiently allocate arrival slots, (2) automate the calculation of delay, (3) give flight dispatchers more time to perform other duties by speeding up the resulting turn out process, and (4) be user-friendly and flexible enough to allow dispatchers to easily alter solutions. The initial implementation of the system at San Francisco International Airport increased arrival dependability from 40 to 84 percent. Airline management estimated this growth in dependability and subsequent customer satisfaction generated an extra $17 million in revenue (Vasquez-Marquez 1991). The papers on crew-pairing optimization and ASAS were both finalists for the 1990 Franz Edelman Award. The following year, American Airlines was awarded the INFORMS prize in recognition of organizational dedication to applied principals of OR/MS in novel and lasting ways.
The American Airlines OR/MS legacy continued into the 21st Century, even though the Sabre Corporation was spun off as an independent entity in 2000. Thomas Cook, who played a major role in growing the company’s relatively small OR group into a major division, was one of eight individuals to receive the 2016 INFORMS Impact Prize for career contributions to revenue management. AA remains an active participant in professional societies and the larger research community dedicated to operational air travel problems.
Compiled by: Reed Devany
Edited by: Linus Schrage
Links and References
Anbil, R., Gelman E., Patty, B., & R. Tanga (1991) Recent advances in crew-pairing optimization at American Airlines, Interfaces 21(1): 62–74.
Beckmann, M. J. (1958) Decision and Team Problems in Airline Reservations. Econometrica 26: 134-145.
Cook, T. (1989) Introduction to Special Section: Airline Operations Research, Interfaces 19(4): 1-2.
Deetman, C. (1964) Booking Levels. in Proceedings of the Fourth AGIFORS Symposium. American Airlines, New York.
Foster, D. (2017, April 25) Armando Silva. AGIFORS: News. https://agifors.org/news/4778488
INFORMS (2016) Award Recipients: Thomas M. Cook. Web Article. INFORMS. https://www.informs.org/Recognizing-Excellence/Award-Recipients/Thomas-M.-Cook
Kosten, L. (1960) Een mathematisch model voor een reserveringsprobleem. Statist. Neerland. 14: 85-94.
Operational Research Society (1962a) News and Notes. OR 13(1): 119-131.
Operational Research Society (1962b) News and Notes. OR 14(2), 229-244.
Rothstein, M., & A. W. Stone (1967) Passenger Booking Levels. in Proceedings of the Seventh AGIFORS Symposium. American Airlines, New York.
Rothstein, M. (1985) OR and the Airline Overbooking Problem. Operations Research, 33(2): 237-248.
Richter, H. (1989) Thirty Years of Airline Operations Research. Interfaces, 19(4): 3-9.
Sabre (2015) The Sabre Story. Online Presentation. Sabre. https://www.sabre.com/files/Sabre-History.pdf
Smith, B. C., Leimkuhler, J. F., & Darrow R. M (1992) Yield Management at American Airlines. Interfaces, 22(1): 8-31.
Spiewak S. (2017) The evolution of airline revenue management: Defining the next generation approach. Web Article. Sabre. https://www.sabre.com/insights/the-evolution-of-airline-revenue-management-defining-the-next-generation-approach/
Taylor, C. J. (1962) The Determination of Passenger Booking Levels. in Proceedings of the Second AGIFORS Symposium. American Airlines, New York.
Thompson, H. R. (1961) Statistical Problems in Airline Reservation Control. Operational Research Quarterly. 12: 167-185.
Vasquez-Marquez, A. (1991) American Airlines Arrival Slot Allocation System (ASAS). Interfaces 21(1): 42–61.
Vickrey, W. (1955) Some Implications of Marginal Cost Pricing for Public Utilities. in The 67th Annual Meeting of the American Economic Association, Detroit, MI.