機隊排程與班次表規劃之優劣影響航空業者營運績效甚巨，而機隊排程作業主要係指業者對所擁有機隊中各飛機之飛航時程與起迄場站之安排，其排程之結果不但攸關設備之使用效率、左右班次表之擬訂與人員之調度，更重要的，將進而直接影響及業者之獲利能力、服務水準與市場之競爭能力等。在國內，實務作業上多以人工試誤方法求解，然隨著經營規模的成長，效率的要求已逐漸突顯此一傳統方法之不敷使用；於近期之相關研究文獻，則有學者沿用目前實務排程規劃作業上採用之「草擬班次表」作為基本輸入，進而再配合考量相關之飛航限制來建立排程模式。此類較系統性之求解方法在處理複雜之排程問題時，效率上應可改善，唯以此方法進行排程作業，必須先間接經由主觀之判斷，決定概略滿足市場需求之航線、班次數與時間（草擬班次表），再以所發展之模式系統化一次求解找出確實的供給。歸納上述二類處理方法均甚難以直接有效的掌握需求與供給之間的互動關係。 本研究因而以數學規劃方法構建一直截整合旅次需求與航次供給之多機種多停靠飛航排程模式，並進一步發展其求解演算法，以幫助業者求得最佳的機隊排程與班次表。本研究模式係以多重時空網路來定式人旅次流動與飛機流動，是為一較特殊之整數多重貨物網路流動問題；數學上係屬於NP-hard 性質之問題。研究中係利用拉氏鬆弛法、次梯度法、網路單體法、流量分解法與最小成本流量推擠法等綜合發展一拉氏演算法（Lagrangian relaxation-based algorithm）求解；另本研究以一本國航空公司之國內客運營運資料進行模式之實證，並以C語言撰寫電腦演算法與實證架構。模式實證之收斂效果尚稱理想，期能於未來實務應用上提供航空業者作為有效改善營運績效之輔助規劃工具。 Fleet routing and flight scheduling are important in airline operations. In particular, they always affect the usage efficiency of facilities, the establishment of timetables and the crew scheduling. As a result, they are essential to carriers’ profitability, level of service and competitive capability in the market. Most of the airlines in Taiwan currently adopt a trial-and-error process for fleet routing and flight scheduling practices. They iterate the schedule construction and evaluation phases through manual operations. Such an approach is considerd to be less efficient when the flight network become larger, and can possibly result in an inferior feasible solution. Recently, there are research developing mathematic models and solution algorithms to solve the problem through the use of an indispensible medium called “draft timetable.” These mathematic approaches were anticipated to be comparatively more systematic and efficient than the traditional trial-and-error method. Nevertheless, not only “draft timetable” itself involves too much subjective judgement and decision in its constructing process, but also such approaches are incapable of directly and systematically managing the interrelationship between supply and demand. This research therefore developed an integrated model and a solution algorithm to help carriers simultaneously solve for better fleet routes and proper timetables. In order to directly manage the interrelationships between trip demand and flight supply, a time-space network technique was applied to modeling the movements of aircraft and passenger flows. Mathematically, the model was formulated as a special integer multiple commodity network flow problem which was categorized as an NP-hard problem. A Lagrangian relaxation-based algorithm was developed to efficiently solve the problem on the basis of Lagrangian relaxation, the sub-gradient method, the network simplex method, the least cost flow augmenting algorithm and the flow decomposition algorithm. To show how well the model and the solution algorithm could be applied in the real world, a case study regarding the domestic operations of a major Taiwan airline was performed by using the C computer language. The admirable outcome has shown the model’s good performance. Presumably, the results are practically helpful for airlines in Taiwan to improve their operations.
