To kick off the blog posts I have decided to go back to my roots in optimisation. Air transportation was the topic of my PhD. So I have built up a lot of knowledge about the uses of optimisation within airlines.
Many of us have used an airline at least once. There are people who are constantly taking flights as part of their work. However, it is more enjoyable taking flights when heading off on a vacation. Our ability to regularly use airlines for work and leisure is directly related to the wide use of optimisation. Through the use of optimisation, airlines have managed to reduce costs and increase offerings to provide the service that we now enjoy.
A key part of the airline business that I am particularly interested in is the optimisation of aircraft routing. A route is the sequence of flights that an aircraft will perform over a day/week/month (the time scale is up to the airline or the researcher looking at the problem). An airline uses an optimisation problem, called the aircraft routing problem, to determine the set of routes that will be performed by all aircraft.
Aircraft routing
The most important aspect of aircraft routing can be given in one word: maintenance. Since sending metal tubes with wings through the sky can be a dangerous activity, regulatory bodies specify what maintenance checks need to be performed by an airline and when. These can range from a visual inspection of the aircraft through to a complete strip down and rebuild. One thing to keep in mind here is that every maintenance check requires an aircraft to be unavailable for a period of time (the duration depends on the type of check).
An airline will use optimisation for two reasons:
- there are not an infinite number of aircraft, and
- aircraft only make money while they are in the sky.
So, an airline will want to use an aircraft as much as possible between each maintenance check. The greater the frequency of maintenance checks, the more often the aircraft will be out of operation, leading to a decrease in revenue for the airline. Now, if there were an infinite number of aircraft, then having aircraft out of operation will not cause any problems at all. This problem is about the efficient use of a scarce resource.
The constraints
In my field of optimisation, every problem needs to have restrictions, which are called constraints. Some of the constraints have been explained in the previous sections, but I will go through more of them here.
- Every flight must be assigned to an aircraft
- An aircraft can only have two flights in a sequence (flight1, flight2) if the destination of flight1 is the origin of flight2; and flight1 arrives before flight2 is due to depart.
- Now this could sound obvious, but from a mathematical point of view each flight is just an entity with an origin, destination, departure and arrival times. So we need to explicitly state what flights can follow another flight. You may see me describe this a flow balance; however, this definition is not too important.
- Each aircraft must enter a maintenance station after certain criteria, calculated from the last maintenance check, is met
- The criteria can be: total flight time, number of days, number of take-offs/landings, …
There are other constraints that can be included for the practical implementation of this problem. These can include details about the fuel efficiency of the aircraft, the capacity of the aircraft, and the length of the routes away from hub airports.
How is this used?
The planning stage for an airline can start around 6 months before the day of operations. That means, the flight you take for a Christmas holiday was thought about by the airline at around June, or even earlier. During the planning process, the aircraft routing is an important part because it influences crew planning decisions. An airline will determine a set of aircraft routes by solving an optimisation problem that is defined by the constraints stated above. These routes are then used as part of the crew planning problem (something for a future blog).
Benefits from optimisation
Modern airlines are large organisation that manage many different resources. The ability to manage the allocation of aircraft to flights in the way that achieves the most efficient usage is very difficult for a human to do. So the use of optimisation increases the utilisation of aircraft, which leads to a decrease in operating costs.