Constraint Technologies International provides planning and decision support systems to industry. In particular, we are very active in the airline industry. Running a large airline requires the ability to solve large and challenging optimisation problems. One of the greatest challenges arises from the tension between the need for powerful numerical optimisation on the one hand, and the requirement to take into account a complicated and changing set of business rules on the other hand. Another major challenge is the problem of real-time disruption management, which requires a high degree of integration between problems that would normally be dealt with in a disjoint fashion.

We begin by describing some of the classic problems and challenges faced by airlines, such as crew scheduling and rostering, and some standard ways of solving these problems. We then go on to discuss particulars of CTI's approach to these problems; some of the practical challenges that we have been faced with and our response to these challenges; and our strategies for achieving flexibility without adversely affecting performance.

We finish by discussing some of the hardest (and indeed only partially solved) challenges of airline decision support: the increasing need for effective disruption management tools, and more generally the desirability of achieving greater integration between the various stages of planning and operations.

It can be helpful to think of the operation of an airline in terms of three distinct time frames.

At the top level, an airline should be doing some kind of strategic planning. This involves making strategic decisions, anywhere from several months to years before they are due to come into effect. Due to the lack of exact information, there is a limited role for optimisation. However, optimisation can play an important role in scenario planning, where the effects of hypothetical scenarios are explored.

It is also necessary for airlines to do a great deal of ongoing, day to day planning. Plans are usually developed several weeks or months before they are due to come into effect. They comprise things like flight schedules, crew schedules, resource allocation plans and so on. This process could be termed "operational planning". Operational planning is a fertile area for mathematical optimisation: there is usually enough information available to be able to develop reasonable mathematical models, and the time frame is long enough to be able to permit optimised plans to be produced and implemented.

Airlines also need to be able to keep track of events as they unfold. This area is usually called "operations". As regards decision support software, there tends to be an emphasis on situational awareness and data flow. However, there is a role for optimisation when things fall over. Due to the tight time frames (usually minutes), the often limited information available, and the requirement to efficiently interface with operations systems, this is an extremely challenging area for optimisation.

Our main example of an airline optimisation problem will be the crew scheduling problem. This is a relatively hard problem that throws up challenges common to several airline optimisation problems.

At the start of the aircraft planning cycle, an aircraft schedule is formulated. This is basically a list of flights, along with the associated departure and arrival times and other relevant information. The aircraft schedule is then passed to the crew planning section, whose job it is to decide how to crew it efficiently.

The crewing problem is usually broken into two subproblems - the crew scheduling problem, and the crew rostering problem.

The crew scheduling problem is to partition the flights in the aircraft schedule into a series of round trips, or pairings. Each pairing represents a chunk of work for a crew member that lasts anywhere from a day to more than two weeks.

Once the crew scheduling problem is solved, the rostering problem then assigns individual crew members to the pairings in an efficient manner.

The nature of the crew scheduling problem changes depending on whether we are looking at pilots or cabin crew, whether the problem is for short-haul or long-haul flights, and so on.

Here is an example of a pairing. It consists of four flights, forming a round trip from Sydney to Auckland via Brisbane. There is break of more than 24 hours in Auckland, during which time the crew member is basically free to do whatever they want.

This pairing has an associated cost. Firstly, the crew member needs to be paid. There is usually even some component of pay for off-duty time. Secondly, two nights in a hotel in Auckland must be paid for. There are also other costs, such as taxis to and from the airports. Certain pairings are more or less efficient with regards to cost. For example, this one might not be very good, because there are two nights and a whole day during which the crew member doesn't work, and must be put up in a hotel.

There are also rules that must be obeyed by the pairings. These rules specify things like the maximum time able to be worked in a day, minimum levels of rest and so on. These rules can be specified by regulatory aviation bodies as well as by clauses in the crews' work contracts.

The crew scheduling problem is then to find the least costly way to partition all of the legs in the aircraft schedule into legal pairings. (Actually this is a simplification: we often need to deal with variable numbers of crew members on each plane leg, and so on).

It is easy to imagine that building all of the complicated cost and legality rules that need to be satisfied by the pairings into a mathematical algorithm would be a recipe for trouble. So how do we manage to apply heavy-duty optimisation to the problem while ensuring that the rules are taken account of?

The answer is to formulate the problem in a manner that decouples the rules from the problem of finding the most efficient schedule. This is done by enumerating all possible legal pairings, and then applying an algorithm that chooses a subset of these that forms an optimal crew schedule.

This problem can be framed as a standard operations research problem - either the set covering problem, or the set partitioning problem.

For realistic sized aircraft schedules, we run into issues with size: there are simply too many possible legal pairings to enumerate, let alone solve. A classic, but not necessarily good, solution is to work with an initial set of pairings that is only a small subset of all possible pairings.

Here is the mathematical statement of the set covering problem. It says: minimise the total cost of all pairings in the solution (that is, all values of xi with a value of 1), with the constraint that each leg must occur in at least one pairing in the solution.

Here is a trivial example of the set covering problem. There are four legs, forming a round trip from Sydney to Melbourne to Adelaide and back again. We assume that both Sydney and Melbourne are crew bases, so that pairings can start at both of these cities. It is then possible to form three pairings:

(SYD-MEL, MEL-SYD)

(SYD-MEL, MEL-ADL, ADL-MEL, MEL-SYD)

(MEL-ADL, ADL-MEL)

The task is to select a subset of these pairings so that every leg appears in at least one pairing.

One solution is to select the first and third pairings, with a total cost of 4. A better solution is obviously to select only the third pairing, with a total cost of 3.

