空服員排班網路模式之研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：56

、訪客IP：3.143.17.50

姓名

杜宇平(Yu-Ping Tu) 查詢紙本館藏

畢業系所

土木工程學系

論文名稱

空服員排班網路模式之研究
(NETWORK MODELS FOR AIRLINE)

相關論文

★ 橋梁檢測人力機具排班最佳化之研究	★ 勤業務專責分工下消防人員每日勤務排班最佳模式之研究
★ 司機員排班作業最佳化模式之研究	★ 科學園區廢水場實驗室檢驗員任務指派最佳化模式之研究
★ 倉儲地坪粉光工程之最佳化模式研究	★ 生下水道工程工作井佈設作業機組指派最佳化之研究
★ 急診室臨時性短期護理人力指派最佳化之探討	★ 專案監造人力調派最佳化模式研究
★ 地質鑽探工程人機作業管理最佳化研究	★ 職業棒球球隊球員組合最佳化之研究
★ 鑽堡於卵礫石層施作機具調派最佳化模式之研究	★ 職業安全衛生查核人員人力指派最佳化研究
★ 救災機具預置最佳化之探討	★ 水電工程出工數最佳化之研究
★ 石門水庫服務台及票站人員排班最佳化之研究	★ 空調附屬設備機組維護保養排程最佳化之研究

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

為改善上述情形，本研究以網路流動方式建構建立一空服員基本排班網路模式，並參考業者實務上的做法，研擬空服員混合排班策略網路模式。由於此類網路模式分別為含額外限制式之網路流動問題及多重貨物網路流動問題，在數學上屬於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.

關鍵字(中)

★ 空服員排班
★ 網路模式
★ 純網路流動問題
★ 含額外限制式之網路流動問題
★ 多重貨物網路流動問題
★ 拉氏演算法

關鍵字(英)

★ crew scheduling
★ network models
★ pure network fl

論文目次

封面
中文摘要
英文摘要
誌謝
目錄
圖目錄
表目錄
第一章　緒論
１．１　研究背景與動機
１．２　研究目的與範圍
１．３　研究方法與流程
第二章　文獻回顧
２．１　傳統空服員排班問題模式
２．２　求解演算法
２．３　線性解整數化
２．４　結語
第三章　模式建立
３．１　問題描述
３．２　基本排班網路模式
３．３　排班策略網路模式
３．４　簡化模式
３．５　空服員排班模式轉換
３．６　空服員排班模式之應用
３．７　結語
第四章　模式求解
４．１　模式存在最佳解
４．２　求解演算法
４．３　組員行程
４．４　結語
第五章　實例測試與結果分析
５．１　資料分析
５．２　模式發展
５．３　結果分析
５．４　敏感度分析
５．５　結語
第六章　結論與建議
６．１　結論
６．２　建議
６．３　貢獻
參考文獻

參考文獻

