因應多機場暫時性關閉之飛航排程方法

Abstract

航空公司營運上隨時都可能面臨許多的不確定因素導致機場關閉，使得航空公司無法按照既定的飛航時間表提供服務，致使乘客抱怨，降低服務水準。因此，如何有效地調度可用飛機來解決擾動班次，降低營運損失，實乃當前業者所普遍關切之課題。 本研究的目的在改進傳統實務的作法，考慮飛機總量數目之限制，發展一因應多機場關閉的飛航排程方法。當面臨如天候之不可抗拒因素時，即啟動即時排程模式，考量受影響的班次，並依照當時可用之飛機產生調度方案供調度者參考。在調度模式中，本研究將即時排程問題轉換成一集合分割的問題，並發展一以變數產生法（Column Generation）為基礎的演算法來產生可行的調度方案。在調度方案的產生上，將子問題設計成一最短路徑問題，利用各節點之成本、對偶值、延遲成本、取消成本求解最短路徑，所得之最短路徑即為一可行之排程方案。 為測試模式的可行性與正確性，本研究模擬各種班表情境，作實例測試與修正。實務上航空業者可以針對其調度方案與考量之不同，設定較合適之可調參數值，以求系統能符合業者的需求。結果顯示，不論是針對機場關閉時間長短，或是延遲方案間隔時間長短，均能夠透過本研究之演算方法，得到一個因應機場關閉之適當排程方案；且與窮舉法比較，透過本方法求得的解之目標值與窮舉法之最佳解目標值無異。

Keeping the announced or pre-established schedule is an important factor to guarantee service quality and operation efficiency of an airline company. Mechanical failures and bad weather conditions usually cause perturbation of schedule and result in additional costs. The purpose of this study is to develop a flight schedule adjustment model and a solution algorithm to address these issues. A set partition based model with side constraints is proposed for this purpose. The number of available aircrafts in each depot is considered in this model. A column generation based algorithm is developed to solve this model. The value of dual variable of each constraint is assigned as the arc cost in the sub-problem network. Label Correcting Method is adopted to solve the shortest path problem in the associated sub-problem network. We use simulation data and various scenarios to evaluate the robust of our model and efficiency of the solution method. The testing results indicate that the proposed model and algorithm are sound and promising.