基于均衡更新蚁群算法的飞机排序调度

计算机与现代化

基于均衡更新蚁群算法的飞机排序调度

南京航空航天大学计算机科学与技术学院，江苏南京210016

收稿日期:2014-11-07 出版日期:2015-02-28 发布日期:2015-03-06
作者简介:李媛祯（1990），女，山东济南人，南京航空航天大学计算机科学与技术学院硕士研究生，研究方向：并行计算；杨群(1974),女，江西南昌人，副教授，博士，研究方向：新型程序设计，软件方法学；段汐（1989），女，云南保山人，硕士研究生，研究方向：并行计算。
基金资助:
国家自然科学基金资助项目(41301407)；江苏省自然科学基金资助项目(BK20130819)

A Balanced Update Ant Colony Optimization for Aircraft Arrival Sequencing and Scheduling

College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China

Received:2014-11-07 Online:2015-02-28 Published:2015-03-06

摘要/Abstract

摘要： 飞机排序调度问题是空中交通管制的一个关键问题，本文在给出飞机排序调度模型的基础上，提出一种均衡更新蚁群算法，利用当前解与全局最优解的差异来均衡地更新信息素，增强算法的全局搜索能力，从而生成更优解。实验结果表明，均衡更新蚁群算法求解飞机排序调度问题时，能用较短时间求出优于对比算法的结果，其性能可以提高12.9%，有助于空中交通管制人员根据实时情况安排合适的飞机着陆顺序。

关键词: 飞机排序调度, 蚁群算法, 均衡更新, 实际载客量

Abstract: Aircraft arrival sequencing and scheduling (ASS) is a key problem of air traffic control (ATC). According to the ASS model, a balanced update ant colony algorithm (BUACO) is proposed in this paper. BUACO balanced update the pheromone and enhance the global search ability of the algorithm by taking advantage of the difference between the current solution and the global optimal solution, in order to generate a better solution. The experiments show that BUACO’s performance can be increased by 12.9% with a shorter computation time than the comparison algorithms when solving ASS problem, which is conductive to arrange a suitable flight landing sequence based on realtime situation for ATC.

Key words: aircraft arrival sequencing and scheduling, ant colony optimization, balanced update, actual seating passengers

中图分类号:

TP391

李媛祯，杨群，段汐. 基于均衡更新蚁群算法的飞机排序调度[J]. 计算机与现代化.

LI Yuanzhen， YANG Qun， DUAN Xi. A Balanced Update Ant Colony Optimization for Aircraft Arrival Sequencing and Scheduling[J]. Computer and Modernization.

参考文献

［1］
Zhan Zhihui, Zhang Jun, Li Yun, et al. 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.
［2］Hu Xiaobing, Di Paolo E.Binaryrepresentationbased genetic algorithm for aircraft arrival sequencing and scheduling［J］. IEEE Transactions on Intelligent Transportation Systems, 2008,9(2):301310.
［3］Hu Xiaobing, Chen Wenhua. Genetic algorithm based on receding horizon control for arrival sequencing and scheduling［J］. Engineering Applications of Artificial Intelligence, 2005,18(5):633642.
［4］Robinson J E, Davis T J, Isaacson D R. Fuzzy reasoningbased sequencing of arrival aircraft in the terminal area［C］// AIAA Guidance, Navigation and Control Conference. 1997:111.
［5］Hu Xiaobing, Di Paolo E A. A ripplespreading genetic algorithm for the aircraft sequencing problem［J］. Evolutionary Computation, 2011,19(1):77106.
［6］Psaraftis H N. A dynamic programming approach for sequencing groups of identical jobs［J］. Operations Research, 1980,28(6):13471359.
［7］Zhao Xiuli, Guo Yanchi. Study on GRAPSACO algorithm for irregular flight rescheduling［C］// IEEE 2012 International Conference on Computer Science & Service System (CSSS). 2012:266269.
［8］刘洪,杨红雨,彭莉娟. 基于分组的进近航班着陆调度算法研究［J］. 电子科技大学学报, 2013,42(4):615620.
［9］赵嶷飞,朱潇,王红勇. 终端区飞机排序的人工蜂群算法［J］. 科学技术与工程, 2013,13(31):92589262.
［10］冯兴杰,孟欣. 基于免疫粒子群优化算法的航班着陆调度研究［J］. 计算机工程, 2012,38(13):273279.
［11］Dorigo M. Optimization, Learning and Nature Algorithms［D］. Milan: Dipartmento di Elettronica, Politecnico di Milano, 1992.
［12］Dorigo M, Birattari M, Stutzle T. Ant colony optimization［J］. Computational Intelligence Magazine, IEEE, 2006,1(4):2839.
［13］Bencheikh G, Boukachour J, Alaoui A E H. Improved ant colony algorithm to solve the aircraft landing problem［J］. International Journal of Computer Theory and Engineering, 2011,3(2):224233.
［14］Wang Shidong, Zhang Yue, Zhang Zhihai, 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.
［15］于剑,王文涛,李航. 对中国航空公司中欧市场运量的影响分析［J］. 中国民航大学学报, 2011,29(1):4245.
［16］Cao Song, Sun Fuchun, Hu Laihong, et al. Departure aircraft sequence optimization using EDA［J］. Journal of Tsinghua University Science and Technology, 2012,52(1):6671.
［17］许军海，何长青，王昭. 机场终端区飞机排序的遗传算法［J］. 信息系统工程, 2013(10):132134.

