Algorithms for airlines: new math model saves money, improves service

March 4, 2002

GAINESVILLE, Fla. — A University of Florida-led research team has developed a new mathematical approach to airline scheduling that could lead to substantial savings for United Airlines, which helped sponsor the research, and eventually for other airlines as well.

A team composed of researchers from UF, the Massachusetts Institute of Technology and United created a mathematical model that helps the airline identify the most profitable assignment of planes to flight legs and determine through connections between flights. The model, which relies on complex algorithms, is predicted to save the airline as much as $25 million annually and improve customer satisfaction once it is fully implemented.

“Mathematical modeling is very powerful,” said Ravindra Ahuja, a UF professor of industrial and systems engineering and the lead researcher on the project. “Companies don’t often realize that mathematical models can result in substantial cost savings for them and pay back for the developmental cost in a couple of months, or even sooner.”

Each day, several hundred thousand passengers travel among hundreds of cities nationwide, with each city-to-city flight known as a “leg.” Airline fleets consist of different types of planes with varying seating capacities. The airlines’ job is to assign the right plane to each flight leg while simultaneously determining the daily route of each plane – and minimizing its cost of operation.

It’s a gigantic scheduling problem. United’s fleet, for instance, consists of more than 490 planes spanning nine different plane types from commuters to 747s. These planes usually fly an average of five flight legs per day or more than 1,700 daily flight legs.

The problem is too complex to be solved manually, so airlines use mathematical models that computers solve.

When assigning planes to flight legs, one model, known as the ”fleet assignment model,” matches the demand for each leg with the planes’ seating capacities. When planes and flight legs have been matched, the airlines then take pairs of consecutive flight legs (such as, Boston to Atlanta, and Atlanta to Austin) and make them “through” flights using the “through assignment model.” Through flights show up on the airline’s schedule (such as, Boston to Austin) as flights with one stopover. Passengers are willing to pay extra for these flights, because they don’t have to change planes, so airlines want to make as many of them available as possible.

United realized that by combining the two models, it could improve profitability. But the combined model was too difficult to be solved with the available technology.

In a research project sponsored through a $500,000 grant from the National Science Foundation, Ahuja and James Orlin, a business school professor at MIT, developed a novel technique to solve such difficult problems quickly. Known as “Very Large-Scale Neighborhood Search,” the technique starts with a feasible solution for a problem and repeatedly replaces it with an improved “neighbor” solution. The NSF grant enabled the Ahuja-Orlin team to develop a method that allowed them to test trillions of neighbors and determine the best solution in a fraction of a second on a typical personal computer.

United then asked the team to develop an application of the technique to solve its combined scheduling model. The software used the solution produced by United’s current software as the starting solution. It was improved by using the neighborhood search that takes less than five seconds to complete. The result increased the number of available through connections and predicted potential savings of some $25 million.

The research was sponsored by United’s Research and Development Department. Two doctoral students, Dushyant Sharma from MIT and Jian Liu from UF, also participated.

United is pleased with the experimental results and looks forward to implementing the technology.

“We are excited about this new technology,” said Raj Sivakumar, director of research and development at United. “It will be a key component of our overall strategy for flight scheduling to develop globally optimal solutions.”