SCIENCE CHINA Information Sciences, Volume 60, Issue 11: 112202(2017) https://doi.org/10.1007/s11432-016-9024-y

A large-scale multi-objective flights conflict avoidance approach supporting 4D trajectory operation

More info
  • ReceivedOct 16, 2016
  • AcceptedJan 20, 2017
  • PublishedSep 1, 2017


Recently, the long-term conflict avoidance approaches based on large-scale flights scheduling have attracted much attention due to their ability to provide solutions from a global point of view. However, current approaches which focus only on a single objective with the aim of minimizing the total delay and the number of conflicts, cannot provide controllers with variety of optional solutions, representing different tradeoffs. Furthermore, the flight track error is often overlooked in the current research. Therefore, in order to make the model more realistic, in this paper, we formulate the long-term conflict avoidance problem as a multi-objective optimization problem, which minimizes the total delay and reduces the number of conflicts simultaneously. As a complex air route network needs to accommodate thousands of flights, the problem is a large-scale combinatorial optimization problem with tightly coupled variables, which make the problem difficult to deal with. Hence, in order to further improve the search capability of the solution algorithm, a cooperative co-evolution (CC) algorithm is also introduced to divide the complex problem into several low dimensional sub-problems which are easier to solve. Moreover, a dynamic grouping strategy based on the conflict detection is proposed to improve the optimization efficiency and to avoid premature convergence. The well-known multi-objective evolutionary algorithm based on decomposition (MOEA/D) is then employed to tackle each sub-problem. Computational results using real traffic data from the Chinese air route network demonstrate that the proposed approach obtained better non-dominated solutions in a more effective manner than the existing approaches, including the multi-objective genetic algorithm (MOGA), NSGAII, and MOEA/D. The results also show that our approach provided satisfactory solutions for controllers from a practical point of view.


[1] Liu W, Hwang I. Probabilistic Trajectory Prediction and Conflict Detection for Air Traffic Control. J Guidance Control Dyn, 2011, 34: 1779-1789 CrossRef ADS Google Scholar

[2] Lü R, Guan X, Li X. A large-scale flight multi-objective assignment approach based on multi-island parallel evolution algorithm with cooperative coevolutionary. Sci China Inf Sci, 2016, 59: 072201 CrossRef Google Scholar

[3] Guan X M, Zhang X J, Han D, et al. A strategic flight conflict avoidance approach based on memetic algorithm. Chinese J Aeron, 2013, 27: 93--101. Google Scholar

[4] Kuchar J K, Yang L C. A review of conflict detection and resolution modeling methods. IEEE Trans Intell Transport Syst, 2000, 1: 179-189 CrossRef Google Scholar

[5] Hwang I, Tomlin C. Protocol-based conflict resolution for finite information horizon. In: Proceedings of American Control Conference, Anchorage, 2002. 748--753. Google Scholar

[6] Archibald K, Hill J C, Jepsen N A, et al. A satisficing approach to aircraft conflict resolution. IEEE Trans Syst, Man, Cybern C, 2008, 38: 510--521. Google Scholar

[7] Tomlin C, Mitchell I, Ghosh R. Safety verification of conflict resolution manoeuvres. IEEE Trans Intell Transport Syst, 2001, 2: 110-120 CrossRef Google Scholar

[8] Kosecka K, Tomlin C, Pappas G, et al. Generation of conflict resolution maneuvers for air traffic management. In: Proceedings of International Conference on Intelligent Robots and Systems, Grenoble, 1997. 1598--1603. Google Scholar

[9] Zhi-Hong Mao , Dugail D, Feron E. Space partition for conflict resolution of intersecting flows of mobile agents. IEEE Trans Intell Transport Syst, 2007, 8: 512-527 CrossRef Google Scholar

[10] Pallottino L, Feron E M, Bicchi A. Conflict resolution problems for air traffic management systems solved with mixed integer programming. IEEE Trans Intell Transp Syst, 2003, 3: 3--11. Google Scholar

[11] Mondoloni S, Conway S. An Airborne Conflict Resolution Approach Using a Genetic Algorithm. NASA Langley Technical Report, AIAA-2001-4054. 2001. Google Scholar

[12] Vivona R, Karr D, Roscoe D. Pattern based genetic algorithm for airborne conflict resolution. In: Proceedings of AIAA Guidance, Navigation, and Control Conference and Exhibit, Keystone, 2006. AIAA-2006-6060. Google Scholar

[13] Pechoucek M, Sislak D. Agent-based approach to free-flight planning, control, and simulation. IEEE Intell Syst, 2009, 24: 14--17. Google Scholar

[14] Hill J C, Johnson F R, Archibald J K, et al. A cooperative multi-agent approach to free flight. In: Proceedings of the 4th International Joint Conference on Autonomous Agents and Multiagent Systems, Utrecht, 2005. 1083--1090. Google Scholar

[15] Rong J, Geng S, Valasek J, et al. Air traffic control nego-tiation and resolution using an on board multi-aircraft system. In: Proceedings of the 21st Digital Avionics System Conference, Irvine, 2002. 69--80. Google Scholar

[16] Durand N, Allignol, C. 4D-Trajectory deconfliction through departure time adjustment. In: Proceedings of Conference on International Air Traffic Management R&D Seminar, Napa, 2009. 1--10. Google Scholar

