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

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

作　　者：王宏[1] 林丹[1] 李敏强[2] 

机构地区：[1]天津大学理学院,天津300072 [2]天津大学管理学院,天津300072

出　　处：《运筹学学报》2012年第1期67-76,共10页Operations Research Transactions

基　　金：国家杰出青年科学基金(70925005C0112)

摘　　要：研究了带有时间窗、飞机着陆的总提前/拖期惩罚最小为目标函数的飞机着陆问题.针对此问题设计了一种遗传算法进行求解.染色体表示为飞机着陆次序和着陆跑道两个向量,一个新的解码算法来计算飞机的着陆时间.采用数据库OR-Library中的实例进行数值实验,实验结果表明:设计的算法是有效的,主要原因是解码算法能大大提高解的质量.该算法对于求解带有时间窗、目标函数为提前/拖期惩罚最小的调度问题具有借鉴意义.This paper considers Aircraft Landing Problem. Each aircraft lands within a predetermined time window and meets separation time requirements with other air- crafts. 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 com- putational 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.

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

分 类 号：O223[理学—运筹学与控制论]