求解带有时间窗和提前/拖期惩罚的飞机着陆问题的遗传算法

运筹学学报 ›› 2012, Vol. 16 ›› Issue (1): 67-76.

求解带有时间窗和提前/拖期惩罚的飞机着陆问题的遗传算法

王宏¹, 林丹¹, 李敏强²

1. 天津大学理学院，天津，300072 2 天津大学管理学院，天津，300072

收稿日期:2011-03-24 修回日期:2011-07-26 出版日期:2012-03-15 发布日期:2012-03-15
通讯作者: 王宏 E-mail:wanghong@tju.edu.cn
基金资助:
国家杰出青年科学基金项目(70925005/G0112)

Genetic Algorithm for Aircraft Landing Problem with Predetermined Time Window and Earliness/Tardiness Penalties

WANG Hong¹, LIN Dan¹, LI Min-Qiang²

1. School of Science, Tianjin University, Tianjin 300072, China; 2. School of Management, Tianjin University, Tianjin 300072, China;

Received:2011-03-24 Revised:2011-07-26 Online:2012-03-15 Published:2012-03-15
Supported by:
China National Funds for Distinguished Young Scientists

摘要/Abstract

摘要： 研究了带有时间窗、飞机着陆的总提前/拖期惩罚最小为目标函数的飞机着陆问题。针对此问题设计了一种遗传算法进行求解。染色体表示为飞机着陆次序和着陆跑道两个向量，一个新的解码算法来计算飞机的着陆时间。采用数据库OR-Library中的实例进行数值实验，实验结果表明：设计的算法是有效的, 主要原因是解码算法能大大提高解的质量。该算法对于求解带有时间窗、目标函数为提前/拖期惩罚最小的调度问题具有借鉴意义。

关键词: 飞机着陆, 调度, 遗传算法, 时间窗, 提前/拖期惩罚

Abstract: This paper considers Aircraft Landing Problem. Each aircraft lands within a predetermined time window and meets separation time requirements with other aircrafts. The objective is to minimize total weighted earliness and tardiness of all aircrafts. We suggest a genetic algorithm (GA) to solve this problem. Each chromosome contains two vectors: a sequence for landing the planes and an assignment of runways. A new decoding procedure is designed to determine the landing time for all aircraft. The computational experiments on 8 standard instances provided by the OR-Library show that the proposed algorithm outperforms the Scatter Search (SS) algorithm and the hybrid method combining Genetic Algorithms with Ant Colony Optimization (ACGA) presented in the literature. In order to evaluate the performance of the proposed decoding procedure, we compare the proposed algorithm with the GA that employs the decoding procedure applied in ACGA. The results show that the proposed decoding procedure can improve the quality of the solution for the considered problem. It is applicable developing the algorithm described in this paper for a similar scheduling problem with predetermined time window and earliness/tardiness penalties.

Key words: aircraft landing, scheduling, genetic algorithm, time window, earliness/tardiness penalties

王宏, 林丹, 李敏强. 求解带有时间窗和提前/拖期惩罚的飞机着陆问题的遗传算法[J]. 运筹学学报, 2012, 16(1): 67-76.

WANG Hong, LIN Dan, LI Min-Qiang. Genetic Algorithm for Aircraft Landing Problem with Predetermined Time Window and Earliness/Tardiness Penalties[J]. Operations Research Transactions, 2012, 16(1): 67-76.

参考文献

