What can O.R. do for you?

Aircraft Scheduling

Airline captain

Whenever we jump aboard an aircraft bound for sunnier skies we're often so wrapped up in the excitement of going on holiday that we pay little attention to what's going on around us. We just assume, for example, that our plane is guaranteed a crew of pilots and cabin staff. But with almost two million flights in and out of the UK every year, how do airlines make sure that every one has its full complement of staff? The answer lies in an area of O.R. known as heuristics.

The airline industry is one of the most regulated work sectors in the world. There are a whole host of rules (constraints) governing the shift patterns of pilots and cabin crew. There is a maximum number of hours that staff can work in one shift, along with a minimum rest they must be allowed between shifts. There must also be the right mix of qualified staff on board and their own holidays must be accounted for. Rostering aircrew to navigate these constraints would be a Herculean task without a little help from mathematics. Computers might be able to chug through all the different possibilities to find the absolute best solution, but the kind of computing power required is prohibitively expensive. Instead, O.R. techniques can be used to take a clever shortcut.

One way to do it is to use a two stage set partitioning function. As the name suggests this breaks the problem down into two more manageable sets and searches for the optimal solutions at each stage. The first stage is to minimise the overall number of air crew needed to cover the flight schedule. In maths this can be done by using a graph. This graph is made of nodes connected by edges. In this example the airports are the nodes and edges are the flight routes of the air crew. In practice this work involves very large numbers of nodes and edges. In the example below the airline wants its crew to begin and end at Heathrow Airport whilst crewing flights between other hub cities in the meantime. Heuristic algorithms can be run to find the graphs with the minimum number of edges connecting all the nodes in such a way that every aircraft has its required staff. More edges means more staff and a harder job to find the right combinations of people to cover the jobs. It also means greater associated costs for the airline. In long haul scenarios, they might even have to pay to put their staff up in hotels whilst they wait to work the next connecting flight.

Aircraft scheduling example graph

Now it could be that the absolute optimum configuration cannot be achieved because of the constraints on working hours and breaks. So in practice the top few configurations are found and then things are juggled around to try and assign actual people to those roles. This is the second stage of the process. It is done using a version of trial and error. A sensible guess is applied to try and assign crew to the desired routes. Another assignment is then made and, if that works better, the old one is disregarded. If it is worse then the process tries to fit more and more scenarios until a better one is found. The process is equivalent to trying to find your way through a maze whilst blindfolded. If you take a step forward and you bump into a wall then you return to where you were and try a step to your right instead. If that works then you try another step to your right. If you again encounter a wall you go back and try a step forward.

This O.R. technique is not guaranteed to find the absolute best answer to the problem, but it allows those in charge of aircraft scheduling to get pretty close to the answer, saving them both time and money and ensuring you have a fully staffed aeroplane to take you on your way.

Similar complex rostering problems are faced by bus and train companies.

Banner Watch our 'What is O.R. movie' Download our Guide to O.R.