Memetic Algorithm for Aircraft Arrival Sequencing and Scheduling Problem
-
摘要: 为克服遗传算法求解多跑道系统到场飞机排序及调度问题时局部搜索能力不强的弱点,建立了该问题 的混合整数0灢1二次规划模型.通过证明同型飞机在每条跑道上都应按其预计到达该跑道时间的先后顺序依次 着陆这一命题,设计了遗传算法与局部优化算法相结合的Memetic算法.算例结果表明:其运行10次的最劣解 均不劣于其他遗传算法的最好解,且在5条跑道、20架飞机的情况下,Memetic算法求解时间为0.17s,与精确 算法相比,能满足实时应用需求.Abstract: In order to improve the local search capacity of genetic algorithms (GAs) in solving the aircraft arrival sequencing and scheduling problem in a multi-runway system, a mixed-integer zero-one quadratic programming model for the problem was built. Then, the proposition was proved that aircrafts of the same type should land on each runway in the order of their expected time of arrival under the first-come first-served policy, and a Memetic algorithm that couples the local improvement algorithm with the genetic algorithm was designed to solve the model. The computational results on several publicly available test problems show that the worst solutions found over ten replications of the Memetic algorithm are not inferior to the best solutions found by some existing GAs, and that the execution time is only 0.17 s for the problem involving 20 aircrafts and 5 runways, and hence is more suitable for real time application compared with the exact algorithm.
点击查看大图
计量
- 文章访问数: 1618
- HTML全文浏览量: 65
- PDF下载量: 474
- 被引次数: 0