Stability Analysis of Runway Schedules
- 29 April 2016
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Intelligent Transportation Systems
- Vol. 17 (12), 3380-3390
- https://doi.org/10.1109/tits.2016.2552082
Abstract
By performing stability analysis on an optimal runway schedule, this paper derives a method to determine whether an optimized landing sequence of aircraft remains optimal after an arbitrary number of aircraft in that sequence are delayed by an arbitrary amount of time. We consider the problem of scheduling aircraft landing on a single runway with the objective of maximizing throughput under changing external conditions such as delays caused by weather. Instead of optimizing the schedule every time delays occur, stability criteria allow for fast evaluation of whether schedules remain optimal. This paper develops a method to compute stability regions for a set of schedules. Sensitivity analysis of the linear programming relaxation and a nonlinear relationship between the delay of individual aircraft and the incurred cost change for all landing sequences yield the stability information. Furthermore, the properties of a first-come-first-serve policy are studied by giving sufficient conditions and a heuristic condition for the optimality of first-come-first-serve sequences. The given results are shown to be also applicable to landing sequences obtained through local neighborhood search, sequences that obey a position shift constraint, and subsequences of landing sequences as used in a rolling horizon approach.Keywords
Funding Information
- U.S. Air Force (FA 8650-07-2-3744)
This publication has 23 references indexed in Scilit:
- Scheduling of airport runway operations using stochastic branch and bound methodsTransportation Research Part C: Emerging Technologies, 2014
- Airport runway schedulingAnnals of Operations Research, 2013
- Algorithms for Scheduling Runway Operations Under Constrained Position ShiftingOperations Research, 2010
- On the waiting time of arriving aircrafts and the capacity of airports with one or two runwaysEuropean Journal of Operational Research, 2007
- Stochastic Programming in Transportation and LogisticsHandbooks in Operations Research and Management Science, 2003
- Interval Estimation for a Binomial ProportionStatistical Science, 2001
- Some concepts of stability analysis in combinatorial optimizationDiscrete Applied Mathematics, 1995
- Stability of discrete optimization problemsCybernetics and Systems Analysis, 1993
- The dynamic scheduling of aircraft in high density terminal areasMicroelectronics Reliability, 1989
- Stability, parametric, and postoptimality analysis of discrete optimization problemsCybernetics and Systems Analysis, 1984