以改良式螞蟻演算法求解航機降落排序問題

A Modified Ant System Algorithm for the Aircraft Landing Problem

吳景堯(Jing-Yao Wu)

指導教授 ： 黃寬丞

國立交通大學/管理學院/運輸科技與管理學系/碩士(2009年)

https://doi.org/10.6842/NCTU.2009.00490

摘要

由於燃油等因素限制，飛機可以降落的時間為一個時窗範圍，且在此時窗範圍內，有最理想的降落時間點。此外，飛機降落會產生空氣擾動，為確保飛航安全，飛機間的降落還必須遵守隔離時間。航機降落排序問題，便是在滿足這些限制之下，分配航機的降落順序及時間。本研究將利用螞蟻演算法求解航機降落排序問題，並透過類似動態規劃的概念，計算固定某一架飛機後的成本下限值，藉此下限值限制搜尋空間，改良螞蟻演算法，更有效率的解決航機降落排序問題。研究結果顯示，問題變數較少時螞蟻演算法可求得最佳解，但隨問題變數增加，求解品質越差。而改良式螞蟻演算法能夠有效限制搜尋空間，當問題變數增加時，仍能求得最佳解，顯示改良式螞蟻演算法求解品質較佳。

關鍵字

航機降落排序 ； 螞蟻演算法

並列摘要

In this paper, we consider the aircraft landing problem at an airport. Because of the fuel, the aircraft landing time will be a time window, in which there are the best landing time for each aircraft. Moreover, when aircraft lands, it will generate air turbulence. For safety reasons, between aircrafts landing should conform to separation time. We solve the aircraft landing problem by ant system. And similar to dynamic programming, we consider a conditional lower bound to constrain the search space, in order to solve the problem faster. The result shows that, ant system can solve the problem, but when variables change more, the solution get worse. And the modified ant system can constrain the search space effectively. When variables change more, it can also find the solution.

並列關鍵字

Aircraft landing ； Ant system

參考文獻

Andreussi, A., Bianco, L. and Ricciardelli, S. (1981) ” A Simulation Model for Aircraft Sequencing in the Near Terminal Area,” European Journal of Operational Research, Vol.8, 345-354.

Beasley, J.E., Krishnamoorthy, M., Sharaiha, Y. M. and Abramson, D. (2000) “Scheduling Aircraft Landings—The Static Case,” Transportation Science, Vol.34, 180-197.

Beasley, J.E., Sonander, J., Havelock, P. (2001) “Scheduling aircraft landings at London Heathrow using a population heuristic,” Journal of the Operational Research Society, Vol.52, 483-493.

Ciesielski, V. and Scerri, P. (1998) “Real Time Genetic Scheduling of Aircraft Landing times,” Proceedings of the 1998 IEEE International conference on Evolutionary Computation.

Leguizamon, G., and Michalewicz, Z., (1999) "A New Version of Ant System for Subset Problem", Evolutionary Computation, CEC 99. Proceedings of the 1999 Congress, Vol.2, 1459-1464