SCIENCE CHINA Information Sciences, Volume 59, Issue 7: 072201(2016) https://doi.org/10.1007/s11432-015-5495-3

A large-scale flight multi-objective assignment approach based on multi-island parallel evolution algorithm with cooperative coevolutionary

More info
  • ReceivedMay 23, 2015
  • AcceptedSep 30, 2015
  • PublishedMay 26, 2016


Due to the rapid increase of air traffic demand, the large-scale flight assignment plays a crucial role in reducing airspace congestion and economic losses via reasonably regulating the air traffic flow of China. In this paper, the large-scale flight assignment problem is formulated as a multi-objective model with consideration of the reduction of airspace congestion and flight delay. However, it is a large-scale combinatorial optimization problem with complex constraints and tightly coupled decision variables, which is difficult to deal with. Hence, an effective multi-objective optimization algorithm is proposed based on the multi-island parallel evolution framework (PEA) with a left-right probability migration topology. Multi-island PEA employs multiple evolution populations for solving the problem simultaneously, and the left-right probability migration topology for exchange individuals among populations to improve the efficiency of the cooperation of populations. Then the cooperative co-evolution (CC) algorithm is introduced for each population to further improve the searching capability. Simulation results using the real traffic data from the China air route network and daily flight plans demonstrate that the proposed approach can improve the solution quality effectively, showing superiority to the existing approaches such as the multi-objective genetic algorithm, the well-known multi-objective evolutionary algorithm based on decomposition, a CC-based multi-objective algorithm as well as other two parallel evolution algorithms with different migration topologies.

Funded by

National Natural Science Foundation of China(U1433203)

Foundation for Innovative Research Groups of the National Natural Science Foundation of China(61221061)



This work was supported by National Natural Science Foundation of China (Grant No. U1433203), and Foundation for Innovative Research Groups of the National Natural Science Foundation of China (Grant No. 61221061).


[1] Liu W, Hwang I. Probabilistic trajectory prediction and conflict detection for air traffic control. AIAA J Guid Control Dynam, 2011, 34: 1779-1789 CrossRef Google Scholar

[2] Alam S, Lokan C, Abbass H A. What can make an airspace un-safe? characterizing collision risk using multi-objective optimi-zation. In: Proceedings of IEEE Congress on Evolutionary Computation, Brisbane, 2012. 1--8. Google Scholar

[3] Tang M D, Zhang G Q, Sun Yi, et al. Integrating local and partial network view for routing on scale-free networks. Sci China Inf Sci, 2013, 56: 102311-1789 Google Scholar

[4] Oussedik S, Delahaye D. Reduction of air traffic congestion by genetic algorithms. In: Parallel Problem Solving from Nature --- PPSN V. Berlin: Springer, 1998. 855--864. Google Scholar

[5] Wei P, Cao Y, Sun D. Total unimodularity and decomposition method for large-scale air traffic cell transmission model. Transport Res Part B, 2013, 53: 1-16 Google Scholar

[6] Ball M, Lulli G. Ground delay programs: optimizing over in-cluded flight set based on distance. Air Traffic Control Quarter, 2004, 12: 1-25 Google Scholar

[7] Bayen A, Raffard R, Tomlin C. Adjoint-based control of a new Eulerian network model of air traffic flow. IEEE Trans Control Syst Tech, 2006, 14: 804-818 CrossRef Google Scholar

[8] Bertsimas D, Patterson S. The air traffic flow management problem with enroute capacities. Oper Res, 1998, 46: 406-422 CrossRef Google Scholar

[9] Delahaye D, Odoni A. Airspace congestion smoothing by sto-chastic optimization. In: Evolutionary Programming VI. Berlin: Springer, 1997. 163--176. Google Scholar

[10] Abad A M, Clarke J B. Using tactical flight level allocation to alleviate airspace corridor congestion. In: Proceedings of AIAA 4th Aviation Technology, Integration and Operations (ATIO) Forum, Chicago, 2004. 1--9. Google Scholar

[11] Vossen T, Michael B. Optimization and mediated bartering models for ground delay programs. Nav Res Log, 2006, 53: 75-90 CrossRef Google Scholar

[12] Bertsimas D, Lulli G, Odoni A. An integer optimization approach to large-scale air traffic flow management. Oper Res, 2011, 59: 211-227 CrossRef Google Scholar

[13] Liu H X, Zhu Y B, Cai K Q, et al. Route network flow assignment in the new generation of aviation by cooperative coevolution. In: Proceedings of IEEE 5th International Conference on Cybernetics and Intelligent Systems (CIS), Qingdao, 2011. 175--180. Google Scholar

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

[15] Tian W, Hu M. Study of air traffic flow management optimization model and algorithm based on multi-objective programming. In: Proceedings of International Conference on Computer Modeling and Simulation, Sanya, 2010. 210--214. Google Scholar

[16] Tang J, Lim M H, Ong Y S. Diversity-adaptive parallel memetic algorithm for solving large scale combinatorial optimization problems. Soft Comput J, 2007, 11: 873-888 CrossRef Google Scholar

[17] Tang J, Lim M H, Ong Y S, et al. Study of migration topology in island model parallel hybrid-GA for large scale quadratic as-signment problems. In: Proceedings of the 8th International Conference on Control, Automation, Robotics and Vision, Kunming, 2004. 3: 2286--2291. Google Scholar

[18] 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-888 Google Scholar

[19] Chen Z, Zhang S, Yang L, et al. Optimal phase searching of PTS using modified genetic algorithm for PAPR reduction in OFDM systems. Sci China Inf Sci, 2014, 57: 062305-888 Google Scholar

[20] Tang J, Lim M H, Ong Y S. Parallel memetic algorithm with selective local search for large Scale quadratic assignment. J Innov Comput Inf Control, 2006, 2: 1399-1416 Google Scholar

[21] Cantu-Paz E. A survey of parallel genetic algorithms. Calculateurs Parall Reseaux et Syst Repartis, 1998, 10: 141-171 Google Scholar

[22] Yang Z, Tang K, Yao X. Large scale evolutionary optimization using cooperative coevolution. Inf Sci, 2008, 178: 2985-2999 CrossRef 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, Jerusalem, 1994. 249--257. Google Scholar

[24] Zhu F M, Guan S U. Cooperative co-evolution of GA-based classifiers based on input decomposition. Eng Appl Artif Intell, 2008, 21: 887-896 Google Scholar

[25] Zhang Q, Li H. MOEA/D: a multi-objective evolutionary algorithm based on decomposition. IEEE Trans Evol Comput, 2007, 11: 712-731 CrossRef Google Scholar

[26] Liu B, Fernandez F V, Zhang Q, et al. An enhanced MOEA/D-DE and its application to multiobjective analog cell sizing. In: Proceedings of IEEE Congress on Evolutionary Computation (CEC), Barcelona, 2010. 1--7. Google Scholar

[27] Miettinen K. Nonlinear Multiobjective Optimization. New York: Springer, 1999. Google Scholar

[28] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evolut Comput, 2002, 6: 182-197 CrossRef Google Scholar

[29] Zitzler E, Thiele L, Laumanns M. Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans Evolut Comput, 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-criterion Optimization. Berlin: Springer, 2003. 519--533. Google Scholar

[31] Wilcoxon F. Individual comparisons by ranking methods. Bio-metrics Bull, 1945, 1: 80-83 Google Scholar

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