策略聯盟下航空公司合作排程暨班表規劃之研究

Coordinated Fleet Routing and Flight Scheduling for Airlines under Alliances

陳佳宏(Chia-hung Chen)

指導教授 ： 顏上堯

國立中央大學/工學院/土木工程學系/博士(2007年)

摘要

近年來航空公司時興透過策略聯盟之建立，增加航空網路與機隊營運之效率。而飛航排程與班次表之建立為航空公司營運之重點，與航空公司間策略聯盟績效之關係密切。良好的飛航排程與班次表規劃，除可強化策略聯盟的績效，亦可在航空公司聯盟的談判中，提供一重要之決策參考。目前航空公司在配合策略聯盟的排班上，以往各家航空公司在進行策略聯盟後，僅就現行的班次表各自以人工方式進行局部的調整，未以系統最佳化方法，調整其排班，如此可能降低聯盟的功效。另外，以往研究主要針對個別航空公司的排班作業，無法應用於聯盟航空公司的排班作業。緣此，本研究針對航空公司策略聯盟及航空公司排程的相關性下，建立數個航空公司聯盟排程模式，以幫助聯盟的航空公司在策略的談判中，求得共同最滿意的機隊排程與班次表。此等模式期能於未來實務應用上，提供有效的工具，以處理航空公司策略聯盟下之飛航排程問題。
為測試所發展的聯盟排程模式之可行性，本研究以航空客運與航空貨運排程問題為應用對象。本研究可分成三個部分：第一個部分在航空客運問題方面，本研究考量航空公司策略聯盟及航空公司排程的相關性下，發展數個航空公司聯盟排程模式，以幫助聯盟的航空公司在策略的談判中，求得共同最滿意的機隊排程與班次表。第二部份則以航空貨運排程問題為對象，考量航點選擇、機隊規劃與班次表規劃等三大重要作業，進而發展數個航空貨運聯盟之航點選擇、機隊排程及班次表建立的整合規劃模式，以幫助航空貨運業者在策略聯盟下能有效的選擇航點、建立班次表與規劃機隊排程，進而降低營運成本，提升營運利潤及服務水準。第三部份則針對本研究發展之聯盟排程模式進行發展數個有效率之演算法進行求解。此三部份皆使用實際營運資料加上適當的假設，利用C程式語言，配合CPLEX數學規劃軟體進行求解。最後，根據此三部份的研究結果，提出結論與建議。

關鍵字

門檻值接受法 ； 策略聯盟 ； 飛航排程 ； 班次表 ； 一般化網路 ； 多重貨物網路流動問題 ； 拉氏鬆弛法 ； 啟發式解法

並列摘要

Recently, the trend has been for major air carriers enter into alliances with other carriers as a means of forming global networks and reaching a more efficient level of operations. Fleet routing and flight scheduling are not only important in individual airline operations, but also affect these alliances. The setting of a good coordinated fleet routing and flight scheduling can not only enhance the operating performance of the allied airlines, but can also be a useful reference for allied airlines in their decision-making process. However, currently in Taiwan most fleet routing and flight scheduling formulation is done on a trial-and-error process. To do this the airline iteratively constructs and evaluates the schedule phases manually and independently of each other, without optimization from a systemic perspective. As well most past research on fleet routing and flight scheduling has mainly focused on single carrier transportation, which is difficult to apply to a coordinated scheduling problem. Therefore, to fill this gap in this dissertation, we develop several coordinated scheduling models, in order to help the allied airlines solve for the most satisfactory fleet routes and timetables. It is expected that such models will be useful tools allowing the allied carriers to plan the most suitable fleet routes and timetables for short-term operations.
To evaluate how the proposed coordinated scheduling models perform in practice, we perform apply them to both passenger and cargo fleet routing and flight scheduling problems. The dissertation includes three essays. In the first, we develop several coordinated scheduling models, which will help the allied airlines solve for the most satisfactory fleet routes and timetables within the alliance. In the second, we also develop several coordinated scheduling models combining airport selection, fleet routing and timetable setting, in order to help cargo airlines solve for the most satisfactory cargo fleet within an alliance. In the third, we develop a mixed-stop heuristic and a family of Lagrangian based algorithms for solving coordinated fleet routing and flight scheduling problems. We perform these applications using real operating data, with reasonable simplifications. The C computer language is used to write the necessary programs, coupled with the CPLEX mathematical programming solver, to solve the problems. Finally, conclusions and suggestions for future research are given.

並列關鍵字

Lagrangian relaxation ； Multiple commodity network flow problem ； Generalized network ； Timetable ； Fleet routing ； Alliance ； Threshold accepting ； Heuristic

參考文獻

Abara, J., 1989. Applying Integer Linear Programming to the Fleet Assignment Problem. Interfaces 19, 20-28.

Aykin, T., 1995. The Hub Location and Routing Problem. European Journal of Operational Research 83, 200-219.

Ball, M.O., Magnanti, T.L., Monma, C.L. and Nemhauser, G.L., 1995. Network Routing. Handbooks in Operations Research and Management Science 8.

Barnhart, C., Johnson, E.D., Nemhauser, G.L., Savelsbergh, M.W.P. and Vance, P.H., 1998. Branch and Price Column Generation for Solving Hugh Integer Programs. Operations Research 46, 316-329.

Barnhart, C., Kniker, T., and Lohatepanont, M., 2002. Itinerary-Based Airline Fleet Assignment. Transportation Science 36(2), 199-217.