Computerised decision support tools and optimisation are widely used among airlines. However, they are mainly used during the earlier stages of the planning process. At Operations Control manual processes dominate. The urgency in which decisions have to be taken leaves little room for formal optimisation. Furthermore, any system must be able to communicate with a number of existing systems residing on different types of platforms. As yet, no-one has been able to deliver an integrated system for the Management of Disruption (MOD) problem at larger airlines. Systems for crew control are emerging on the North-American market. Only one of those systems can be considered to be commercially available today, and that is designed to cover specific situations for a hub-and-spoke network. Other systems are still on the prototype level, and none of them has the scope of the system described here.
The MOD problem is by any standards very complex. The management of disruption often has weakly defined and often conflicting goals, a set of complex and interacting constraints, and solutions must often be identified within a very short time span. Hence, the problem to be solved in a given situation is not even well defined. In addition, a planning tool that will be used in the control environment has to be sufficiently intuitive to be able to be used by operation controllers, who are not necessarily familiar with the underlying problem solving techniques.
Regarding solutions, we have chosen to aim at a system which presents a small number (3 - 6) of feasible solutions to the operation controller. These solutions should be of almost equal value, but should be structurally different so that they represent true choices and not minor variations of the same solution. This approach leaves the maximum amount of freedom for the operations controller, and it still has the advantage of providing structured support for decision making in an extremely complex solution space.
The approach taken in the current project is that of prototype development based on use cases combined with simulation enabling identification of those real-life problems, which are most important to solve. The solution time limits greatly influence the choices of solution methods. This calls for heuristics. If, on the other hand, more time is available, solution methods resembling those used to produce the master plan based on advanced mathematical programming methods may be feasible. In both cases, the choice of problem representation is extremely important. With respect to heuristics, the representation should allow local search to be applied since many of the most successful heuristics are based hereon, while for other methods a formulation as a mixed integer linear program is essential.
Alternatively, a complete mathematical model for the MOD problem could be sought. Such a model will, however, at best be a multi-objective mixed integer model of tremendous dimensions, and no currently available optimisation software will be able to solve the model. Also, a purely artificial intelligence approach based on heuristic search and identifying and propagating constraints as needed could be taken. The nature of the MOD problem suggests that both of these methods applied individually will fail and that an integrated approach, in which one seeks to exploit all available problem solving techniques is the only way ahead.
The MOD problem is an extremely important problem seen in a real-life perspective. In particular, the development of a system with a user interface enabling an operations controller to use it without modelling and problem solving knowledge is a significant contribution. In order to construct such a system, ways of identifying the right problem to solve in terms of objectives and problem representation, and based thereon, ways of determining one or a set of feasible solution methods for the problem, are key issues.
Both in case where a high quality solution must be found in a short time period and in the case where an optimal solution must be identified, it is a major research task to develop the methods to be used. State of the art prototype methods are well known, but the experiences from other industrially related projects indicate that tailoring the prototype methods to match all the constraints of real-life problems is a highly complex research task.
The general planning situation for the MOD-problem is that a master plan for the operation is known and that this has to be modified in order to take into account small scale and large scale changes to the master plan that have occurred due to disruption.
In case nothing is known regarding how the master plan has been found, methods have to be developed to generate a small number of feasible changes, which from the point of view of cost/value are almost equally good, but which are structurally different that the planners see these as true alternatives. Evolutionary metaheuristics are known to be able to provide such solutions, but are often too slow to use in an on-line environment. Other metaheuristics like Simulated Annealing and Tabu Search are on the other hand known to produce good solutions fast, but do usually not provide structurally different alternatives. The objective is hence to develop a set of problem specific methods, which fulfil the requirements both with respect to solution time and structure of solutions.
One way of tackling the situation is for each master plan to build a "solution library" for foreseeable problems. Drawing on experience from master plans similar to the one in question, revised plans for the most likely or most difficult changes may be developed in the time between the generation of the master plan and the day of operation. The feasibility of this approach can then be evaluated using the developed off-line simulation tool.
If the rules by which the master plan was generated are known, additional information may be available, which eases the task of finding alternative plans. More specifically, the problem may now be tackled as a dynamic problem, in which one has to adjust the solution corresponding to information, which changes over time. Here the research issue is to develop methods, which can take advantage of information already present, thereby enabling much more efficient solution of the problem at hand than possible if the problem is solved from scratch.
If the allowed solution time is sufficiently large, methods generating optimal solutions for the given problem may be feasible. Such methods build on integer programming, and development of specific methods for the MOD-problem is hence an integral part of the project.
If non-optimal solution methods are used, it is important to identify the potential benefit lost by using heuristics rather than optimal methods. The proposed solutions hence have to be evaluated, i.e. compared against either optimal solutions or tight bounds on the value of an optimal solution for the problem at hand. This again calls for the development of optimal solution methods for the MOD-problem.
From a systems development point of view, the contribution of the project is to develop a tool, which enables the integration of the planning process. The integrated tool must have a user interface enabling the daily planner to use it in decision making without detailed knowledge of the underlying solution methods. Hence, a key issue is identifying/agreeing upon methods for validation of the system from the user perspective.
This situation is not unique for the airline industry, but appears also in other cases. Examples particularly relevant for current DTU projects are routing of vehicles for public and private transportation, production planning in shipyards, and planning of operation of telecommunication networks. Therefore, the methods developed and the experiences gathered in the project are envisaged to have substantial impact on other industrial and public sectors.
The technical achievements of the project fall into two categories: Solution methods and software tools.
Development of a span of solution methods for the MOD ranging from table-look-up in a pre-calculated solution library over fast heuristic methods to time consuming optimal methods is a major research issue. The results of the development process are easily quantifiable and verifiable since the methods can be tested against each other and against common practice in the airline industry with respect to solution quality and solution time.
Testing software tools for planning is a complex task involving both technical issues (user interface, response time, reliability, portability etc.) as well as managerial issues (implementation in the organisation). Here, design of the measures and verification process has to be decided in the first phase of the project.
The prime technical risks in the project are that 1) it will turn out to be impossible to develop solution methods, which on the one hand meet the timing requirements of the planner and on the other hand produce solutions of sufficiently high quality and 2) the development of a system, which requires no modelling and solution knowledge for the planners, may turn out to be impossible. However, managing the risks can most reasonably be done by identifying which among the research objectives are of prime importance for the partners in order that the project contributes significantly to the advancement of technology in the organisation.
The simulation model implies little risk, but will be of great value to the operations controllers. At the first milestone (15 months), the on-line simulation model and the first use case should be completed, and the second use case should be conceptually modelled. If the optimisation approach faces any of the two technical risks mentioned above, the following fall-back positions are open: 1) reduce the scope and concentrate on one or two of the use-cases; 2) accept longer solution times as sacrificing quality would risk credibility among the operations controllers; 3) accept a system that requires some modelling knowledge; 4) abandon the optimisation path and settle with simulation. Option 4) would result in a shorter project.
A final additional risk area is that of data quality and timeliness. Management of disruption is entirely dependent upon good quality information being available in a timely manner. This risk has been minimised by the implementation within British Airways of a new corporate operational database which is already on-line for a small number of operational applications in the Ops Control area. This insulates the work of this project from requiring to obtain such operational data, which includes aircraft movement times, crew availability, ATC slot times and many other items. In effect, this risk has already been addressed.