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.
A team composed of researchers from UF, the Massachusetts Institute of Technology and United created a mathematical model that is said to help 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 once it is fully implemented.
‘Mathematical modelling 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 realise 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 in the US, 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 minimising its cost of operation.
United’s fleet 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, called 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 said to be 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 realised 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 US National Science Foundation, Ahuja and James Orlin, a business school professor at MIT, developed a technique to solve such difficult problems quickly.
Known as ‘Very Large-Scale Neighbourhood Search,’ the technique starts with a feasible solution for a problem and repeatedly replaces it with an improved ‘neighbour’ solution. The NSF grant is said to have enabled the Ahuja-Orlin team to develop a method that allowed them to test trillions of neighbours 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 neighbourhood 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.
‘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.’