Flight Conflict Resolution and Trajectory Recovery Through Mixed Integer Nonlinear Programming Based on Speed and Heading Angle Change

Abstract

A scheme for conflict resolution with trajectory recovery is proposed to solve the problem of multi-aircraft flight conflict. First, the conflict resolution problem is modeled as an optimal control problem. The weighted sum of the speed change and the heading angle change is defined as the objective function. The limitations of distance, aircraft performance, and route width are taken as constraints. Second, the optimization problem is resolved by mixed integer nonlinear programming. Conflict resolution with trajectory recovery is then achieved by speed and heading angle changing three times based on the optimal solution; whether the speed and heading angle need to be changed depends on the corresponding weight coefficients in the objective function. Finally, the applicability and superiority of the designed conflict resolution scheme are verified, which is of great significance to the application of conflict resolution with trajectory recovery schemes in automated air traffic control systems.

Keywords

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

Get full access to this article

View all access options for this article.

References

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

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

Kuchar

J. K.

Yang

L. C.

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

Sun

Yong Tian Ye

A Review of Research on Flight Conflict Detection and Resolution Methods. Aeronautical Computing Technology, Vol. 49, No. 5, 2019, pp. 125–128.

Wei

Pan

Summary of Research on Flight Conflict Resolution Methods. Journal of China Civil Aviation Flight Academy, Vol. 33, No. 6, 2021, pp. 5–9.

Cecen

R. K.

Cetek

Conflict-Free En-Route Operations with Horizontal Resolution Manoeuvers Using a Heuristic Algorithm. The Aeronautical Journal, Vol. 124, No. 1275, 2020, pp. 767–785.

Medioni

Durand

Alliot

J.-M.

Air Traffic Conflict Resolution by Genetic Algorithms. Proc., Artificial Evolution: European Conference, Brest, France. Springer, Berlin, 1995, pp. 370–383.

Conway

Mondoloni

An Airborne Conflict Resolution Approach Using a Genetic Algorithm. Proc., AIAA Guidance, Navigation and Control Conference and Exhibit, Montreal, Canada. American Institute of Aeronautics and Astronautics, Reston, VA, 2001, pp. 2001–4054.

Yang

Dai

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

10.

Ramzan

Khan

M. Q.

Iqbal

M. A.

Aasem

Jaffar

Anwar

Adnan

Tamleek

Ali

Alam

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

11.

Shu

Liang

Kui

Research on Algorithm of Conflict Detection and Resolution in Free Flight Based on Genetic Algorithms. Proc., International Workshop on Education Technology and Computer Science, Wuhan, China. IEEE, New York, 2009, pp. 1134–1136.

12.

Hao

Cheng

Zhang

A Multi-Aircraft Conflict Detection and Resolution Method for 4-Dimensional Trajectory-based Operation. Chinese Journal of Aeronautics, Vol. 31, No. 7, 2018, pp. 1579–1593.

13.

Ramamoorthy

K. A.

Singh

Crassidis

J. L.

Potential Functions for En-Route Air Traffic Management and Flight Planning. Proc., AIAA Guidance, Navigation, and Control Conference and Exhibit, Providence, RI. American Institute of Aeronautics and Astronautics, Reston, VA, 2004, p. 4878.

14.

Yang

Naeem

Fei

A Cooperative Formation-Based Collision Avoidance Approach for A Group of Autonomous Vehicles. International Journal of Adaptive Control and Signal Processing, Vol. 31, No. 4, 2017, pp. 489–506.

15.

Zhang

Shao

X. Y.

Zhou

Gao

Research on Conflict Resolution Method Based on Particle Swarm Optimization in Collaborative Design. Proc., World Congress on Intelligent Control and Automation, Dalian, China. IEEE, New York, 2006, pp. 3451–3455.

16.

Emami

Derakhshan

Multi-Agent Based Solution for Free Flight Conflict Detection and Resolution Using Particle Swarm Optimization Algorithm. UPB Scientific Bulletin, Series C: Electrical Engineering, Vol. 76, 2014, pp. 49–64.

17.

Zhen

Zhang

Study of the Aircraft Conflict Resolution Method Based on Modified Particle Swarm Optimization. Journal of Hebei University of Science and Technology, Vol. 36, 2016, pp. 491–496.

18.

Hong

Choi

Lee

Kim

Nonlinear Conflict Resolution and Flow Management Using Particle Swarm Optimization. IEEE Transactions on Intelligent Transportation Systems, Vol. 18, No. 12, 2017, pp. 3378–3387.

19.

Durand

Alliot

J.-M.

Ant Colony Optimization for Air Traffic Conflict Resolution. Journal of Intelligent & Robotic Systems, 2009, pp. 1–6.

20.

Chen

M. Q.

Flight Conflict Detection and Resolution Based on Neural Network. Proc., International Conference on Computational and Information Sciences, Chengdu, China. IEEE, New York, 2011, pp. 860–862.

21.

Kaidi

Lazaar

Ettaouil

Neural Network Apply to Predict Aircraft Trajectory for Conflict Resolution. Proc., International Conference on Intelligent Systems: Theories and Applications, Rabat, Morocco. IEEE, New York, 2014, pp. 1–6.

22.

Casado

Bermúdez

Neural Network-Based Aircraft Conflict Prediction in Final Approach Maneuvers. Electronics, Vol. 9, No. 10, 2020, p. 1708.

23.

Yang

Wen