[17] Durand N, Alliot J M, Noailles J. Automatic aircraft conflict resolution using genetic algorithms. In: Proceedings of the 1996 ACM symposium on Applied ComputingSymposium on Applied Computing, Pennsylvania, 1996. 289--298. Google Scholar

[18] Su J, Zhang X J, Guan X M. 4D-Trajectory conflict resolution using cooperative coevolution. In: Proceedings of International Conference on Information Technology and Software Engineering, Beijing, 2012. 387--395. Google Scholar

[19] Yang Z, Tang K, Yao X. Large scale evolutionary optimization using cooperative coevolution. Inf Sci, 2008, 178: 2985-2999 CrossRef Google Scholar

[20] Ray T, Yao X. A cooperative coevolutionary algorithm with correlation based adaptive variable partitioning. In: Proceedings of the 11th Congress on Evolutionary Computation, Montreal, 2009. 983--989. Google Scholar

[21] Omidvar M N, Li X D, Yao X. Cooperative coevolution with delta grouping for large scale non-separable function optimization. In: Proceedings of the IEEE Congress on Evolutionary Computation, Barcelona, 2010. 1762--1769. Google Scholar

[22] Sayed E, Essam D, Sarker R A. Dependency identification tech-nique for large scale optimization problems. In: Proceedings of the IEEE Congress on Evolutionary Computation, Brisbane, 2012. 1--8. Google Scholar

[23] Potter M, Jong K D. A cooperative coevolutionary approach to function optimization. In: Proceedings of the 3rd Conference on Parallel Problem Solving from Nature, London, 1994. 249--257. Google Scholar

[24] Qingfu Zhang , Hui Li . MOEA/D: A multi-objective evolutionary algo-rithm based on decomposition. IEEE Trans Evol Computat, 2007, 11: 712-731 CrossRef Google Scholar

[25] Delahaye D, Sofiane O, Puechmorel S. Airspace congestion smoothing by multi-objective genetic algorithm. In: Proceedings of ACM Symposium on Applied Computing, Santa Fe, 2005. 907--912. Google Scholar

[26] Deb K, Pratap A, Agarwal S. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Computat, 2002, 6: 182-197 CrossRef Google Scholar

[27] Prandini M, Hu J, Lygeros J. A probabilistic approach to aircraft conflict detection. IEEE Trans Intell Transport Syst, 2000, 1: 199-220 CrossRef Google Scholar

[28] Zhang X J, Guan X M, Hwang I, et al. A hybrid distributed-centralized conflict resolution approach for multi-aircraft based on cooperative co-evolutionary. Sci China Inf Sci, 2013, 56: 128202. Google Scholar

[29] Zitzler E, Thiele L, Laumanns M. Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans Evol Computat, 2003, 7: 117-132 CrossRef Google Scholar

[30] Fleischer M. The measure of Pareto optima: applications to multiobjective metaheuristics. In: Proceeding of the 2nd International Conference on Evolutionary Multi-objective Optimization, Faro, 2003. 519--533. Google Scholar

[31] Wilcoxon F. Individual Comparisons by Ranking Methods. Biometrics Bull, 1945, 1: 80-83 CrossRef Google Scholar

[32] Delahaye D, Sofiane O, Puechmorel S. Airspace congestion smoothing by multi-objective genetic algorithm. In: Proceedings of ACM Symposium on Applied Computing, Santa Fe, 2005. 907--912. Google Scholar

[33] Deb K, Pratap A, Agarwal S. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Computat, 2002, 6: 182-197 CrossRef Google Scholar

  • Figure 1

    Adaptive crossover operator.

  • Figure 2

    Adaptive mutate operator.

  • Figure 3

    (Color online) (a) The relationship between the number of flights and the conflict situation in every two hours; (b) the relationship between the number of flights and the conflict situation as the considered time accumulates.

  • Figure 4

    (Color online) Adaptive mutate operator.


    Algorithm 1 The framework of the proposed method

    Initialize the population $g=0$.

    //Main loop:

    while $g$ ( < ) maxgen do

    Evaluate all individuals in the population.

    Compute the non-dominated solutions.

    //cooperative co-evolution.

    Divide the decision variables into groups based on the dynamic grouping strategy.

    Decision variables in each group generate its subpopulation.

    for each subpopulation

    Use the MOEA/D framework with a genetic algorithm.

    Evaluate all individuals in the subpopulation, and compute the non-dominated solutions.

    end for

    Obtain the non-dominated solutions.

    (g = g + 1.)

    end while


    Algorithm 2 Algorithmic flow of MOEA/D with GA


    (1) A stopping criterion;

    (2) $np$: the number of the sub-problems;

    (3) An uniform spread of n weight vectors: ${\lambda~^1},~\ldots,~{\lambda~^{np}}$;

    (4) $T$: the number of the weight vectors in the neighborhood of each weight vector;

    Output:Approximation to the PF and PS.


    Step 1 Initialization:

    Step 1.1 Compute the Euclidean distances between the weight vectors and work out the $T$ closest weight vectors to each weight vector. For each (i = 1, …, np), set (B(i) = i_1 …, i_T ), where (λ ^i_1 …, λ ^i_T) are the $T$ closest weight vectors to (λ ^i).

    Step 1.2 Generate an initial population (x¹ …, x^np). Calculate the fitness values of the population.

    Step 1.3 Initialize (z = (z_1 …, z_m), where (z_j =

    min _1 łe i łe nf_jx^i).

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有