A stochastic 0-1 program based approach for the air traffic flow management problem

Thumbnail Image
Full text at PDC
Publication Date
Advisors (or tutors)
Journal Title
Journal ISSN
Volume Title
Elsevier Science
Google Scholar
Research Projects
Organizational Units
Journal Issue
We present a model and a robust algorithmic framework for the Air Traffic Flow Management Problem (TFMP) under uncertainty in airport arrival and departure and airspace capacity due to weather conditions. For this purpose we use the state-of-the-art 0-1 deterministic model due to Bertsimas and Stock. We present two 0-1 versions of the stochastic model, depending upon the type of recourse policy to use. A multistage scenario analysis approach based on a simple and full recourse scheme is used. The air traffic scheduling can be implemented for a given set of initial time periods in the full recourse environment and the solution for the other periods does not need to be anticipated and, then, it depends on the scenario to occur. We present a Fit-and-Relax approach to solve the very large-scale 0-1 deterministic equivalent model. Computational results are presented by comparing the deterministic approach (where the stochasticity of the uncertain parameters is reduced to their average) with the recourse based schemes; the optimality gap is within 0.25% of the LP optimal solution for most of the cases with dozens of thousands of constraints and variables.
Ahn, S., Escudero, L.F., Gugnard-Spielberg, M., Jurnsten K., 1993. Modeling robust policies for trading. 16th Conference on Modeling and Optimization, Compiegne, France. Alonso, A., 1997. Optimización combinatoria estocástica aplicada al control del tráfico aéreo. Ph.D. Thesis Dissertation. Universidad Complutense de Madrid. Andreatta, G., Brunetta, L., 1998. Multi-airport ground holding problem: A computational evaluation of exact algorithms. Operations Research 46 (1), 57-64. Bertsimas, D.J., Stock, S., 1994. The multi-airport flow management problem with en route capacities. Technical Report No. 3736-94 MSA, Sloan School of Management, Massachusetts Institute of Technology, Cambridge, MA. See also Operations Research 46 (3), 1998, 406-422. Dembo, R.S., 1991. Scenario optimization. Annals of Operations Research 30, 63-80. IBM OSL 1990. Optimization subroutine Library, Guide and Reference, SC23-0519. Matos, P., Chen, B., Ormerod, R., 1996. Optimization models for re-routing air traffic flows. Warwick Business School Research Papers, No. 240, University of Warwick, Coventry. Matos, P., Ormerod, R., 1995. The application of operational research to european air traffic management -understanding the context. Warwick Business School Research Papers, No. 200, University of Warwick, Coventry. Mulvey, J.M., Vandebei, R.J., Zenios, S.A., 1996. Robust optimization of large-scale systems: General modeling framework and computations. Operations Research 42, 205-221. Rockafellar, R.T., Wets, R.J.-B., 1991. Scenario and policy aggregation in optimization under uncertainty. Mathematics in Operation Research 16, 119-147. Vranas, P.B., Bertsimas, D.J., Odoni, A.R., 1994. The multiairport ground-holding problem in air traffic Control. Operations Research 42, 249-261.