Ahuja, R. K., Magnanti, T. L. and Orlin, J. B. (1993), Network Flows, Theory, Algorithms, and Applications, Prentice Hall, Englewood Cliffs, NJ.
Anbil, R., Gelman, E., Patty, B. and Tanga, R. (1991), “Recent Advances in Crew-Pairing Optimization at American Airlines,” Interfaces 21, pp. 62-74.
Anbil, R., Tanga, R. and Johnson , E. L. (1992), “A Global Approach to Crew-pairing Optimization ,” IBM Systems Journal 31, No. 1, pp. 71-78.
Arabeyre, J. P., Feranley, J., Steiger, F. C. and Teather, W. (1969), “The Airline Crew Scheduling Problem: A Survey,” Transportation Science 3, pp. 140 - 163.
Ball, M. O., Magnati, T. L., Monma, C. L. and Nemhauser, G. L. (1995), Network Routing, Handbooks in Operations Research and Management 8, North Holland, Amsterdam.
Barnhart, C. and Shenoi, R. G. (1998), “An Approximate Model and Solution Approach for the Long-haul Crew Pairing Problem,” Transportation Science 32, No.3, pp. 221-231.
Barnhart, C., Hatay, L. and Johnson, E. L. (1995), “Deadhead Selection for the Long-Haul Crew Pairing Problem,” Operations Research 43, No. 3, pp. 491-499.
Barnhart, C., Johnson, E. L., Nemhauser, L. G., Savelsbergh, M. W. P. and Vance, P. H. (1998), “Branch-and-price: Column Generation for Solving Huge Integer Programs,” Operations Research 46, No.3, pp. 316-329.
Chu, H. D., Gelman, E. and Johnson, E. L. (1997), “Solving Large Scale Crew Scheduling Problems,” European Journal of Operational Research 97, pp. 260-268.
Desaulniers, G., Desrosiers, J., Dumas, Y., Marc, S., Rioux, B., Solomon, M. M. and Soumis, F. (1997), “Crew Pairing at Air France,” European Journal of Operational Research 97, pp. 245-259.
Etschmaier, M. M. and Mathaisel, D. F. X. (1985), “Airline Scheduling: An Overview,” Transportation Science 19, pp. 127-138.
Gerbracht, R., (1978), “A New Algorithm for Very Large Crew Pairing Problems,” Continental Airlines, pp. 315-341.
Gershkoff, I. (1989), “Optimizing Flight Crew schedules,” Interfaces 19, pp. 29-43.
Graves, G. W., McBride, R. D. and Gershkoff, I. (1993), “Flight Crew Scheduling,” Management Science 39, pp. 736-745.
Hoffman, K. L. and Padberg, M. (1993), “Solving Airline Crew-Scheduling Problem by Branch-and-Cut,” Management Science 39, pp. 657-682.
Jones, R. D. (1989), “Development of an Automated Airline Crew Bid Generation System,” Interfaces 19, pp. 44-51.
Lavoie, S., Minoux, M. and Odier, E. (1988), “A New Approach for Crew Pairing Problems by Column Generation with an Application to Air Transportation,” European Journal of Operational Research 35, pp. 45-58.
Minoux, M. (1984), "Column Generation Techniques in Combinatorial Optimization, A New Application to Crew - Pairing Problems," Proceedings XXIVth AGIFORS Symposium, Strabosurg, France.
Nicoletti, B. (1975), “Automatic Crew Rostering, ” Transportation Science 9, No. 1, pp. 33-42.
Rubin, J., (1973), “A Technique for the Solution of Massive Set Covering Problems, with Application to Airline Crew Scheduling,” Transportation Science 7, No. 1, pp. 34-48.
Stojkovic, M., Soumis, F. and Desrosiers, J. (1998), “The Operational Airline Crew Scheduling Problem,” Transportation Science 32, pp. 232-245.
Teodorovic, D. (1988), Airline Operations Research, Gordon & Breach Science
Vance, P. H., Barnhart, C., Johnson, E. L. and Nemhauser, G. L. (1997), “Airline Crew Scheduling: A New Formulation and Decomposition Algorithm, “ Operations Research 45, pp. 188-200.
Wedelin, D. (1995), “An Algorithm for Large Scale 0-1 Integer Programming with Application to Airline Crew Scheduling,” Annals of Operations Research 57, 283-301.
Yan, S. and Tu, Y. P. (1997), “Multifleet and Multistop Flight Scheduling for Schedule Perturbation,” European Journal of Operational Research 103, pp. 155-169.
沈志展 (民國80年), “民航空運排程分析模式之應用”，國立交通大學運輸研究所碩士論文。
陳本立 (民國79年)，”零壹整數規劃問題新解法之研究：位置搜尋法之建立與評估”，國立交通大學資訊科學研究所碩士論文。
湯敦台，民國87年，”空服員混和策略排班模式之研究”，國立中央大學土木工程學系碩士論文。
顏上堯，林錦翌，民國86年，”空服員排班組合最佳化之研究”，中國土木水利工程學刊，第9卷第1期，頁303-313。
顏上堯，湯敦台，民國89年，”空服員整合排班模式之建立”，中國土木水利工程學刊（已接受）。

指導教授

顏上堯(Shang-Yao Yan)

審核日期

2000-7-10

推文