Multi-Aircraft Flight Conflict Resolution and Trajectory Recovery Scheme Based on Mixed Integer Linear Programming and Geometric Rules

Abstract

A conflict resolution and trajectory recovery scheme based on heading angle change (HAC) is proposed to solve mid-term conflict between multi-aircraft cruising in a shared airspace. Flight conflict resolution has always been regarded as one of the most important responsibilities of air traffic controllers (ATCOs). The proposed conflict resolution scheme can be applied to decision support tools to assist ATCOs in making decisions. The goals of reducing the possibility of human error and increasing the efficiency of airspace operations can be achieved. Firstly, the flight conflict problem is modeled as a class of optimal control problem. Secondly, the optimal solution can be obtained by mixed integer linear programming (MILP) method based on HAC strategy. Thirdly, a trajectory recovery method based on geometric rules is proposed. It can be found through simulated experiment that the extra flight distance and delay adopting the designed scheme is smaller than the compared method.

Keywords

aviation airfield and airspace capacity and delay air traffic control operations traffic simulation traffic management and control

Get full access to this article

View all access options for this article.

References

SESAR. SESAR Solutions Catalogue. SESAR. https://doi.org/10.2829/0404.

FAA. NextGen Implementation Plan. Federal Aviation Administration, Washington, D.C., 2018, pp. 1–83.

Kuchar

J. K.

Yang

L. C.

A Review of Conﬂict Detection and Resolution Modeling Methods. IEEE Transactions on Intelligent Transportation Systems, Vol. 1, No. 4, 2000, pp. 179–189.

Medioni

Durand

Alliot

J.-M.

Air Trafﬁc Conﬂict Resolution by Genetic Algorithms. European Conference on Artificial Evolution, Berlin, 1995, pp.370–383.

Mondoloni

Conway

An Airborne Conﬂict Resolution Approach Using a Genetic Algorithm. Proc., American Institute of Aeronautics and Astronautics Guidance, Navigation and Control Conference and Exhibit, Montreal, Canada, 2001.

Yang

Dai

Conﬂict Resolution in Free Flight Based on an Immune Genetic Algorithm. Aeronautical Computing Technique, Vol. 37, 2007, pp. 41–43.

Ramzan

Khan

M. Q.

Iqbal

M. A.

Aasem

Jaffar

Anwar

Adnan

Tamleek

Ali

Alam

A Genetic Algorithms Based Approach for Conﬂicts Resolution in Requirement. International Journal of the Physical Sciences, Vol. 6, 2011, pp. 828–836.

Shu

Liang

Kui

Research on Algorithm of Conﬂict Detection and Resolution in Free Flight Based on Genetic Algorithms. Proc., 1st International Workshop on Education Technology and Computer Science, Wuhan, China, 2009. https://doi.org/10.1109/etcs.2009.259.

Ramamoorthy

Singh

Crassidis

J. L.

Potential Functions for En-Route Air Trafﬁc Management and Flight Planning. Proc., AIAA Guidance, Navigation, and Control Conference and Exhibit, Providence, Rhode Island, 2004.

10.

Zhang

Shao

Zhou

Gao

Research on Conﬂict Resolution Method Based on Particle Swarm Optimization in Collaborative Design. Proc., 6th World Congress on Intelligent Control and Automation, Vol. 1, Dalian, IEEE, New York, 2006, pp. 3451–3455.

11.

Emami

Derakhshan

Multi-Agent Based Solution for Free ﬂight Conﬂict Detection and Resolution Using Particle Swarm Optimization Algorithm. UPB Scientiﬁc Bulletin, Series C: Electrical Engineering, Vol. 76, 2014, pp. 49–64.

12.

Zhen

Zhang

Study of the Aircraft Conﬂict Resolution Method Based on Modiﬁed Particle Swarm Optimization. Journal of Hebei University of Science and Technology, Vol. 36, No. 5, 2016, pp. 491–496.

13.

Durand

Alliot

J.-M.

