Abstract
Detecting and solving aircraft conflicts, which occur when aircraft sharing the same airspace are too close to each other according to their predicted trajectories, is a crucial problem in Air Traffic Management. We focus on mixed-integer optimization models based on speed regulation. We first solve the problem to global optimality by means of an exact solver. Since the problem is very difficult to solve, we also propose a heuristic procedure where the problem is decomposed and it is locally exactly solved. Computational results show that the proposed approach provides satisfactory results.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
1 NM (Nautical Mile) = 1,852 m.
References
Alonso-Ayuso, A., Escudero, L.F., Martín-Campo, F.J.: Collision avoidance in air traffic management: a mixed-integer linear optimization approach. IEEE Trans. Intell. Transp. Syst. 12(1), 47–57 (2011)
Alonso-Ayuso, A., Escudero, L.F., Martín-Campo, F.J.: A mixed 01 nonlinear optimization model and algorithmic approach for the collision avoidance in ATM: velocity changes through a time horizon. Comput. Oper. Res. 39(14), 3136–3146 (2012)
Belotti, P., Lee, J., Liberti, L., Margot, F., Wächter, A.: Branching and bounds tightening techniques for non-convex MINLP. Optim. Methods Softw. 24(4), 597–634 (2009)
Bonini, D., Dupré, C., Granger, G.: How ERASMUS can support an increase in capacity in 2020. In: Proceedings of the 7th International Conference on Computing, Communications and Control Technologies: CCCT 2009, Orlando, Florida (2009)
Durand N., Alliot J.M.: Optimal resolution of en-route conflict. In: Proceedings of the Eurocontrol/FAA ATM Seminar. Eurocontrol/FAA, (1997)
Durand, N., Alliot, J.M.: Ant-colony optimization for air traffic conflict resolution. In: Proceedings of the Eighth USA/Europe Air Traffic Management Research and Development Seminar. Eurocontrol/FAA (2009)
Durand, N., Alliot, J.M., Noailles, J.: Automatic aircraft conflict resolution using genetic algorithms. In: Proceedings of the Symposium on Applied Computing, Philadelphia. ACM (1996)
Durand, N., Granger, G.: Modeling the controller’s conflict detection task using fast time simulation. In: 30th Digital Avionics Systems Conference (DASC), Seattle, USA (2011)
EUROCONTROL: Eurocontrol long-term forecast : IFR Flight Movements 2010–2030. Technical report, Eurocontrol–Air Traffic Statistics and Forecasts (2010)
Fortet, R.: Application de l’algèbre de boole en recherche opérationelle. Revue Française de Recherche Opérationelle 4, 17–26 (1960)
Fourer, R., Gay, D.: The AMPL Book. Duxbury Press, Pacific Grove (2002)
Granger, G., Durand, N.: A traffic complexity approach through cluster analysis. In: Proceedings of the 5th ATM R &D Seminar, Budapest (2003)
Hammer, P.L., Rudeanu, S.: Boolean Methods in Operations Research and Related Areas. Springer, Berlin (1968)
Kuchar, J., Yang, L.: A review of conflict detection and resolution modeling methods. IEEE Trans. Intell. Transp. Syst. 1(4), 179–189 (2000)
Liberti, L., Cafieri, S., Tarissan, F.: Reformulations in mathematical programming: a computational approach. In: Abraham, A., Hassanien, A.-E., Siarry, P., Engelbrecht, A. (eds.) Foundations of Computational Intelligence (Global Optimization: Theoretical Foundations and Applications), vol. 203 of Studies in Computational Intelligence, pp. 153–234. Springer, Berlin (2009)
Martín-Campo, F.J.: The collision avoidance problem: methods and algorithms. Ph.D. thesis, Rey Juan Carlos University, Madrid (2010)
Pallottino, L., Feron, E., Bicchi, A.: Conflict resolution problems for air traffic management systems solved with mixed integer programming. IEEE Trans. Intell. Transp. Syst. 3(1), 3–11 (2002)
Rey, D., Constans, S., Fondacci, R., Rapine, C.: A mixed integer linear model for potential conflict minimization by speed modulations. In: Proceedings of the International Conference on Research in Air Transportation, Budapest (2010)
Rey, D., Rapine, C., Fondacci, R., El Faouzi, N.-E.: Minimization of potential air conflicts through speed regulation. Transp. Res. Rec. J. Transp. Res. Board. 2300(1), 59–67(2012)
Richards, A., How, J.P.: Aircraft trajectory planning with collision avoidance using mixed integer linear programming. In: American Control Conference, Anchorage, Alaska, (2002)
SESAR consortium: The european ATM master plan. Technical Report 1, European Commission and EUROCONTROL, (2009)
Vela, A., Solak, S., Singhose, W., Clarke, J.-P.: A mixed-integer program for flight-level assignment and speed control for conflict resolution. In: Proceedings of the Joint 48th IEEE Conference on Decision and Control and 28th Chinese Control Conference, Shanghai (2009)
Acknowledgments
The authors are grateful to the anonymous referees for their constructive comments that helped improving the paper. The first author gratefully acknowledges financial support under grant ANR 12-JS02-009-01 “ATOMIC”.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Cafieri, S., Durand, N. Aircraft deconfliction with speed regulation: new models from mixed-integer optimization. J Glob Optim 58, 613–629 (2014). https://doi.org/10.1007/s10898-013-0070-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-013-0070-1