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

Abstract

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

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.

References

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]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[2]	CHEN Rubing, YUAN Jinjiang. Single-machine scheduling to minimize total weighted late work with positional due-indices [J]. Operations Research Transactions, 2020, 24(2): 131-144.
[3]	LIU Xiaoxia, YU Shanshan, LUO Wenchang. Approximation algorithms for single machine parallelbatch scheduling with release dates subject to the number of rejected jobs not exceeding a given threshold [J]. Operations Research Transactions, 2020, 24(1): 131-139.
[4]	WANG Yizhan, ZHANG An, CHEN Yong, CHEN Guangting. An approximation algorithm for reclaimer scheduling [J]. Operations Research Transactions, 2020, 24(1): 147-154.
[5]	GOU Yan, DAI Qin, ZHANG Xingong. Scheduling problem with time-and-position-dependent effect on two parallel machines environments [J]. Operations Research Transactions, 2019, 23(4): 86-94.
[6]	LI Ganggang, LU Xiwen. An improved algorithm for single-machine scheduling problem with a period of maintenance to minimize total delivery time [J]. Operations Research Transactions, 2019, 23(4): 95-104.
[7]	LI Wenhua, ZHAI Weina, CHAI Xing, GAO Chao. On-line bounded-batching scheduling of unit-length jobs with two families [J]. Operations Research Transactions, 2019, 23(4): 105-110.
[8]	ZHANG Guochuan, CHEN Lin. The load balancing problem [J]. Operations Research Transactions, 2019, 23(3): 1-14.
[9]	ZHONG Weiya, YANG Ruoyao. Scheduling with sub-jobs' due dates [J]. Operations Research Transactions, 2019, 23(2): 67-74.
[10]	CHEN Qiuhong, ZHANG Xingong. Two-agent preemptive scheduling of jobs with fixed time windows problem about total tardiness on a single machine [J]. Operations Research Transactions, 2019, 23(1): 61-71.
[11]	PENG Nannan, ZHANG Yuzhong, BAI Qingguo, WANG Chengfei. Online batch scheduling problem on uniform machines with agreeable processing times [J]. Operations Research Transactions, 2019, 23(1): 111-118.
[12]	CAI Shuang, YANG Ke, LIU Ke. Model and algorithms of the distributed permutation flow shop scheduling problem with machine eligibility constraints [J]. Operations Research Transactions, 2018, 22(4): 17-30.
[13]	ZHAO Xiaocheng, LI Dagang. Parallel machine scheduling with machine and human eligibility restrictions [J]. Operations Research Transactions, 2018, 22(3): 99-108.
[14]	LI Ying, QIAO Longliang, ZHENG Feifeng. A study of online berth and quay crane integrated allocation problem with lookahead ability [J]. Operations Research Transactions, 2018, 22(3): 28-36.
[15]	HE Cheng, HAN Xinxin. Two-agent scheduling on an unbounded parallel-batching machine to minimize maximum cost and makespan [J]. Operations Research Transactions, 2018, 22(3): 109-116.

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

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments