Uncertainty models for optimal and robust ATM schedules
Andreas Heidt, FAU Erlangen-Nürnberg
Supervisor: Prof. Dr. Alexander Martin
In the context of air traffic management efficient use of limited ATM resources is required, e.g., runway capacity, aircraft, fuel, passenger gates, arrival and departures routes, buses and other turnaround resources. This requirement is also reflected in more than ten articles presented EUROCONTROL/FAA ATM conference (ATM 2009 in Napa/California) which deal with resource scheduling. Although performance-based ATM [SE] is heavily promoted by SESAR, it is impossible to create schedules for future use which never need to be adapted. Reasons are uncertainties, e.g., unexpected weather conditions, late passengers, late arrival, etc., which lead to intended and unintended deviations from schedule. State-of-the-art is to update and thereby change the plans by occurrence of uncertainties. But every intervention affects the whole ATM-system. Thus we have to accept these phenomena and have to incorporate uncertainty into the model, with the aim to get robust plans with respect to the data and to achieve a better utilization of resources and more efficient support for ATM controllers.
Such problems arise in different ATM applications, for instance, in the tactical arrival and departure management which efficient design is studied in [CH, ER, HE, NEU, VO] and in the pre-tactical runway flow control considered in [GI1, GI2, GL]. Examples for other ATM problems occur at Airline Scheduling at Airports and Aircraft Turnaround Operations [WU], congested airport and sectors [GI3] as well as speed adjustments [WA]. To handle uncertainty in a more efficient way, the aim is to “robustify” airline, air traffic and airport schedules/processes beforehand. Extensive research has been done regarding ATM scheduling, but uncertainty, sensitivity analysis as well as discrete and stochastic optimization methods have hardly been considered. Despite this there is a strong need for robust planning based on modelling of uncertainty aspects. This applies to both scheduling of a single resource, e.g., one inbound, one bus, one gate, and multiple resources, i.e., flows.
The thesis addresses scheduling problems concerning ATM while considering uncertainty and using methods of discrete optimization. Therefore, the focus of the assigned task lies on modeling, understanding and controlling uncertainty in ATM problems. The ambition is to evaluate approaches to model ATM planning problems in a robust way and to develop new and appropriate algorithms and solution techniques to cope with uncertainty.
Methodology & Techniques
The preferred methods to approach these ATM-problems are located in discrete and robust optimization since the focus of these methods is to provide optimal decisions in the presence of uncertainties. The ATM scheduling problems have been mathematically described as a combinatorial and discrete mathematical optimization problem. To solve such (mixed-)integer (non-linear) programs, different methods from discrete optimization have been applied. Furthermore, we have defined the characteristics of the uncertainties. To incorporate them, there is the possibility to choose different uncertainty sets, i.e., sets that describe the uncertainty in the input data, like box uncertainty or ellipsoidal uncertainty sets. The methodology also depends on the choosen uncertainty set, e.g., we have used straight forward robust approaches for box uncertainties, and second-order cone programming methods for ellipsoidal uncertainty sets.
With these methods we engaged in and will further work on
- analysing the impact of uncertainty
- the research for approaches to model ATM planning problems in a mathematically robust way
- the development of new and effective algorithms and solution techniques in order to cope with uncertainty
- measuring of Robustness
Models & Robust approaches
In general, scheduling problems in ATM can be mathematically modeled in a straight forward way. Thereby it is modeled as a mixed-integer-problem (MIP), deciding the ordering of the aircraft together with the scheduled time, mathematically called a scheduling problem. Since there are non-linearities, coming up with deciding the sequence, this is mathematically very challenging. Alternatively, one can discretize the time horizon into time slots, which we call a time-indexed model. This then leads to a linear binary integer program (IP), which computes for every discretized point in time, whether an aircraft is scheduled and if so, which one is. Thereby the problem class is reduced, but the number of variables and constraints increases rapidely by the number of time slots. One of the first goals in this thesis was to compare both models for the runway scheduling problem, both preserving the setting of the problem. Because of performance reasons we have chosen the time-indexed model for robustification. Thus from a mathematical point of view we consider an assignment problem with further constraints, preserving the minimum separation times between two consecutive aircraft.
To cope with uncertainties, mainly lying in the earliest and latest possible take-off and touch-down times, we utilised the mathematical structure of the uncertainty. The idea of Bertsimas/Sim [BS] would protection against a several number of deviations from the earliest possible times. Ben-Tal, El Ghaoui and Nemirovski [BGN] consider ellipsoidal uncertainty sets, that may mathematically lead to second-order cone programming. Knowing that the uncertainties lie at the boundary of the intervall of earliest and latest time, it was possible to develop a strict robust model. We have compared the strict robust time-indexed model with the nominal one, which does not imply robustness aspects. Thereby we have choosen different discretization sizes (time slot sizes) in the simulation and tested for different measurements, like go-arounds, departures drops, changes in position and changes in target times. Since for greater discretization sizes makespan as well as punctuality gets worse, we developped a dynamic time-discretized model, i.e., for each aircraft and remaining time to touch-down, one can choose a different time-discretization. Thus, for "far-away" aircraft a greater discretization is meaningful, whereas the nearer an aircraft gets to its destination, the more exact the solution gets.
Furthermore strict robust models are conservative in general. We discovered that we do not suffer from this, because the strict robust model computes less go-arounds and less departure drops. Nevertheless it was worth thinking of less conservative models. We hereby developped in cooperation with the RobustATM project a light and recoverable model for the runway scheduling problem. The preliminary computational results are very promising and we will study these models in a mathematical way to prove the results in theory.
- A. Heidt and O. Gluchshenko, From uncertainty to robustness and system's resilience in ATM: a case study, Proceedings of 3rd International Air Transport & Operations Symposium, Delft, Netherlands, 2012, ISBN 9781614991182
- Polyhedral Approximation of Ellipsoidal Uncertainty Sets via Extended Formulations - a computational case study -, Tech. Report. (submitted 2014), A. Bärmann, A. Heidt, A. Martin, S. Pokutta, C. Thurner
- A. Heidt, H. Helmke, F. Liers and A. Martin, Robust Runway Scheduling Using a Time-indexed Model, Proceedings of 4th SESAR Innovation Days, Madrid, Spain, 2014
- N. Fürstenau, A. Heidt, H. Helmke, M. Kapolke and F. Liers, Pre-Tactical Time Window Assignment: Runway Utilization and the Impact of Uncertainties, Proceedings of 4th SESAR Innovation Days, Madrid, Spain, 2014
- First ComplexWorld Conference, Sevilla, July 6-7, 2011, Complexity and Air Traffic Management
- First SESAR InnovationDays, Toulouse, ENAC, November 29 - December 1, 2011
- Third International Air Transport & Operations Symposium, Delft, June 18-20, 2012
- Second SESAR InnovationDays, Braunschweig, November 27 - 29, 2012
- Third SESAR InnovationDays, Stockholm, November 26 - 28, 2013
- International Conference on Operations Research, Aachen, September 2 - 5, 2014
- Fourth SESAR InnovationDays, Madrid, November 25 - 27, 2014
[AG] A. Agogino: Robustness of two Air Traffic Scheduling Approaches to Departure Uncertainty, 30th Digital Avionics Systems Conference (DASC), Seattle, 2011
[AN] I. Anagnostakis, J.P. Clarke: Runway operations planning: a two-stage solution methodology, Proceedings of the 36th Hawaii International Conference on System Sciences, 2003
[BA] H. Balakrishnan, B.Chandran: Scheduling Aircraft Landings under Constrained Position Shifting. AIAA Guidance, Navigation, and Control Conference and Exhibit, Keystone, Colorado, 2006
[BGN] A. Ben-Tal, L. El Ghaoui, A. Nemirovski: Robust Optimization, Princeton University Press, 2009
[BN] A. Ben-Tal, A. Nemirovski: Robust Solutions of Uncertain Linear Programs", Operations Research Letters , Vol. 25, pp. 1-13, 1999
[BS] D. Bertsimas, M. Sim: The price of robustness, Operations Research, 52(1):35-53, 2004
[CH] V. Cheng, L. Crawford, P. Menon: Air traffic control using genetic search techniques, Control Applications, 1999, Proceedings of the 1999 IEEE International Conference, 2002
[CL] G. Clare, A. Richards: Optimization of taxiway routing and runway scheduling, IEEE Trans. Intell. Transp. Syst., vol. 12, no. 4, pp.1000 -1013, 2011
[DY] M. Dyer, L. Wolsey: Formulating the single machine sequencing problem with release dates as a mixed-integer program, Discrete Applied Mathematics, no. 26 (2-3), pp. 255-270, 1990
[ER] H. Erzberger, W. Nedell: Design of automated system for management of arrival traffic, NASA Technical Memorandum 102201, 1989
[FI] M. Fischetti, M. Monaci: Light robustness, in R.K. Ahuja, et al. (Eds.): Robust and online large scale optimization, Springer, 2009
[GI1] E. Gilbo, H. Kenneth: Collaborative Optimization of Airport Arrival and Departure Traffic Flow Management Strategies for CDM, 3rd USA/Europe Air Traffic Management R&D Seminar, Napoli, Italy, 2000, June 13-16
[GI2] E. Gilbo: Optimizing airport capacity utilization in air traffic flow management subject to constraints at arrival and departure fixes, Control Systems Technology, IEEE Transactions, 2002
[GI3] E. Gilbo, S. Smith: Monitoring and Alerting Congestion at Airports and Sectors under Uncertainty in Traffic Demand Predictions, Air Traffic Control Quarterly, 19(2): 83-113, 2011
[GL] O. Gluchshenko: Dynamic Usage of Capacity for Arrivals and Departures in Queue Minimization, Control Applications (CCA), 2011 IEEE International Conference on, 2011, pp. 139-146
[HE] H. Helmke, R. Hann, D. Müller, M. Uebbing-Rumke, D. Wittkowski: Time-Based Arrival Management for Dual Threshold Operation and Continous Descent Approaches , 8th FAA/Eurocontrol ATM Seminar, Napa, California, USA, 2009
[KJ] D. Kjenstad, C. Mannino, T.E. Nordlander, P. Schittekat and M. Smedsrud: Optimizing AMAN-SMAN-DMAN at Hamburg and Arlanda airport, Proceedings of the SID, Stockholm, 2013
[LI] C. Liebchen, M. Lübbecke, R. Möhring and S. Stiller: The concept of recoverable robustness, in R.K. Ahuja et al. (Eds.): Robust and online large scale optimization, Springer, 2009
[NEU] F. Neuman, H. Erzberger: Analysis of sequencing and scheduling methods for arrival traffic, NASA Technical Memorandum, Moffett Field, California, 1990
[SCH] A. Schöbel: Generalized light robustness and the trade-off between robustness and nominal quality, Mathematical Methods of Operations Research, Vol.80, pp.161-191, 2014
[SE] SESAR consortium: The ATM Target Concept D3, DLM-0612-001-02-00, 2007
[VO] U. Völkers: Arrival planning and sequencing with COMPAS-OP at the Frankfurt ATC-Center, The 1990 American Control Conference, San Diego, California, 1990
[WA] T.-C. Wang, Y.-J. Li: Optimal Scheduling and Speed Adjustment in En Route Sector for Arriving Airplanes, Journal of Aircraft, Vol. 48, No. 2, 2011
[WU] C.-L. Wu: Airline Operations and Delay Management, Ashgate Publishing Limited, 2010