Ant Colony Optimization for Air Trafﬁc Conﬂict Resolution. Proc., Europe Air Trafﬁc Management Research and Development Seminar, Napa, CA, 2009.

14.

Chen

M. Q.

Flight Conﬂict Detection and Resolution Based on Neural Network. Proc., International Conference on Computational and Information Sciences, Chengdu, China, IEEE, New York, 2011, pp. 860–862. https://doi.org/10.1109/iccis.2011.154.

15.

Kaidi

Lazaar

Ettaouil

Neural Network Apply to Predict Aircraft Trajectory for Conﬂict Resolution. Proc., 9th International Conference on Intelligent Systems: Theories and Applications (SITA-14), Rabat, Morocco, IEEE, New York, 2014, pp. 1–6.

16.

Casado

Bermúdez

Neural Network-Based Aircraft Conﬂict Prediction in Final Approach Maneuvers. Electronics, Vol. 9, No. 10, 2020, p. 1708. https://doi.org/10.3390/electronics9101708.

17.

Mateos

Jiménez-Martín

Multiobjective Simulated Annealing for Collision Avoidance in ATM Accounting for Three Admissible Maneuvers. Mathematical Problems in Engineering, Vol. 2016, 2016, pp. 1–16. https://doi.org/10.1155/2016/8738014.

18.

Piera

M. A.

Radanovic

Leal

Multi-Agent Systems for Air Trafﬁc Conﬂicts Resolution by Using a Causal Analysis of Spatio-Temporal Interdependencies. Proc., SummerSim, Montreal, Quebec, Canada, 2016, p. 29.

19.

Pei

Wang

. Application of Simulated Annealing Genetic Algorithm in Flight Conﬂict Resolution. Transportation and Computer, Vol. 23, 2004, pp. 115–117.

20.

Zhou

Rahmani

Liu

Wang

L.-L.

Application of Distributed MAS in Flight Conﬂict Avoidance. Journal of Transportation Systems Engineering and Information Technology, Vol. 15, 2015, pp. 231–238. https://doi.org/10.16097/j.cnki.1009-6744.2015.05.033.

21.

Soler

Kamgarpour

Lloret

Lygeros

A Hybrid Optimal Control Approach to Fuel-Efﬁcient Aircraft Conﬂict Avoidance. IEEE Transactions on Intelligent Transportation Systems, Vol. 17, No. 7, 2016, pp. 1826–1838. https://doi.org/10.1109/Tits.2015.2510824.

22.

Richards

How

J. P.

Aircraft Trajectory Planning With Collision Avoidance Using Mixed Integer Linear Programming. Proc., 3rd American Control Conference, Anchorage, AK, IEEE, New York, 2002, pp. 1936–1941.

23.

Alonso-Ayuso

Escudero

L. F.

Martín-Campo

F. J.

Collision Avoidance in Air Trafﬁc Management–A Mixed-Integer Linear Optimization Approach. IEEE Transactions on Intelligent Transportation Systems, Vol. 12, No. 1, 2011, pp. 47–57.

24.

Omer

A Space-Discretized Mixed-Integer Linear Model for Air-Conﬂict Resolution With Speed and Heading Maneuvers. Computers and Operations Research, Vol. 58, 2015, pp. 75–86. https://doi.org/10.1016/j.cor.2014.12.012.

25.

Alonso-Ayuso

Escudero

L. F.

Martín-Campo

F. J.

An Exact Multi-Objective Mixed Integer Nonlinear Optimization Approach for Aircraft Conﬂict Resolution. TOP, Vol. 24, No. 2, 2015, pp. 381–408. https://doi.org/10.1007/s11750-015-0402-z.

26.

Caﬁeri

Omheni

Mixed-Integer Nonlinear Programming for Aircraft Conﬂict Avoidance by Sequentially Applying Velocity and Heading Angle Changes. European Journal of Operational Research, Vol. 260, No. 1, 2017, pp. 283–290. https://doi.org/10.1016/j.ejor.2016.12.010.

27.

Lehouillier

Omer

Soumis

Desaulniers