YU G. Operations research in the airline industry[M]. Boston: Kluwer Academic Publishers, 1997.
Erzberger H, Nedell W. Design of automated system for management of arrival traffic[R]. NASA TM 102201, 1989.
DEAR R D. The dynamic scheduling of aircraft in the near terminal area[R]. Cambridge: MIT Press, 1976.
应圣钢, 孙富春, 胡来红, 刘华平, 等. 基于多目标动态规划的多跑道进港排序. 控制理论与应用, 2010, 27(7): 827-835.
DEAR R D. The dynamic scheduling of aircraft in the near terminal area[R]. Cambridge: MIT Press, 1976.
DEAR R D. The dynamic scheduling of aircraft in the near terminal area[R]. Cambridge: MIT Press, 1976.
DEAR R D. The dynamic scheduling of aircraft in the near terminal area[R]. Cambridge: MIT Press, 1976.
王莉莉, 史忠科, 张兆宁, 机场着陆排序的一种滑动窗优化算法[J]. 中国民航学院学报, 2004, 22(6): 18-21.
徐肖豪, 李忠诚, 模糊模式识别算法在最后进近排序中的应用[J]. 中国民航学院学报, 2004, 22(2): 1-5.
冯兴杰, 黄亚楼, 飞机着陆调度排序算法的设计与实现[J]. 计算机工程, 2004，30(10): 160-162.
杨秋辉, 游志胜, 冯子亮, 等. 一种改进的基于遗传算法的多跑道到达飞机调度[J]. 四川大学学报(工程科学版), 2006, 38(2): 141-145.
DEAR R D. The dynamic scheduling of aircraft in the near terminal area[R]. Cambridge: MIT Press, 1976.
陈欣, 杨文东, 陆迅, 朱金福, 一种机场终端区飞机排序问题的蚁群算法研究[J]. 山东大学学报(工学版), 2007, 37(6): 111-117.
Ernst A T, Krishnamoorthy M, Storer R H, Heuristic and exact algorithms for scheduling aircraft landings[J]. Networks, 1999, 34: 229-241.
Hansen J V, Genetic search methods in air traffic control[J]. Computers and Operations Research, 2004, 31: 445-459.
Pinol H, Beasley J E, Scatter Search and Bionomic Algorithms for the aircraft landing problem[J]. European Journal of Operational Research, 2006, 171: 439-462.
Hu X B, Paolo E D, An efficient genetic algorithm with uniform crossover for air traffic control[J]. Computers and Operations Research, 2009, 36: 245 - 259.
Bencheikh G, Boukachour J., Alaoui A E H, et al. Hybrid method for aircraft landing scheduling based on a Job Shop formulation [J]. IJCSNS International Journal of Computer Science and Network Security, August 2009, 9(8): 78-88.
Lee C Y, Choi J Y, A genetic algorithm for job sequencing problems with distinct due dates and general early-tardy penalty weights[J]. Computers and Operations Research, 1995, 22(8): 857-869.
Beasley J E, Krishnamoorthy M, Sharaiha Y M, et al. Scheduling aircraft landings-The static case[J]. Transportation Science, 2000, 34(2): 180-197.

[1]	王翼展, 张安, 陈永, 陈光亭. 堆取料机调度问题的一个近似算法[J]. 运筹学学报, 2020, 24(1): 147-154.
[2]	陈秋宏, 张新功. 带有固定区间的单机双代理可中断总误工问题[J]. 运筹学学报, 2019, 23(1): 61-71.
[3]	李英, 乔龙亮, 郑斐峰. 具有预知信息的集装箱码头泊位与岸桥联合调度在线模型[J]. 运筹学学报, 2018, 22(3): 28-36.
[4]	宁涛, 陈荣, 郭晨, 梁旭. 一种基于双链量子编码的动态车辆路径问题解决策略[J]. 运筹学学报, 2015, 19(2): 72-82.
[5]	蒋建林, 李雪, ASSANI Saeed, 吴仆, 王璨璨. 带投资约束且p不确定的推广p-中位问题[J]. 运筹学学报, 2013, 17(4): 69-79.
[6]	段渊. 实时系统中单处理器调度算法的优化设计研究[J]. 运筹学学报, 2013, 17(2): 27-34.
[7]	帅天平，余金果，孙玲. 一种求解延迟工件数最小的混合流水车间调度问题的模拟退火算法[J]. 运筹学学报, 2013, 17(2): 41-47.
[8]	汪传旭, 蒋良奎. 基于应急救援物资单向转运的受灾点库存策略研究[J]. 运筹学学报, 2011, 15(4): 93-101.