×

zbMATH — the first resource for mathematics

Aircraft deconfliction with speed regulation: new models from mixed-integer optimization. (English) Zbl 1301.90062
Summary: 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.

MSC:
90C11 Mixed integer programming
90C26 Nonconvex programming, global optimization
90C90 Applications of mathematical programming
Software:
AMPL; ROSE
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alonso-Ayuso, A; Escudero, LF; Martín-Campo, FJ, Collision avoidance in air traffic management: a mixed-integer linear optimization approach, IEEE Trans. Intell. Transp. Syst., 12, 47-57, (2011)
[2] 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) · Zbl 1349.90641
[3] Belotti, P; Lee, J; Liberti, L; Margot, F; Wächter, A, Branching and bounds tightening techniques for non-convex MINLP, Optim. Methods Softw., 24, 597-634, (2009) · Zbl 1179.90237
[4] 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)
[5] Durand N., Alliot J.M.: Optimal resolution of en-route conflict. In: Proceedings of the Eurocontrol/FAA ATM Seminar. Eurocontrol/FAA, (1997)
[6] 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) · Zbl 1179.90237
[7] 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)
[8] 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)
[9] EUROCONTROL: Eurocontrol long-term forecast : IFR Flight Movements 2010-2030. Technical report, Eurocontrol-Air Traffic Statistics and Forecasts (2010)
[10] Fortet, R, Application de l’algèbre de Boole en recherche opérationelle, Revue Française de Recherche Opérationelle, 4, 17-26, (1960)
[11] Fourer, R., Gay, D.: The AMPL Book. Duxbury Press, Pacific Grove (2002)
[12] Granger, G., Durand, N.: A traffic complexity approach through cluster analysis. In: Proceedings of the 5th ATM R &D Seminar, Budapest (2003)
[13] Hammer, P.L., Rudeanu, S.: Boolean Methods in Operations Research and Related Areas. Springer, Berlin (1968) · Zbl 0155.28001
[14] Kuchar, J; Yang, L, A review of conflict detection and resolution modeling methods, IEEE Trans. Intell. Transp. Syst., 1, 179-189, (2000)
[15] 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)
[16] Martín-Campo, F.J.: The collision avoidance problem: methods and algorithms. Ph.D. thesis, Rey Juan Carlos University, Madrid (2010)
[17] 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, 3-11, (2002)
[18] 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)
[19] 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)
[20] Richards, A., How, J.P.: Aircraft trajectory planning with collision avoidance using mixed integer linear programming. In: American Control Conference, Anchorage, Alaska, (2002)
[21] SESAR consortium: The european ATM master plan. Technical Report 1, European Commission and EUROCONTROL, (2009)
[22] 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)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.