Two Decomposition Algorithms for Solving a Minimum Weight Maximum Clique Model for the Air Conﬂict Resolution Problem. European Journal of Operational Research, Vol. 256, No. 3, 2017, pp. 696–712. https://doi.org/10.1016/j.ejor.2016.07.008.

28.

Caﬁeri

Rey

Maximizing the Number of Conﬂict-Free Aircraft Using Mixed-Integer Nonlinear Programming. Computers and Operations Research, Vol. 80, 2017, pp. 147–158.

29.

Pallottino

Feron

E. M.

Bicchi

Conﬂict Resolution Problems for Air Trafﬁc Management Systems Solved with Mixed Integer Programming. IEEE Transactions on Intelligent Transportation Systems, Vol. 3, No. 1, 2002, pp. 3–11.

30.

Alonso-Ayuso

Escudero

L. F.

Martín-Campo

F. J.

A Mixed 0–1 Nonlinear Optimization Model and Algorithmic Approach for the Collision Avoidance in ATM: Velocity Changes Through a Time Horizon. Computers and Operations Research, Vol. 39, No. 12, 2012, pp. 3136–3146. https://doi.org/10.1016/j.cor.2012.

31.

Lehouillier

Nasri

M. I.

Soumis

Desaulniers

Omer

Solving the Air Conﬂict Resolution Problem Under Uncertainty Using an Iterative Biobjective Mixed Integer Programming Approach. Transportation Science, Vol. 51, No. 4, 2017, pp. 1242–1258. https://doi.org/10.1287/trsc.2016.0714.

32.

Cafieri

Durand

Aircraft Deconﬂiction with Speed Regulation–New Models From Mixed-Integer Optimization. Journal of Global Optimization, Vol. 58, 2014, pp. 613–629.

33.

Alonso-Ayuso

Escudero

L. F.

Martín-Campo

F. J.

Exact and Approximate Solving of the Aircraft Collision Resolution Problem via Turn Changes. Transportation Science, Vol. 50, No. 1, 2016, pp. 263–274. https://doi.org/10.1287/trsc.2014.0557.

34.

Rey

Hijazi

Complex Number Formulation and Convex Relaxations for Aircraft Conﬂict Resolution. Proc., IEEE Annual Conference on Decision and Control, Melbourne, VIC, Australia, IEEE, New York, 2017, pp. 88–93.

35.

Caﬁeri

D’Ambrosio

Feasibility Pump for Aircraft Deconﬂiction with Speed Regulation. Journal of Global Optimization, Vol. 71, No. 3, 2017, pp. 501–515. https://doi.org/10.1007/s10898-017-0560-7.

36.

Pelegrín

D’Ambrosio

Aircraft Deconﬂiction via Mathematical Programming: Reviem and Insights. Transportation Science, Vol. 56, No. 1, 2021, pp. 118–140.

37.

Kuenz

Resolving Super-Conﬂicts Strategically. Proc., IEEE/AIAA 35th Digital Avionics Systems Conference (DASC), Sacramento, CA, IEEE, New York, 2016, pp. 1–9. https://doi.org/10.1109/DASC.2016.7777965.

38.

Omer

Farges

J.-L.

Hybridization of Nonlinear and Mixed-Integer Linear Programming for Aircraft Separation With Trajectory Recovery. IEEE Transactions on Intelligent Transportation Systems, Vol. 14, No. 3, 2013, pp. 1218–1230. https://doi.org/10.1109/tits.2013.2257758.

39.

Omer

Comparison of Mixed-Integer Linear Models for Fuel-Optimal Air Conﬂict Resolution With Recovery. IEEE Transactions on Intelligent Transportation Systems, Vol. 16, No. 6, 2015, pp. 3126–3137. https://doi.org/10.1109/tits.2015.2434942.

40.

Dias

F. H.

Rey

Aircraft Conﬂict Resolution with Trajectory Recovery Using Mixed-Integer Programming. arXiv Preprint arXiv:2203.11990, 2022. https://doi.org/10.48550/arXiv.2203.11990.