In reality, things are always more nasty than the previous example. Typically, we have hundreds, thousands, or tens of thousands of plane legs. The number of possible pairings is astronomical for most realistic aircraft schedules; certainly too many to be explicitly enumerated.

We can simply ignore most of the pairings, working with a severely reduced subset. This is a classic approach that can lead to bad solutions. Usually we want to do something cleverer.

The two most popular techniques available to deal with huge problems are (1) column generation and (2) subproblem optimisation. The first of these techniques works with a limited subset of all possible pairings at any given time, the second works with a limited subset of all legs.

The simplest technique for dealing with the exponential blow-out in problem size could be referred to as subproblem optimisation. It has been used in airline crew scheduling since the 1970s. It is still a very effective technique.

We start with a feasible schedule that we want to improve. We select a subset of the pairings in this schedule. This subset defines a "mini aircraft schedule", consisting of all flights in the selected pairings. This mini schedule is then optimised, usually using the classic technique of generating all possible pairings and then solving an integer program. The process is repeated iteratively.

The solution will converge to something that may or may not be the optimal solution, because there is always the possibility of getting "stuck" at a local minimum.

There is some subtlety required in applying the algorithm, for example to avoid re-optimising combinations of pairings that we know will not lead to improvement.

A somewhat more involved means of dealing with larger problems is column generation. Column generation has been applied to airline crew scheduling for close to 20 years now.

The algorithm starts by first finding a solution to the LP relaxation of the problem, using a restricted subset of all possible pairings. Dual information from this solution is then used to devise a subsidiary problem, the column generation subproblem, whose solution gives extra pairings that are guaranteed to improve the current optimal solution when added to the current list of pairings. The process is repeated iteratively.

We need some way to guarantee that the solution found has integer values of x, since, as described here, this will not necessarily be the case. Techniques such as branch and price can be applied. This is quite involved and has been the subject of a great deal of research.

Solving the column generation subproblem can be done by means of constrained shortest path algorithms, using dynamic programming. Again, its solution is quite involved, and it has been the subject of a great deal of research.

We will move away from looking at crew scheduling in order to look at some of the systems issues that arise in applying optimisation to real world airlines.

We can identify four main challenges:

(1) A need for flexibility in defining data, and the relationships between data, needs to be coupled with the (sometimes opposing) need to apply very efficient mathematical optimisation techniques. A good example is the costing and legality rules discussed in the context of the crew scheduling problem. In order to handle these kinds of issues, Constraint Technologies International has developed the "Common Rules" rule management system.

(2) We need to be able to handle the "fuzzy" human factors - crews getting jetlagged, people becoming sick and so on. It is difficult to incorporate these kinds of situations into an often rigid IT framework.

(3) We need to be able to deal with uncertainty. From the point of view of planning (crew scheduling and the like) this means being able to build robust plans. With regard to operations, this means we need to be able to field systems that enable informed decisions to be made and implemented on the run.

(4) We need to be able to gather and manipulate data from a variety of sources including legacy systems. This is the perennial challenge inherent in fielding complex IT systems in many industries.

In dealing with these challenges, we also need to keep in mind that we are often required to apply mathematically efficient algorithms, a requirement that often runs counter to the requirements discussed above.

This image shows a view from the CTI "Common Rules" editor. In the current example, the data flow for a rule determining the maximum time that a staff member is allowed to work is shown.

The system can be used to evaluate both cost and legality.

Rules systems like this provide a higher degree of flexibility to optimisation software, because the rules are highly transparent and configurable. The system has also been developed so that the rules are evaluated in an efficient manner, in order that algorithms are not unduly slowed down.

Finally, using a modular rules system like this enables better communication between various programs, hence the name "Common Rules".

The above image shows a graphical display from the CTI crew scheduling system. Two weeks worth of flying between London, Bangkok and Sydney is shown.

Although we have concentrated on the crew scheduling problem, there are several other problems that arise in airline planning and operations to which optimisation can be applied. Some examples are listed above.

This screen snapshot shows a Gantt chart from a CTI rostering system.

So far, we have discussed airline optimisation problems as if each problem exists in isolation from the others. In the real world, of course, we cannot make such neat divisions into problem domains. Basically, everything affects everything else.

A good example is airline crew scheduling and rostering. These are usually solved as two separate problems, for reasons relating both to the mathematical difficulty of solving the combined problem, and to the general systems issues that arise from the increased complexity of the combined problem.

Nonetheless, if we could deal with the combined problem, it might be possible to achieve greater efficiency. For example, certain classes of pairings turn out to be easier to roster. Normally, this is either not taken into account when solving the crew scheduling problem, or it is considered in a very crude manner.

It should also be possible to achieve greater efficiency by blurring the usual distinction between planning that occurs weeks or months ahead of time, and day to day operations.

CTI has been looking at issues such as these.

To finish, we will look at the very challenging problem of how to manage disruptions to normal airline operations.

We need to deal with a variety of related problems: canceling or re-routing aircraft, re-routing passengers or even putting them up in hotels, re-crewing the disrupted aircraft, dealing with gate constraints at airports, and even dealing with issues such as catering.

We need to deal with these issues on a very tight time frame, usually minutes. We also need to do so under conditions of incomplete or uncertain information.

Such problems will always require skilled operators, and good situational awareness and control systems.

It is also possible to apply optimisation. Due to the degree of uncertainty, it is probably preferable for an optimisation system to provide a number of reasonable solutions to be evaluated by human operators, rather than a single "best solution".

As such, optimisation for disruption management often has a somewhat different focus than optimisation for planning. Possibly there will always be a greater role for heuristics and "quick and dirty" solutions.

This screen snapshot shows a disruption management GUI that permits a range of possible solutions to be evaluated against each other based on a variety of criteria.