應用離散差分進化演算法求解航機降落問題

近年來，國際間觀光貿易愈趨頻繁，連帶加增航空運輸需求量，因此，能有效的處理航機降落問題實屬不易。本研究嘗試以離散差分進化演算法架構求解OR-Library中關於航機降落問題的13個不同航機數大小的案例資料。探討此演算法在初始解集合組成方式、降落時間計算方法，交配重組法，以及演算法架構之參數組合等情境組合下的求解能力。實驗結果顯示，在初始解集合組成方式方面，小案例以隨機亂數比例高所產生之解有較佳求解能力；而大案例單跑道與小案例單跑道相同，大案例多跑道則以案例資料變換比例高所產生之解較佳。在降落時間計算方法方面，小案例單跑道係以依照航機降落順序改善而有較佳的求解能力，多跑道則以航機降落之反向順序改善較佳；而大案例單跑道係與小案例多跑道相同，但於多跑道則以從時間成本最大的航機改善起為較佳。在交配重組法方面，小案例以Order Crossover(OX)交配法之求解能力較Edge Recombination(ER)交配法來得優秀；而在大案例卻以ER交配法較好。在演算法架構之參數組合方面，無論航機數量大小，皆以10組解集合配合菁英主義之更新機制有較佳的求解能力。另外，在求解結果部分，小案例除了皆能求得與文獻相同最佳值外，尤以單跑道問題的求解能力較文獻優秀；在大案例中，雖僅更新一個單跑道、三個雙跑道之最佳值，其餘多跑道最佳值皆能與文獻相同，而同等情境組合之求解能力則係以本研究較文獻為佳。因此，本研究所提之演算法對於處理航機降落問題係有相當優良的適應性並有其參考價值。

關鍵字

航機降落問題；離散差分進化演算法；交配重組法

並列摘要

Due to the increased touristic activities and booming commercial intercourses between nations, the efficiency of the aircraft landing problem (ALP) has attracted intensive attention. This study proposes a discrete differential evolution algorithm to solve the 13 ALP benchmarks, which are commonly found in OR-Library and have different number of aircraft and runway. This study tries to explore the performance of this algorithm based on different scenarios – such as the creating of the initial solutions, the calculating of the aircraft landing time, the selecting of crossover operators, and the setting of other important parameters. The results show some important findings. Firstly, for the initial solution generation, the algorithm has better performance by using random generation on the small cases. Yet for the single runway, there is not much difference between the small and large cases. The algorithm has better performance if it frequently exchanges the order from dataset for the large case with multiple runways. As for the issue of calculating the landing time, it has better performance if the landing sequence for the small cases with single runway is improved. On the other hand, it does have better performance if the algorithm improved by the reversed order of the landing sequence for the large cases with multiple runways. The costs of landing time are the same for the large cases with single runways and singe cases with multiple runways; however, it will reach better performance if the aircraft with the highest cost can be improved first. For the different crossover operations, this study has shown that the order crossover (OX) operator is superior to the edge recombination (ER) operator for small cases, yet the ER is favored in large cases. For the setting of other parameters, this study has found that using 10 sets of solutions with elitism approach outperforms the other settings, no matter the numbers of the aircrafts. The numerical experiment also shows that this proposed method reaches the optimal solutions for the small cases, and even obtains better solution for the single runway cases compared with the results published in previous studies. For the large cases, even though the algorithm renewed the objective values for a single runway case and three double runway cases, the rest of the cases did converge to the optimal solutions. The efficacy of this proposed algorithm shows its potential compared to those published previously with the same scenario in large cases. Hence, it is believed that this proposed algorithm can be applied to complicated aircraft landing problems and reach important academic contributions.