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

Abstract

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

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.