We first entered the field of airline optimization about twenty years ago with a project on fleet assignment for Delta Airlines.

There is an amusing story about how this work for Delta began. At the time, Delta was using a new crew scheduling system that was based on the polynomial time linear programming algorithm developed by Narendra Karmarkar at AT&T Bell Labs and implemented in the KORBX optimization system, an eight processor Alliant computer. The system reputedly cost $8.9 million and, not surprisingly, only two such systems were ever sold. Delta bought one of them to solve crew scheduling. The important point to note is that crew scheduling is an integer programming problem, which is hard to solve, and KORBX could only solve linear problems, which are much easier relatively. So, the AT&T folks could only provide a heuristic for converting linear solutions to integer solutions.

We had some new ideas for solving crew scheduling problems; however, our attempts to contact Delta fell on deaf ears until Mike Thomas, then school chair, had a brilliant idea. Ron Allen, an ISyE graduate, class of 1964, had recently been appointed CEO of Delta. Thomas arranged a dinner at which Allen would be honored, and we would get a chance to suggest to him that we could help Delta with scheduling. The evening went well except for the end. Atlanta had just started car emission checks, and because of the low fee paid to the stations that could perform them, there were very long lines. A black market emerged for the emission stickers that were attached to license plates.

When we left the Alumni House at the end of the dinner, we discovered that each of the cars that previously held these stickers were missing the part of their license plate where the sticker had been. Allen's car was one of them. Nevertheless, from Allen we got an inroad to Delta's IT group. Because of their work with KORBX, they were not interested at the time in help with crew scheduling. But they decided to work with us on plane scheduling, which is called fleet assignment in the industry.

Given a schedule that lists the time, origin, and destination of all flights, fleet assignment addresses the question of what type of aircraft should be assigned to each flight. The answer is driven by demand and the network structure of all of the flights. Large planes should be assigned to high-demand legs. However, if a large plane is assigned to a flight from A to B, then there should be a flight from B that departs soon after the A-to-B flight that also has large demand and so on. The optimization model minimizes flying costs and the costs of lost demand. Cindy Barnhart, then an assistant professor in our group, now a professor and associate dean at MIT and a leading international expert in airline research, got her start on the Delta project. We successfully completed this project and then went on to do research sponsored by almost all of the major domestic carriers, including American, Northwest, United, and US Air, as well as the National Science Foundation.

By the mid-1990s, we began to tackle harder problems including systems optimization and uncertainty. Traditionally, fleet assignment was done before crew scheduling since crews are scheduled by aircraft type. However, an optimal solution for fleet assignment could lead to very costly crew schedules. For example, a crew might spend more than twenty-four hours simply waiting for the next airplane they could fly. We developed technology for optimizing fleet and crew assignments together.

Schedules were developed assuming no disruptions. But weather, equipment problems, and many other causes led to delays that propagated throughout the system. We developed some of the first technology for fast reoptimization or recovery of crew and fleet schedules when the current schedule was broken. We provided technology for producing robust schedules that make it easier to recover from these disruptions. To evaluate the quality of schedules in an uncertain environment, we developed SIMAIR, which allowed operations to be simulated for millions of days to evaluate the performance of different schedules.

Most of this work was done in collaboration with Sabre Decision Technologies, led by Barry Smith, and United Airlines, where Eric Gellman headed the operations research group. This work led to many publications, about ten dissertations, and some national awards to the students. Some of these students are now in operations research groups in the airline industry, and several others are faculty at other universities and continue to do good work on airline optimization.

Recently, our focus has shifted to on-demand air transportation, which involves unscheduled airlines where service is requested simply by origin***destination pairs and time windows. There are many ways of delivering this type of service including charter, fractional ownership, and air taxi. Professors Ellis Johnson and Ozlem Ergun have an ongoing project with Citation Shares to fulfill requests from individuals or companies that have fractional ownership rights to a fleet of planes. A business model that potentially can be widely used in place of standard airline transportation is an air taxi service. Anyone can request a seat on a plane by providing the earliest departure time from origin, latest arrival time at destination, and number of passengers. The planes can fly to and from very small airports. The cost can be made nearly competitive with commercial service. The convenience of such a service can be very appealing to business people, especially those who do not live close to a major airport. In many situations, it is an attractive alternative to car trips of several hours. Professors George Nemhauser and Martin Savelsbergh worked with DayJet, which at the time was the leading company providing this service using lightweight Eclipse jets. Unfortunately, the recent economic downturn has caused DayJet to terminate operations.

Air transportation networks have always been a fertile field for optimization applications and will continue to be so as we begin to work on new problems involving online optimization and optimization under uncertainty.