Conflict Resolution Strategy Based on Flight Conflict Network Optimal Dominating Set. International Journal of Aerospace Engineering, Vol. 2022, 2022, pp. 1–9.

24.

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.

25.

Piera

M. A.

Radanovic

Leal

Multi-Agent Systems for Air Traffic Conflicts Resolution by Using a Causal Analysis of Spatio-Temporal Interdependencies. Proc., SummerSim, Montreal, Canada. Society for Computer Simulation International, San Diego, CA, 2016, p. 29.

26.

Pelegrin

D’Ambrosio

Aircraft Deconfliction via Mathematical Programming: Reviem and Insights. Transportation Science, Vol. 56, No. 1, 2022, pp. 118–140.

27.

Pallottino

Feron

E. M.

Bicchi

Conflict Resolution Problems for Air Traffic Management Systems Solved with Mixed Integer Programming. IEEE Transactions on Intelligent Transportation Systems, Vol. 3, No. 1, 2002, pp. 3–11.

28.

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.

29.

Cafieri

Durand

Aircraft Deconfliction with Speed Regulation: New Models from Mixed-Integer Optimization. Journal of Global Optimization, Vol. 58, 2014, pp. 613–629.

30.

Omer

A Space-Discretized Mixed-Integer Linear Model for Air-Conflict Resolution with Speed and Heading Maneuvers. Computers and Operations Research, Vol. 58, 2015, pp. 75–86.

31.

Alonso-Ayuso

Escudero

L. F.

Martín-Campo

F. J.

An Exact Multi-Objective Mixed Integer Nonlinear Optimization Approach for Aircraft Conflict Resolution. Top, Vol. 24, No. 2, 2015, pp. 381–408.

32.

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.

33.

Cafieri

Omheni

Mixed-Integer Nonlinear Programming for Aircraft Conflict Avoidance by Sequentially Applying Velocity and Heading Angle Changes. European Journal of Operational Research, Vol. 260, No. 1, 2017, pp. 283–290.

34.

Lehouillier

Omer

Soumis

Desaulniers

Two Decomposition Algorithms for Solving a Minimum Weight Maximum Clique Model for the Air Conflict Resolution Problem. European Journal of Operational Research, Vol. 256, No. 3, 2017, pp. 696–712.

35.

Cafieri

Rey

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

36.

Lehouillier

Nasri

M. I.

Soumis

Desaulniers

Omer

Solving the Air Conflict Resolution Problem Under Uncertainty Using an Iterative Biobjective Mixed Integer Programming Approach. Transportation Science, Vol. 51, No. 4, 2017, pp. 1242–1258.

37.

Rey

Hijazi

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

38.

Cafieri

D’Ambrosio

Feasibility Pump for Aircraft Deconfliction with Speed Regulation. Journal of Global Optimization, Vol. 71, No. 3, 2017, pp. 501–515.

39.

Jin

Han

Nonlinear Programming for Conflict Resolution in Free Flight. Proc., National Youth Academic Conference in the Field of Transportation, On line, Chang Sha, 2003, pp. 187–193.

40.

Dias

F. H. C.

Hijazi

Rey

Disjunctive Linear Separation Conditions and Mixed-Integer Formulations for Aircraft Conflict Resolution. European Journal of Operational Research, Vol. 296, No. 2, 2022, pp. 520–538.

41.

Pei

Qingsheng

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

42.

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.

43.

Zhou

Rahmani

Liu

Wang

Application of Distributed MAS in Flight Conflict Avoidance. Journal of Transportation Systems Engineering and Information Technology, Vol. 15, 2015, pp. 231–238.

44.

Soler

Kamgarpour

Lloret

Lygeros

A Hybrid Optimal Control Approach to Fuel-Efficient Aircraft Conflict Avoidance. IEEE Transactions on Intelligent Transportation Systems, Vol. 17, No. 7, 2016, pp. 1826–1838.

45.

Lovato

A. V.

Fontes

C. H.

Embiruçu

Kalid

A Hybrid Approach for Detecting and Resolving Conflicts in Air Traffic Routes. IEEE Access, Vol. 7, 2019, pp. 169865–169887.

46.

Pappas

G. J.

Tomlin

Sastry

S. S.

Conflict Resolution for Multi-Agent Hybrid System. Proc., Conference on Decision and Control, Kobe, Japan, Vol. 2, IEEE, New York, 1996, pp. 1184–1189.

47.

Yang

Zhang

Perc

A Satisficing Conflict Resolution Approach for Multiple UAVs. IEEE Internet of Things Journal, Vol. 6, No. 2, 2019, pp. 1866–1878.

48.

Liu

Xiao

Multi-Aircraft Flight Conflict Resolution and Trajectory Recovery Scheme Based on MILP and Geometric Rules. Transportation Research Record: Journal of the Transportation Research Board, 2022. 2677: 166–182.

49.

Richards

How

J. P.

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

50.

Alonso-Ayuso

Escudero

L. F.

Martín-Campo

F. J.

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

51.

Cai

Zhang

Research on Aircraft Conflict Resolution Based on MINLP Model. Journal of Chongqing University of Technology, Vol. 34, No. 2, 2020, pp. 188–195.

52.

Yang

Yin

Cheng

Shen

Two-Layered Mechanism of Online Unmanned Aerial Vehicles Conflict Detection and Resolution. IEEE Transactions on Intelligent Transportation Systems, Vol. 19, No. 10, 2018, pp. 3230–3244.