Aircraft scheduling

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 Operational Research (OR) 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, OR 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.