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

交通运输系统工程与信息 ›› 2014, Vol. 14 ›› Issue (2): 94-101.

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

张勰^*，赵嶷飞，刘宏志

中国民航大学天津市空管运行规划与安全技术重点实验室，天津300300

收稿日期:2013-08-29 修回日期:2013-10-29 出版日期:2014-04-25 发布日期:2014-07-07
作者简介:张勰（1981-），男，陕西咸阳人，助理研究员，博士.
基金资助:
国家自然科学基金（61039001）；国家科技支撑计划(2011BAH24B10)；中国民航大学科研基金(2011kyE04)；中国民航大学科研启动基金(2012QD04X) .

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

ZHANG Xie，ZHAO Yi-fei，LIU Hong-zhi

Tianjin Key Lab of Operation Programming and Safety Technology of Air Traffic Management, Civil Aviation University of China, Tianjin300300, China

Received:2013-08-29 Revised:2013-10-29 Online:2014-04-25 Published:2014-07-07

摘要/Abstract

摘要：

航班进港调度问题是一个典型的组合优化问题，具有多约束复杂特性.针对遗传算法求解航班进港调度问题时多约束难以处理、运算量大、易陷入局部最优的不足，本文应用协同进化思想，构建航班进港调度问题决策解种群和惩罚因子种群，通过种群间的竞争、协作改善算法性能；设计一种带约束处理的编码策略，将安全间隔约束纳入编码过程，降低了问题的约束复杂度，进而提出一种改进的协同进化遗传算法(Co-evolution? ary Genetic Algorithm，CoGA)，并应用首都机场的实际运行数据进行了仿真.结果表明，本文方法能够有效处理航班进港调度问题中的大量约束，在优化效果与GA算法相当的情况下，有效降低了计算时间，克服了问题规模剧增导致的计算效率低下的难题.

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

Abstract:

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 International 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.

Key words: air transportation, co- evolutionary, genetic algorithm, aircraft arrival scheduling, air traffic flow management

中图分类号:

V355.2

张勰，赵嶷飞，刘宏志. 基于协同进化遗传算法的航班进港优化调度[J]. 交通运输系统工程与信息, 2014, 14(2): 94-101.

ZHANG Xie，ZHAO Yi-fei，LIU Hong-zhi. Optimal Scheduling of Aircraft Arrivals Based on Co-evolutionary Genetic Algorithm[J]. Journal of Transportation Systems Engineering and Information Technology, 2014, 14(2): 94-101.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract18753.shtml

http://www.tseit.org.cn/CN/Y2014/V14/I2/94

参考文献

[1] Andreussi A, Bianco L, Ricciardelli S. A simulation mod? el for aircraft sequencing in the near terminal area[J]. European Journal of Operational Research,1981, 8(4): 345-354.

