航空公司之空服員排班問題，在傳統上，一般定式為集合涵蓋問題或集合分割問題，近十幾年來，對於空服員排班問題多以變數產生法求解之，並常需進一步配合整數規劃之演算法求得整數解。然而，當航空公司考量在不同機型接續、不同艙位等級服務限制及多基地型態之實際營運服務情形時，將使問題更趨複雜，若以上述演算法求解之，將無法有效求解此類問題。 為改善上述情形，本研究以網路流動方式建構建立一空服員基本排班網路模式，並參考業者實務上的做法，研擬空服員混合排班策略網路模式。由於此類網路模式分別為含額外限制式之網路流動問題及多重貨物網路流動問題，在數學上屬於NP-Hard性質的問題，為有效求解大規模問題，本研究利用拉氏鬆弛法暨次梯度法、網路單體法、及自行發展之啟發式解法加以求解。本研究亦針對一航班僅包含於一航行勤務，且不考慮排班策略之情況下，提出一排班簡化模式。此模式可定式為純網路流動問題，本研究係以網路單體法求解此一模式。本研究並以國內一主要航空公司之實際國際線營運資料為例，進行測試分析，結果顯示本研究所提出之排班網路模式及求解演算法，可有效地處理大型排班問題。 Airline crew scheduling problems have been traditionally formulated as set covering problems or set partitioning problems. To resolve large-scale problems in practice, the column generation approach with integer programming algorithms has usually been employed in decades. When airline carriers face the multi-base operations as well as aircraft type continuity and cabin classes in practical operations, these problems become more complicated and difficult to solve. In this research, taking into account the aforementioned factors, we introduce new network models that can improve both efficiency and effectiveness of solving crew scheduling problems to help air carriers minimize crew cost and plan proper crew service rotations under the real constraints. Mathematically, the models will be respectively formulated as network flow problems with side constraints and multi-commodity network flow problems. A Lagrangian relaxation-based algorithm, coupled with a subgradient method, the network simplex method and a heuristic for upper bound solution, is suggested to solve the problem. Based on the scenario, which a specific flight is only included in a work duty, we provide a simplified model which is classified as a pure network flow problem. The network simplex method is suggested to solve the simplified model in this research. Furthermore, the flow decomposition algorithm is applied to generate all pairings for cabin crews. In order to evaluate the model in practice, computational tests referring the international operation of a major airline carrier in Taiwan were performed. The results show the network models and the Lagrangian relaxation-based algorithm can be useful for efficiently solving large-scale airline crew scheduling problems.
