RobustATM
RobustATM – Robust optimization of ATM planning processes by modelling of uncertainty impact. The RobustATM project belongs to the 2nd WPE Call for Projects.
Abstract
Planning, particularly scheduling of limited resources is one of the main challenges of Air Traffic Management (ATM). Uncertainty, inaccuracy and non-determinism almost always lead to a deviation from the actual plan or schedule. State-of-the-art to deal with these changes in the ATM context is regular re-computation or update of the schedule. These adjustments are performed when a change in the input data has occurred. The challenge is to incorporate uncertainty into the initial computation of the plans so that these plans are robust with respect to changes in the data leading to a better utilization of resources, to more stable plans and to a more efficient support for ATM controllers and stakeholders. State-of-the-art in mathematics when addressing uncertainties in planning is an application of two different approaches to handle uncertainty: stochastic optimization to get optimal expected values and robust optimization to protect against worst-case scenarios within a predetermined uncertainty set. In this project an appropriate ATM application will be chosen for investigation. Using this application, the two optimization approaches mentioned above will be compared with respect to their costs and benefits. Furthermore, the goal is to combine these approaches and develop appropriate mixed models to gain the advantages from both optimization techniques. Afterwards, a generalization of the new models is planned to make them usable for other ATM applications as well.
Introduction and problem statement
Introduction
In planning and optimization processes we ubiquitously have to handle incomplete or erroneous data. Thus to build up a real-world model, uncertainty has to be incorporated in the process to achieve robust outcome. In the context of air traffic management a very efficient use of limited ATM resources is required, e.g. aircraft, fuel, passenger gates, runway capacity, arrival and departure routes. Performance-based ATM is heavily promoted by SESAR. Currently it is impossible to create schedules for future use which never need to be adapted. Reasons are uncertainties of input data whose sources can be divided into the following major groups: human, meteorology, technic and transparency of data. These are, just to name a few, e.g., weather forecasts, late passengers, strikes, inaccurate estimates, which lead to deviations from schedule. These uncertainties affect many ATM processes and thereby updates of the plans are unavoidable. For instance, uncertainties influence the process of tactical arrival/departure management or of pre-tactical arrival/departure flow control. Examples of critical problems caused by uncertainties can be found especially at hub airports or at airports working on the limits of their capacity as well as at overloaded sectors. Therefore, stable plans that take into account these uncertainties are essential to support efficient utilization of available resources. Furthermore, a holistic approach to control processes under uncertain conditions is still missing. Hence, it is crucial to develop mathematical methods that enable this control. Thus, considering airline, air traffic and airport schedules/processes, a robustification (i.e., getting full protection against a determined set of uncertainties) by the use of mathematical methods and models, is of great importance.
Problem statement
Since ATM resources are limited, their efficient utilization is the main goal of all stakeholders involved in ATM planning processes. Technical support tools enable optimal planning of resources assuming, that their availability is exactly known. However, processes in an ATM system are always influenced by disturbances of different types and by uncertain input data for the planning of these processes. Therefore, the resulting schedule is uncertain. Current state-of-the-art in ATM planning is a computation of a new plan if there are changes in the input data on the basis of updated information. Disturbances can be classified by their type, frequency, intensity and duration. However, it is more important in the planning process to detect the impact of a disturbance on each considered resource or input data. For instance, a snowfall and a defective aircraft in the apron area of an airport are different types of disturbances. However, they cause a decreasing of the capacity of the runway system or even its closure for some time period. In other words, it should be investigated which uncertainty brings the disturbance into resource availability and estimation of input data for a planning process. Our goal is to investigate how the impact of uncertainties can be modelled in order to achieve robustification of planning processes and efficient utilization of resources.
Project objectives and expected results
Objectives
As it was already mentioned, there exist two different mathematical approaches to handle uncertainty in optimization: stochastic optimization and robust optimization. Both approaches will be described more precisely in the section Approach/methodology. They have not been considered in detail in the context of ATM, yet. A comparison between them will provide evidence for the costs and benefits. Steps beyond the state-of-the-art have two aspects. The first addresses the application of innovative mathematical methods according to ATM problems and the second considers the development of a new method of the ATM planning under uncertainties. For the first aspect an evaluation is performed to quantify the benefits and costs of application of innovative mathematical methods for optimization of planning in the ATM context. Hence, an assessment if such methods should be used for the development of support systems could be performed by SESAR. The second aspect addresses the mixture of stochastic and robust approaches in ATM which will provide protection against worst-case scenarios, where needed, as well as good mean values to handle occurring uncertainty. Thereby the problem of (over-)conservatism, leading to higher costs, will be avoided. Hence, application of these new mathematical approaches for ATM problems allows to expect a great benefit in cost reduction and reliability.
Expected Results
It will be reported which ATM planning problem is selected for investigation and the impact of disturbances will be described. For the selected problem both stochastic and robust optimization approaches will be implemented and integrated into the Mixed Integer Program (MIP) solver Gurobi. It will be analysed which optimization techniques are appropriate for the solution of the selected ATM planning problem. Further, the stochastic and robust approaches will be used to create a new combined model. Its implementation based on Gurobi and heuristics of DLR’s scheduling toolbox will be tested with the selected application. The concept of the new optimization approach for ATM applications, including the model and computational efforts will be described in a report. The project considers and analyses four approaches: nominal approach without explicit modelling of uncertainty (to have a benchmark for the other solutions), stochastic approach, robust approach and the new combined approach. To evaluate them extensive simulations with the selected ATM application will be performed and corresponding validation and analysis reports will be delivered. Moreover, the combined approach will be generalized, so that it is not only usable for the selected application, but can be beneficial for other ATM planning problems. The results of the generalization will be summarized in a report. Additionally, a remarkable benefit for mathematics is expected. Existing tools will be enhanced as well as new techniques will be applied and proved. Likewise, research in the relatively new field of robust optimization will be done especially with respect to real-time computing. These outcomes will also be presented in a conference and in a journal paper. The communication to EUROCONTROL and the SJU as well as the communication to the ATM community will guarantee the dissemination of project results to external organisations, i.e. end-users and industry. The created robust planner can act as a prototype for industrial applications (e.g. robust Total Airport Management, robust flow planning for a whole airport, airline fleet management).
Approach/methodology
Since the focus of the project lies on providing of optimal decisions in the presence of uncertainty, we first have to model uncertainty of resources availability and of other input data for the planning. In the case when a disturbance occurs or some input data are incomplete/uncertain we study their impact on the used resources. Thereby it is non-relevant whether the uncertainty is caused by, for instance, fog or by heavy rain. It will be considered how the disposable resource is affected by its presence, e.g. availability and saturation of a runway capacity. The character of impact on resources caused by disturbance(s) can be distinguished between an immediate impact on resources availability and an impact some time later. Functionally an influence of disturbance(s) on a resource can vary from gradually decreasing of resource availability to the complete elimination of resource from the process of its utilization. For instance, continuing snowfall can lead to a gradual reduction of runway capacity up to the closure of runway that means its complete elimination as a resource. Our goal is to investigate this impact and to model it within the possible time and probability corridor. The obtained mathematical description should allow highly complex interference patterns to include all possible uncertainties. Furthermore an optimization of the performance of the considered ATM system when disturbances occur is only possible with mathematical methods approving an objective validation. The preferred methods are located in discrete stochastic and robust optimization. The goal of stochastic optimization is to describe an uncertainty by (multi-dimensional) probability distributions and then to optimize the expected value of these. From a computational point of view the only distribution that can manage this, is discrete, because there are no existing models that apply continuous distributions. A straight forward approach with such a discrete scenario set leads to huge MIPs with block diagonal matrix structure.
The second approach to incorporate uncertainty is located in robust optimization. In difference to the stochastic approach, robust optimization assumes that the probability distributions of the uncertainties are unknown. But the uncertainties occur within a certain predefined space. The task of robust optimization is to find a solution that is feasible for all considered scenarios, including the worst-case scenario in the considered uncertainty space, and which optimizes the objective function. In this respect, robust optimization methods protect against worst-case scenarios and do not need any probability distribution within the space. But often they are too conservative and thus too expensive. Hence, it is crucial to find an appropriate description of uncertainty sets: as simple as possible, appropriate for the mathematical model and still reflecting reality well enough. In scheduling problems, e.g. in the Arrival Management, the uncertainty sets can be modelled as boxes: Consider two aircrafts A1 and A2, scheduled on time t1 and t2. Due to uncertainties, the arrival time varies in the range [t1-∆t, t1+∆t] and [t2-∆t, t2+∆t]. Thus, we get a box describing the uncertainty set. However, due to mathematical considerations, it often makes sense to reduce this box to an ellipsoid. Furthermore, we can decrease the size of the ellipsoid with increasing knowledge available. In this project stochastic as well as robust optimization methods for an ATM planning problem will be applied and verified. Moreover, these two approaches will be combined to develop a conceptually new approach that involves advantages of both methods. The impact of uncertainty on the resources is crucial for this issue and therefore has to be studied. The analysis of the different uncertainties should provide evidence for the appropriateness of the investigated methods. Furthermore our aim is to develop new methods to incorporate the serial structure of the planning problem at hand to ensure short runtimes which are imperative for an operative environment.
Project consortium and contact information The project consortium consists of the Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU) and the German Aerospace Center (DLR). Coordinator: Prof. Dr. Alexander Martin, FAU, Chair of Economics, Discrete Optimization, Mathematics Contact: Prof. Dr. Frauke Liers (Project Leader, FAU) frauke.liers @ math.uni-erlangen.de
Dr. Olga Gluchshenko (DLR) olga.gluchshenko @ dlr.de