[2] Coumba D, Babacar M, Diaraf S. Scheduling aircraft landings at LSS airport[J]. American Journal of Operations Research,2012,2(2):235-241.
[3] Beasley J E, Krishnamoorthy M, Sharaiha Y M. Scheduling aircraft landings - the static case[J]. Transportation Science.2000,34(2):180–197.
[4] Stiverson P, Rathinam S. Heuristics for a runway-queue management problem[J]. Journal of Aerospace Engineering,2011,225(5):481–499.
[5] Reza T, Mojtaba Y, Farzad R. Scheduling the sequence of aircraft landings for a single runway using a fuzzy programming approach[J]. Journal of Air Transport Management,2012,25:15-18.
[6] Dear R G. The dynamic scheduling of aircraft in the near terminal area[R].M.I.T, Flight Transportation Laboratory Report, R76-9,1976.
[7] Balakrishnan H, Chandran B. Scheduling aircraft landings under constrained position shifting[C]// AIAA Guidance, Navigation, and Control Conference and Exhibit. Keystone, Colorado, USA,2006:21-24.
[8] LEE H, Balakrishnan H. Fuel cost delay and throughput tradeoffs in runway scheduling[C] // Proceedings of the American Control Conference. Seattle, USA,2008:2449-2454.
[9] 朱星辉，朱金福，高强. 基于约束编程的飞机排班问题研究[J]. 交通运输系统工程与信息, 2011, 11(6):151-156．[ZHU X H, ZHU J F, GAO Q. Aircraft scheduling based on constraint programming[J]. Journal of Transportation Systems Engineering and Information Technology,2011,11(6):151-156.]
[10] Ciesielski V, Scerri P. An anytime algorithm for scheduling of aircraft landing times using genetic algorithms[J].Australian Journal of Intelligent Information Processing Systems.1997,4(3):206–213.
[11] Cao Y, and Sun D. Greedy-heuristic-aided mixed-integer linear programming approach for arrival scheduling [J]. Journal of Aerospace Information Systems, 2013, 10(7):323-336.
[12] Ciesielski V, Scerri P. Real time genetic scheduling of aircraft landing times[C] // Proceedings of the IEEE Conference on Evolutionary Computation. Anchorage, USA,1998:360–364.
[13] Pinol H, Beasley J E. Scatter search and bionomic algorithms for the aircraft landing problem[J]. European Journal of Operational Research.2006, 171(2):439-462.
[14] Zhan Z H, Zhang J, Li Y. An efficient ant colony system based on receding horizon control for the aircraft arrival sequencing and scheduling problem[J]. IEEE Transactions on Intelligent Transportation Systems. 2010, 11(2):399-412.
[15] 王世东，张越，张智海，等. 繁忙机场航班降落排序的多目标优化[J]. 交通运输系统工程与信息, 2012, 12(4):135-142. [WANG S D, ZHANG Y, ZHANG Z H, et al. Multi- objectives optimization on flights landing sequence at busy airport[J]. Journal of Transportation Systems Engineering and Information Technology,2012,12(4):135-142]
[16] Tian J, Xu H. Optimizing arrival flight delay scheduling based on simulated annealing algorithm[C]. Physics Procedia,2012,33:348-353.
[17] 冯兴杰，孟欣.基于免疫粒子群优化算法的航班着陆调度研究[J].计算机工程,2012,38(13):273-275,279. [FENG X J, MENG X. Research on flight landing schedule based on immune particle swarm optimization algorithm[J]. Computer Engineering,2012,38(13):273-275,279.]
[18] 孟祥伟，张平，李春锦. 到场飞机排序及调度问题的Memetic算法[J].西南交通大学学报，2011，46(3):488-493. [MENG X W, ZHANG P, LI C J. Memetic algorithm for aircraft arrival sequencing and scheduling problem[J]. Journal of Southwest Jiaotong University,2011,46(3):488-493.]
[19] Dong B, Du W. Scheduling arrival aircrafts on multi-runway based on an improved artificial Fish Swarm algorithm[C]// Proceedings of the 2010International Conference on Computational and Information Sciences,Chengdu, Sichuan, China,2010:499-502.
[20] 慕彩红. 协同进化数值优化算法及其应用研究[D].西安: 西安电子科技大学, 2010. [MU C H. Co-evolutionary numerical optimization algorithms and their applications[D]. Xi’an: Xidian University,2010]
[21] Zhang X, Zhang X J, Zhang J, et al. Optimization of sequencing for aircraft arrival based on approach Routes [C]// Proceedings of the 10th International IEEE Conference on Intelligent Transportation Systems. Seattle,USA,2007:592-596.[22] Thomas P R, Xin Y. Stochastic ranking for constrained evolutionary optimization[J]. IEEE Transactions on Evolutionary Computation.2000,4(3):284–294.[23] Tessema B, Yen G G. A Self Adaptive penalty function based algorithm for constrained optimization[C]. IEEE Congress on Evolutionary Computation. Vancouver, BC 2006:246–253.
[24] Liu J, Zhong W C, Jiao L C. An organizational evolutionary algorithm for numerical optimization[J]. IEEE Transactions on Systems, Man, and Cybernetics—Part B: Cybernetics,2007,37(4):1052-1064.