基于协同进化遗传算法的航班进港优化调度  

Optimal Scheduling of Aircraft Arrivals Based on Co-evolutionary Genetic Algorithm

作　　者：张勰[1] 赵嶷飞[1] 刘宏志[1] 

机构地区：[1]中国民航大学天津市空管运行规划与安全技术重点实验室,天津300300

出　　处：《交通运输系统工程与信息》2014年第2期94-101,共8页Journal of Transportation Systems Engineering and Information Technology

基　　金：国家自然科学基金(61039001);国家科技支撑计划(2011BAH24B10);中国民航大学科研基金(2011kyE04);中国民航大学科研启动基金(2012QD04X)

摘　　要：航班进港调度问题是一个典型的组合优化问题,具有多约束复杂特性.针对遗传算法求解航班进港调度问题时多约束难以处理、运算量大、易陷入局部最优的不足,本文应用协同进化思想,构建航班进港调度问题决策解种群和惩罚因子种群,通过种群间的竞争、协作改善算法性能;设计一种带约束处理的编码策略,将安全间隔约束纳入编码过程,降低了问题的约束复杂度,进而提出一种改进的协同进化遗传算法(Co-evolutionary Genetic Algorithm,CoGA),并应用首都机场的实际运行数据进行了仿真.结果表明,本文方法能够有效处理航班进港调度问题中的大量约束,在优化效果与GA算法相当的情况下,有效降低了计算时间,克服了问题规模剧增导致的计算效率低下的难题.Optimal scheduling of aircraft arrivals is a typical combinatorial optimization problem,which features complexity with multi-constraint.In order that the deficiencies can be overcome,which are multiconstraint,huge amount of computation and local optimum attraction,when the scheduling of aircraft arrivals is constituted with generic algorithms,a decision solutions population and a penalty factor population are constructed for the optimal scheduling problem,which is inspired by coevolution.The performance of the algorithm is improved by the competition and the coordination between the two populations.A coding strategy with constraints is designed,into which the safe separation constraint is coded,and the complexity of constraints is lowered with the coding strategy.Furthermore,an improved co-evolutionary genetic algorithm is proposed,and a simulation is conducted with the operational data from Beijing Capital Intemational Airport.It is shown that the huge amount of constraints for the optimal scheduling can be tackled effectively with the approach proposed.When the optimal result corresponds to the result of original genetic algorithm,the time cost is reduced effectively and the difficulty is overcome,that the computation efficiency decreases sharply as the scale of the problem increases.

关 键 词：航空运输 协同进化 遗传算法 航班进港调度 空中交通流量管理 

分 类 号：V355.2[航空宇航科学与技术—人机与环境工程]