Application of Multi-Objective Optimization Genetic Algorithms for Airline Disruption Management

[[abstract]]本計劃擬提出一多目標最佳化基因演算法應用在航空排程擾動管理上以便在很短的時間內求算出一個具有時間效益之航班排班方式，用以處理航班受擾動後之回復，此一處理方式涵蓋五個最佳化目標，包括：1)地面停等時間、2)流量守衡、3)總航班延誤時間、4)航班互換、及5)三十分鐘最長延誤時間等。為期能在班表變動最小的情況下完成航班擾動之處理作業，本計劃所採行之多目標最佳化基因演算法係以傳統之基因演算法加上制約不等式法及多目標最佳化之方法以便於能在同一時間考慮到許多不同的目標並找出最佳解。傳統上航班擾動管理的問題都是採用作業研究 (Operations Research, OR) 的技巧，然而此類方法必須要有精確的數學模式定義，在現實作業中由於環境的複雜及動態的變化常常需要同時考慮許多因素，因而使得數學模式的定義變得非常困難。本研究未來將會使用實際之航空公司班表來進行驗證，以確認本研究所提出之多目標最佳化航空擾動管理模式具有在短時間內處理航班擾動問題之能力，未來希望能將此一模式推廣應用至航空公司之實務運作上，以便爭取決策時效，節省經營成本、增進旅客權益。[[abstract]]This research proposes a method of using Multi-objective Optimization Genetic Algorithm (MGA) to quickly generate a time-effective aircraft routing in response to the schedule disruption of short-haul flights and tries to optimize objective functions involving ground turn-around time, flow balance, total flight delay time, flight swap and 30 minutes maximum delay time of the original schedules. The MGA approach, a method of combining the traditional genetic algorithm (TGA) with the multi-objective optimization method, can consider multiple objectives in the same time then explore the optimal solution. Traditionally, Airline Disruption Management problem is solved by Operations Research (OR) techniques, which always require a precise mathematical model. But in real-world airline operation environment, there are too many factors to be considered dynamically, and thus it is very difficult to define a precise mathematical model in time. The computational experiment will base on a real-world airline flight schedule and prove that the proposed method, Multi-objective Optimization Airline Disruption Management (MOADM) by Genetic Algorithms, can recover the perturbation within a very short duration. Finally, the results will show the application capability for presenting high quality solutions in a few minutes and therefore can be used as a real-time decision support tool for practical complex airline operations.[[note]]NSC96-2221-E327-005-MY