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

作　　者：Renli LU Xiangmin GUAN Xueyuan LI Inseok HWANG 

机构地区：[1]Department of General Aviation, Civil Aviation Management Institute of China, Beijing 100102, China [2]School of Electronic and Information Engineering, Beihang University, Beijing 100191, China [3]School of Aeronautics and Astronautics, Purdue University, West Lafayette, IN 47907-2023, USA

出　　处：《Science China(Information Sciences)》2016年第7期181-197,共17页中国科学（信息科学）（英文版）

基　　金：supported by National Natural Science Foundation of China (Grant No. U1433203);Foundation for Innovative Research Groups of the National Natural Science Foundation of China (Grant No. 61221061)

摘　　要：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 optimiza- tion 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 evo- lution 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.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 optimiza- tion 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 evo- lution 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.

关 键 词：air traffic flow management flight assignment multi-island parallel evolution algorithm migration topology cooperative co-evolution 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] V556.5[自动化与计算机技术—计算机科学与技术]