放射型航線飛機排程模式之研究

A Time-Aircraft Network Model for the Aircraft Routing Problem

傳統上，飛機排程問題多藉時空網路構建模式。本研究考慮放射型航線之特性，利用特別設計之時間－運具網路，表示往返班次指派給個別飛機之可行性，而構建飛機排程模式。經分析，確認該模式為一具額外限制式之最小化成本流量問題，透過不同的網路變化，可適用於確知班表下、班表規劃中與班表受擾動等三種不同使用時機的飛機排程問題。本研究以國內某國際航空公司之班表與機隊為例進行模式驗證，並利用分支定限法直接求其正確整數解，所得排程計劃顯示模式指派結果之適切性。此外，亦透過延長規劃期與增加飛機數之變化進行演算績效測試，測試結果顯示分支定限法所需分支次數相當少，故可在合理時間內獲得整數解，求解績效堪稱良好。

Conventionally, the aircraft routing model is formulated with the time-space network. We substitute the space dimension with the aircraft dimension inthe network. The aircraft routing model for the round trip flights rooted at itshome base (radial flights) can take advantages of this time-aircraft network. Itcan be formulated as a minimum cost flow problem with a bundle of sideconstraints, simple equality constraints. This model is applied to a real-worldcase with radial flights and solved with the branch-and-bound algorithm. Thecomputational results show that only a few branches are needed. We also testthis model with more general cases and obtain promising outcomes.