publication . Preprint . Conference object . 2017

Complex Number Formulation and Convex Relaxations for Aircraft Conflict Resolution

David Rey; Hassan Hijazi;
Open Access English
  • Published: 20 Mar 2017
Abstract
We present a novel complex number formulation along with tight convex relaxations for the aircraft conflict resolution problem. Our approach combines both speed and heading control and provides global optimality guarantees despite non-convexities in the feasible region. As a side result, we present a new characterization of the conflict separation condition in the form of disjunctive linear constraints. Our formulation features one binary variable per pair of aircraft, is free of trigonometric functions, and captures the non-convexity in a set of quadratic concave constraints. Using our approach, we are able to close a number of open instances and reduce computa...
Subjects
free text keywords: Computer Science - Computational Engineering, Finance, and Science, Order of magnitude, Mathematical optimization, Feasible region, Complex number, Atmospheric model, Trajectory, Global optimality, Computer science, Regular polygon, Conflict resolution
31 references, page 1 of 3

[1] Eurocontrol, “Performance review report,” Eurocontrol, 96, rue de la Fuse, B-1130 Brussels, Belgium, Tech. Rep., 2011. [Online]. Available: https://www.eurocontrol.int/sites/default/files/ publication/files/prr-2011.pdf

[2] European Comission and Eurocontrol, “European air traffic management master plan,” SESAR, Tech. Rep., 2009.

[3] Federal Aviation Administration, “FAA's NextGen Implementation Plan,” FAA, Tech. Rep., 2011.

[4] M. Nolan, Fundamentals of Air Traffic Control. Cengage Learning, 2010.

[5] ICAO, “Rules of the air and air traffic services,” International Civil Aviation Organization, Tech. Rep., 1996.

[6] P. Averty, “Conflict perception by atcs admits doubt but not inconsistency,” in 6th USA/Europe Air Traffic Management Research and Development Seminar, Baltimore, USA, 2005.

[7] J. K. Kuchar and L. C. Yang, “A review of conflict detection and resolution modeling methods,” Intelligent Transportation Systems, IEEE Transactions on, vol. 1, no. 4, pp. 179-189, 2000.

[8] A. Richards and J. P. How, “Aircraft trajectory planning with collision avoidance using mixed integer linear programming,” in American Control Conference, 2002. Proceedings of the 2002, vol. 3. IEEE, 2002, pp. 1936-1941.

[9] L. Pallottino, E. M. Feron, and A. Bicchi, “Conflict resolution problems for air traffic management systems solved with mixed integer programming,” IEEE transactions on intelligent transportation systems, vol. 3, no. 1, pp. 3-11, 2002. [OpenAIRE]

[10] A. Vela, S. Solak, W. Singhose, and J.-P. Clarke, “A mixed integer program for flight-level assignment and speed control for conflict resolution,” in Decision and Control, 2009 held jointly with the 2009 28th Chinese Control Conference. CDC/CCC 2009. Proceedings of the 48th IEEE Conference on, Dec 2009, pp. 5219-5226.

[11] D. Rey, C. Rapine, R. Fondacci, and N.-E. El Faouzi, “Subliminal speed control in air traffic management: Optimization and simulation,” Transportation Science, vol. 50, no. 1, pp. 240-262, 2015.

[12] J. Omer, “A space-discretized mixed-integer linear model for airconflict resolution with speed and heading maneuvers,” Computers & Operations Research, vol. 58, pp. 75-86, 2015. [OpenAIRE]

[13] A. Alonso-Ayuso, L. Escudero, and F. Mart´ın-Campo, “Collision avoidance in air traffic management: A mixed-integer linear optimization approach,” Intelligent Transportation Systems, IEEE Transactions on, vol. 12, no. 1, pp. 47-57, March 2011.

[14] A. Alonso-Ayuso, L. F. Escudero, and F. J. Mart´ın-Campo, “Exact and approximate solving of the aircraft collision resolution problem via turn changes,” Transportation Science, vol. 50, no. 1, pp. 263-274, 2014.

[15] --, “An exact multi-objective mixed integer nonlinear optimization approach for aircraft conflict resolution,” TOP, vol. 24, no. 2, pp. 381- 408, 2016.