[1]	张雄, 潘大志, . 融合邻域搜索策略蚁群算法求解带时间窗口的车辆路径问题[J]. 计算机与现代化, 2022, 0(03): 98-102.
[2]	曲建波, 孙剑伟. 基于蚁群算法的导航卫星功率增强任务规划[J]. 计算机与现代化, 2021, 0(02): 104-108.
[3]	高月仁, 吴涛, 高峡. 基于蚁群算法优化的路由频率动态择径的研究[J]. 计算机与现代化, 2020, 0(12): 32-37.
[4]	李显良1,2，周庆平2，谭长庚3，谭焱良2，徐则阳2. 基于蚁群算法的城市体育设施优化选址[J]. 计算机与现代化, 2020, 0(03): 33-.
[5]	叶家琪1，符强1，2，贺亦甲1，叶浩1 . 基于聚类集成的蚁群算法求解大规模TSP问题[J]. 计算机与现代化, 2020, 0(02): 31-.
[6]	梁晶亮,黄军胜,白树军,王鹏,李睿. 基于蚁群算法的电力数据网络APT攻击预警模型[J]. 计算机与现代化, 2019, 0(01): 95-.
[7]	付永忠，潘云峰. 基于改进蚁群算法的垂直旋转式贴片机贴装顺序优化[J]. 计算机与现代化, 2017, 0(8): 17-.
[8]	凌云翔1,2,宋志远1,张世海1,马力2. 基于蚁群算法的高原地区车辆运输路径优化问题[J]. 计算机与现代化, 2016, 0(9): 77-82.
[9]	宋琪，敬超. 面向多核系统的蚁群最优化能耗调度算法[J]. 计算机与现代化, 2016, 0(6): 91-96.
[10]	蔡明，左勇安. 基于MapReduce的混合蚁群算法研究[J]. 计算机与现代化, 2016, 0(10): 6-.
[11]	蔡文哲，王斌君. 一种QoS平面蚁群路由算法的设计与实现[J]. 计算机与现代化, 2015, 0(12): 15-.
[12]	陈曼青1，武子荣1，崔伟宁1，常婷婷2. 改进蚁群算法在装备保障路径选择中的应用[J]. 计算机与现代化, 2015, 0(11): 113-117.
[13]	朱卫宵，祝前旺，陈康. 基于改进蚁群算法的海上编队传感器资源分配模型[J]. 计算机与现代化, 2014, 0(12): 15-18+22.
[14]	刘晓曦;李卓越. 优化蚁群算法的云环境负载均衡[J]. 计算机与现代化, 2013, 1(9): 42-45.
[15]	袁东锋;吕聪颖. 改进蚁群算法在二次分配问题中的应用[J]. 计算机与现代化, 2013, 1(3): 9-11,1.