Presented at the AGIFORS 45th Annual Symposium on 29th September 2005
By Alan Dormer
Constraint Technologies International
CTI has been working in the transportation and logistics industry for over 10 years building and developing operations control and crewing solutions.
A recent addition to this portfolio is Recovery Optimisation, which is the process of recovering from schedule disruptions. This technology has been applied to airline operations.
There are a number of issues that arise from solving this problem. These include:
-
Solving the operations and crewing problem simultaneously
-
How to improve decision making rather than taking the decision away from the user
-
Dealing with external issues that the system may not (or cannot) be aware of
The paper will discuss these and how they relate to a practical solution of the problem
Disruptions to plans and schedules are inevitable and can be expensive. The requirements from airlines to manage disruptions are demanding and multi-faceted.
On the face of it the requirements are quite simple:
-
Find the 'best' solution
-
Make as few changes as possible
-
Get back on schedule as quickly as possible.
On further reflection, this is a lot more complicated
-
It's often not clear what 'best' is, and this can change from day-to-day
-
External dependencies or problems may rule out or modify potential solutions
-
Finding a solution to a problem caused change, yet making few changes, are essentially conflicting requirements
In order to solve these problems, CTI have developed a methodology that:
-
Quickly finds a range of good/acceptable solutions
-
Helps the user determine which solution is best on the day and allows them to use their wider knowledge of the situation
-
Makes as few changes as possible and returns to schedule quickly
On day of operations events occur that disrupt scheduled operations. Recovery Optimisation is a process that identifies potential solutions in real-time to minimise overall impact. By overall impact we mean passenger delays, schedule changes, crew, aircraft and other costs.
Recovery Optimisation is essentially a decision support activity that enables operations controllers to take a holistic view and make rational, consistent and accountable decisions in the full knowledge of the wider implications.
On the day of operations, airlines are interested in solving problems caused by unplanned events. These include:
-
Weather (delaying or preventing take-off or landing)
-
Port closure
-
Congestion on the ground
-
Congestion in the air
-
Equipment unserviceable
-
Crew unavailable
Each one of these - and there may be more than one at a time - prevents the schedule being flown as planned, and has a problem on one sector has a knock on effect, through patterns and passenger connections, on many other sectors.
The irony is that the tighter the schedule, in terms of resource and manpower utilization, the greater the effect of any disruption.
Airlines want to make timely corrections that:
-
Reduce the potential negative impact for passengers
-
Limit the cost - if any - of additional resources
-
Reduce the impact on related functions, such as maintenance, ground staff, etc
-
Return the operation to schedule as soon as possible
It is worth examining some of these to understand what we mean:
Reduce potential negative impact for passengers
There is certainly a real cost associated with delaying passengers, over and above compensation, meals or accommodation. But this is not easy to quantify. Every passenger is different. For some, a one hour delay may mean that they avoid an airline for the rest of their life if possible. For another the threshold may be 24 hours. Others may not care, or have no choice.
Therefore it is true to say that, although we want to minimize the cost of passenger delays, we cannot determine with real any accuracy what they are.
Reduce the impact on related functions
There are in fact two issues here:
-
Any change is undesirable. It requires communication, management time, and is prone to errors. There are many examples in military history of orders being changed before an engagement with disastrous consequences.
-
Changes which result in problems for other functions have costs which may be considerable but not easy to quantify. Aircraft out-of-place or gate changes, for example.
Returns the operation to schedule as soon as possible
This is not just an extension to item 3. Passengers expect to leave and arrive on the published schedule. The longer the schedule departs from that, the longer this negative impact remains.
It is tempting to look at this problem as one of mathematical optimisation. This is not unreasonable as all the ingredients are there. We have:
-
Costs (objective function)
-
Limits and definite does and don'ts (hard constraints)
-
Avoid or minimise (soft constraints)
But in this case, we don't believe that mathematical optimisation, per se, is the best technique.
There are a number of reasons:
-
Soft constraints require penalties. These are not easy to set. For example, if we do not know the cost of a passenger delay how can we trade that off against the cost of additional resources to reduce it?
-
Any system necessarily optimises with a subset of the real world and incomplete data. An optimal solution may not be feasible for any number of reasons.
-
We need to consider operations and crew, but this optimisation problem is very large and can take a long, indeterminate time to solve.
-
Airlines don't want a new schedule; they want their old one back! It is a matter of fact that small changes to the input parameters of an optimisation problem can cause (many and large) changes to the answer.
However when we talk about Recovery Optimisation, we mean optimising the process of recovery. What we want to provide is decision support.
There are a number of reasons for this:
-
Operations staff can generally get an acceptable solution, given enough time. We don't want to take them out of the loop altogether, we want to provide help
-
If we want to produce 'the optimum' it implies the system knows about everything - which it cannot. There will always be factors unbeknown to any system, but which operations controllers are aware of
-
We believe it is far better for a computer to produce a range of good solutions, with hard costs and other implications, that the operations staff can assess and analyse quickly and decide on the best one.
So the driving force for CTI's technology development has been:
-
Generate a range of good solutions. Avoid passenger delays, avoid excessive cost, etc.
-
Recognise that it is impossible to quantify some soft constraints
-
Start from the existing schedule and attempt to get back on schedule within a limited time
-
Minimise changes to the schedule
-
Limit attention to actions that are easy to implement. E.g., cancel, delay, swap, move, divert, etc.
CTI has built a decision support system consisting of the following elements:
-
A Problem Manager that quantifies the effect of any disruption in terms of cost and consequential delays. This allows operations control personnel to quickly understand what has happened and identify quick manual solutions if these are obvious.
-
A Solution Generator that generates a range of potential solutions - all within existing hard constraints - to the problem. This is discussed in more detail below.
-
A Solution Manager that allows operators to view, compare, assess, accept or reject solutions.
-
A browser based interface (WebPAC) for other functions - not directly involved in the decisions regarding disruption management - to be notified of schedule changes
This is an important part of the system. It generates solutions using a combination of techniques:
-
A decision tree where each node is an action on a sector
-
Different initial actions to generate a range of reasonable solutions
-
Limited actions (cancel, delay, swap, etc) which can be applied to any sector
-
A predictor/corrector algorithm for efficiently comparing solutions and rejecting poor solutions early
-
Recursion whereby any solution can be improved using the same procedure as the original
The benefits of this approach are:
-
The algorithm only makes changes that have real benefits
-
The algorithm is fast; less than one minute for a fleet size of more than 200
-
The process can be truncated yet still yield acceptable solutions
-
The operator can view a range of solutions and make his/her own assessment
-
The algorithm adapts the schedule to cope with disruption, rather than changing schedule
Let us suppose that we have a disruption that has three basic solutions:
-
Solution 1: Cancel a flight and incur passenger delays of 1,000 hours
-
Solution 2: Make swaps, etc, and get relief crew. Incur delays of 500 hours and $5,000 costs
-
Solution 3: Use spare aircraft and relief crew. Incur delays of 100 hours and $25,000 costs
By presenting all the solutions to the operator he can see that:
-
The cost of reducing delays from 1,000 to 500 hours is $5,000
-
The cost of reducing delays from 500 to 100 is $20,000
On the face of it, option 1 is attractive unless:
-
There is some overriding instruction to avoid delays that day (due to previous problems and bad publicity)
-
There is some overriding instruction to limit the costs of managing disruptions (due to budget constraints)
-
The relief crew that should be available is not
The alternative solution, obtained by straightforward mathematical optimisation could be any one of the above depending on weighting factors that may have been determined weeks or months before. In addition;
-
It would not take in to account today's policies or priorities
-
It may suggest a solution that is not feasible on the day
The solution manager enables the user to look at a wide range of solutions.
Each solution comes with costs which are either hard ($) or soft (delay minutes), and implications (for example aircraft out of place overnight or passenger accommodation required, etc).
The user looks at all solutions and can reorder based on best or worst in any category and prune away unacceptable solutions and/or solutions which have unacceptable implications. Out of the solutions remain after this exercise the best solution can be selected.
Because the algorithm works on the basis of changes to the schedule, it is possible to produce information to the user indicating how the new schedule was produced from the old one. This makes it very easy to understand and rationalize.
CTI Recovery Optimisation has been field tested for a customer with a fleet size of 200+ aircraft.
The conclusions are:
-
Between 30 and 100 acceptable solutions can be produced in minutes
-
The system produces solutions as good as a very experienced Operations Controller
-
Using the Solution Manager, the user can take account of external factors
Although one of the requirements is to minimize schedule changes, it is essential that any changes are efficiently and effectively communicated to other functions, such as engineering, ground staff, etc.
CTI have built a read-only, browser based interface to operations control that allows other users to see what is happening, and what is planned. This is not the only communication mechanism since in many case changes are discussed before implementation. But it is a useful back up and aide memoire.
WebPAC can also be set up to actively alert users of changes that should be of interest. For example, maintenance might be interested in the destination and arrival times of aircraft due for scheduled maintenance.
The Recovery Optimisation problem is more complicated than it appears and not amenable to traditional optimisation methods. CTI have developed a decision support system that addresses this issue.
Recovery Optimisation works by quickly providing the user a range of acceptable solutions - with associated hard costs and implications - and analysis tools. This allows the user to deal with external issues, day-to-day changes in priorities and soft issues.
The system has been proven in practice at one major airline.
Further Information
You may wish to look at the PDF version ( 
) of this
document.