31 references, page 1 of 3
Abstract
We present a novel complex number formulation along with tight convex relaxations for the aircraft conflict resolution problem. Our approach combines both speed and heading control and provides global optimality guarantees despite non-convexities in the feasible region. As a side result, we present a new characterization of the conflict separation condition in the form of disjunctive linear constraints. Our formulation features one binary variable per pair of aircraft, is free of trigonometric functions, and captures the non-convexity in a set of quadratic concave constraints. Using our approach, we are able to close a number of open instances and reduce computa...
Subjects
free text keywords: Computer Science - Computational Engineering, Finance, and Science, Order of magnitude, Mathematical optimization, Feasible region, Complex number, Atmospheric model, Trajectory, Global optimality, Computer science, Regular polygon, Conflict resolution
31 references, page 1 of 3

[1] Eurocontrol, “Performance review report,” Eurocontrol, 96, rue de la Fuse, B-1130 Brussels, Belgium, Tech. Rep., 2011. [Online]. Available: https://www.eurocontrol.int/sites/default/files/ publication/files/prr-2011.pdf

[2] European Comission and Eurocontrol, “European air traffic management master plan,” SESAR, Tech. Rep., 2009.

[3] Federal Aviation Administration, “FAA's NextGen Implementation Plan,” FAA, Tech. Rep., 2011.

[4] M. Nolan, Fundamentals of Air Traffic Control. Cengage Learning, 2010.

[5] ICAO, “Rules of the air and air traffic services,” International Civil Aviation Organization, Tech. Rep., 1996.

[6] P. Averty, “Conflict perception by atcs admits doubt but not inconsistency,” in 6th USA/Europe Air Traffic Management Research and Development Seminar, Baltimore, USA, 2005.

[7] J. K. Kuchar and L. C. Yang, “A review of conflict detection and resolution modeling methods,” Intelligent Transportation Systems, IEEE Transactions on, vol. 1, no. 4, pp. 179-189, 2000.

[8] A. Richards and J. P. How, “Aircraft trajectory planning with collision avoidance using mixed integer linear programming,” in American Control Conference, 2002. Proceedings of the 2002, vol. 3. IEEE, 2002, pp. 1936-1941.

[9] L. Pallottino, E. M. Feron, and A. Bicchi, “Conflict resolution problems for air traffic management systems solved with mixed integer programming,” IEEE transactions on intelligent transportation systems, vol. 3, no. 1, pp. 3-11, 2002. [OpenAIRE]

[10] A. Vela, S. Solak, W. Singhose, and J.-P. Clarke, “A mixed integer program for flight-level assignment and speed control for conflict resolution,” in Decision and Control, 2009 held jointly with the 2009 28th Chinese Control Conference. CDC/CCC 2009. Proceedings of the 48th IEEE Conference on, Dec 2009, pp. 5219-5226.

[11] D. Rey, C. Rapine, R. Fondacci, and N.-E. El Faouzi, “Subliminal speed control in air traffic management: Optimization and simulation,” Transportation Science, vol. 50, no. 1, pp. 240-262, 2015.

[12] J. Omer, “A space-discretized mixed-integer linear model for airconflict resolution with speed and heading maneuvers,” Computers & Operations Research, vol. 58, pp. 75-86, 2015. [OpenAIRE]

[13] A. Alonso-Ayuso, L. Escudero, and F. Mart´ın-Campo, “Collision avoidance in air traffic management: A mixed-integer linear optimization approach,” Intelligent Transportation Systems, IEEE Transactions on, vol. 12, no. 1, pp. 47-57, March 2011.

[14] A. Alonso-Ayuso, L. F. Escudero, and F. J. Mart´ın-Campo, “Exact and approximate solving of the aircraft collision resolution problem via turn changes,” Transportation Science, vol. 50, no. 1, pp. 263-274, 2014.

[15] --, “An exact multi-objective mixed integer nonlinear optimization approach for aircraft conflict resolution,” TOP, vol. 24, no. 2, pp. 381- 408, 2016.

31 references, page 1 of 3
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue
publication . Preprint . Conference object . 2017

Complex Number Formulation and Convex Relaxations for Aircraft Conflict Resolution

David Rey; Hassan Hijazi;