跳到主要內容

臺灣博碩士論文加值系統

(54.83.119.159) 您好!臺灣時間:2022/01/17 08:32
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:王國琛
研究生(外文):Kuo-Chen Wang
論文名稱:結合限制規劃與數學規劃求解大型後艙空勤組員排班問題
論文名稱(外文):Applications of Constraint Programming and Mathematical Programming Techniques to Solve Large-Scale Cabin Crew Scheduling Problems
指導教授:韓復華韓復華引用關係
指導教授(外文):Anthony Fu-Wha Han
學位類別:碩士
校院名稱:國立交通大學
系所名稱:運輸科技與管理學系
學門:運輸服務學門
學類:運輸管理學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:132
中文關鍵詞:空勤組員排班勤務組合產生限制滿足問題限制規劃變數產生法
外文關鍵詞:Crew SchedulingPairing GenerationConstraint Satisfaction ProblemConstraint ProgrammingColumn GenerationConstrained Enumeration
相關次數:
  • 被引用被引用:44
  • 點閱點閱:1105
  • 評分評分:
  • 下載下載:221
  • 收藏至我的研究室書目清單書目收藏:3
空勤組員排班屬於NP-Hard之大型組合最佳化問題,也是航空公司營運規劃的重要課題,由於其實務問題之規模龐大計算複雜度高,故在作業研究領域中有諸多文獻探討。本研究將應用新近發展之限制規劃方法與傳統的數學規劃方法,求解大型後艙空勤組員排班問題。
CP源自於人工智慧領域,主要是用來求解限制滿足問題(CSP),此方法論之最大優點在於高度的模式彈性與快速的求解績效。一般而言,組員排班可分為「勤務組合產生」與「排班成本最小化」兩個部分。本研究將勤務組合產生問題視為一個CSP問題,並應用CP建立一個有效率的勤務組合產生模式(簡稱CSP模式),該模式能同時考慮各種排班法規(飛時、工時、休時)與營運因素(基地、機型接續、艙等、空載),故較傳統之勤務組合產生方法更具彈性。以CSP模式為基礎,將航段依班次頻率分類,再加上專家知識之限制式,構建一個CSP-CP模式來產生具有實用價值之受限性勤務組合集合(簡稱CP集合),期能有效地縮小最小成本問題之求解規模。
考慮實務問題規模通常屬於大型問題,本研究結合CSP-CP模式與MP模式建立一套以限制規劃為基礎之變數產生法。在績效比較方面,本研究採用兩篇文獻所使用之測試問題作為比較基準,其問題之實際規模分別為1.7*106與6*107。測試結果發現,此求解方法在兩個大型測試例題上所求得之最小成本皆優於文獻結果,其改善幅度分別為3%與2.7%,運算時間分別為23.9秒與203.2秒。此結果顯示,CSP-CP模式確實能有效地結合MP來求解大型後艙組員排班問題。
基於CSP-CP模式能有效地產生具實用性之受限性勤務組合,本研究亦根據CSP-CP模式列舉所有不含空載之基本勤務組合(Basic Pairing, BP)集合與恰含1個空載之延伸性勤務組合(Extended Pairing, EP)集合,直接作最小成本之優化。結果發現,此種限制列舉式之產生-優化法(Generate-and-Optimize),對兩個大型測試例題亦可不經由變數產生法的分解機制,直接求得相同最小成本的結果,由此可知,CSP-CP模式確實能有效地縮減問題規模並保持解之品質。
Because crew cost is only second to fuel in airline operations, the crew scheduling problem has been widely studied in the literature. Most existing literature on this problem is based on mathematical programming (MP) models. This research takes a new approach using constraint programming (CP) to complement MP in solving large-scale crew scheduling problems.
Essentially, a crew scheduling problem can be decomposed into a pairing generation problem, and a minimum-cost set partitioning problem (SPP). In this research, we took the pairing generation problem as a constraint satisfaction problem (CSP) and developed a CSP model to generate feasible pairings. Since the number of feasible pairings tends to be enormous, we developed a CSP-CP model to generate feasible constrained pairings (CP) by adding some expert-knowledge rules to CSP model.
Considering most crew scheduling problems in practice are large-scale, we combine the CSP-CP model and SPP model to develop a CP-based column generation method. To evaluate the performance of this method, we adopted two large-scale problems in literature as our test problems, each has a problem size of 1.7*106 and 6*107 respectively. Computational results showed that CP-based column generation yields an improvement of 3% and 2.7% over the published best-known solutions of the two test problems respectively. Such results imply that the CSP-CP model can be used to complement the MP in column generation effectively.
Because the CSP-CP model can effectively generate feasible pairings, we also applied the CSP-CP model to solve the crew scheduling problem in the “generate-and-optimize” framework. The generated CP includes a set of basic pairings (BP), each of which contains no deadheads, and a set of extended pairings, each of which contains exactly one deadhead. We found that the CP-based generate-and-optimize method yielded the same optimal costs as we obtained in the CP-based column generation method. Such results imply that the CSP-CP model may effectively reduce the problem size without losing solution quality in solving large-scale cabin crew scheduling problems.
中文摘要 Ⅰ
英文摘要 Ⅱ
誌謝 Ⅲ
目錄 IV
圖目錄 VII
表目錄 VIII
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的與範圍 3
1.3 研究方法與流程 3
第二章 文獻回顧 6
2.1 組員排班問題 6
2.1.1 勤務組合產生問題與求解方式 6
2.1.2 最小成本勤務組合產生問題 9
2.1.3 勤務組合產生問題之相關成計算 10
2.2 最小成本勤務組合產生問題特性之探討 12
2.3 最小成本勤務組合產生問題之求解演算法 15
2.3.1 啟發式解法 15
2.3.2 最佳解解法 16
2.4 變數產生法 18
2.4.1 以網路模式為基礎之變數產生法 19
2.4.2 以限制規劃為基礎之變數產生法 22
第三章 限制規劃文獻回顧 24
3.1 限制規劃簡介 24
3.2 限制滿足問題簡介 27
3.2.1 限制滿足問題之定義 27
3.2.2 限制滿足問題中之限制式種類 28
3.3 限制規劃中之求解演算法簡介 29
3.3.1 一致性檢驗技術介紹 29
3.3.2 空間搜尋演算法 32
3.3.2 空間搜尋演算法中之搜尋策略 37
3.4 限制規劃之整體求解機制 40
3.5 構建限制規劃模式所需考慮之因素 42
3.6 模式化語言OPL之簡介 46
第四章 一般化勤務組合產生問題限制規劃模式 47
4.1 勤務組合產生問題 47
4.1.1 問題描述 47
4.1.2 勤務型態 50
4.1.3 勤務組合型態 50
4.2 勤務組合產生問題所考慮之勤務組合集合 53
4.3 勤務組合產生問題之相關法規限制 54
4.4 勤務組合產生問題之成本計算方式 57
4.5 一般化勤務組合產生問題限制規劃模式 58
4.5.1 模式輸入資料 59
4.5.2 模式參數與變數 59
4.5.3 模式限制式 64
4.6 勤務組合集合產生架構 72
4.6.1 TP集合產生架構 72
4.6.2 CP集合產生架構 73
4.7 一般化勤務組合產生問題限制規劃模式之類型 77
4.7.1 窮舉式的勤務組合產生模式 77
4.7.2 限制列舉式的勤務組合產生模式 77
第五章 後艙空勤組員排班模式與求解架構 78
5.1 八種後艙空勤組員排班模式 78
5.2 排班模式求解架構 81
5.2.1 以限制規劃為基礎之變數產生法 81
5.2.1.1 起始解建構模組 83
5.2.1.2 子問題求解模組 83
5.2.2 限制列舉式之產生-優化法 85
第六章 實證分析 87
6.1 測試例題簡介 87
6.2 排班模式之測試-單基地、單機型接續、單艙等 87
6.2.1 排班資料 87
6.2.2 問題規模與最佳解 90
6.2.2.1問題規模-TP集合 90
6.2.2.2問題規模-CP集合 91
6.2.2.3問題之最佳解 91
6.2.3 測試結果與分析 92
6.3 排班模式之測試-多基地、多機型接續、多艙等 95
6.3.1 排班資料 95
6.3.2 問題規模與最佳解 98
6.3.2.1問題規模-TP集合 98
6.3.2.2問題規模-CP集合 99
6.3.2.3問題之最佳解 99
6.3.3測試結果與分析 100
第七章 結論與建議 105
7.1結論 105
7.2建議 107
參考文獻 108
附錄一 111
附錄二 114
1. Arabeyre, H. L., F. Fearrnley, C. Steiger, and W. Teather, “The Airline Crew Scheduling Problem:Survey,” Transp. Sci. 3, 140-163, 1969.
2. Anbil, R., E. Gelman, B. Patty, and R. Tanga, “Recent Advances in Crew-Pairing Optimization at American Airlines,” Interfaces, vol. 21 , pp. 62—74, 1991.
3. Andersson E., E. Housos, N. Kohl, and D. Wedlin, “Crew Pairing Optimization,” 1997.
4. Appelgren, L. H., “A Column Generation Algorithm for a Ship Scheduling Problem,” Transportation Science, vol 3, pp. 53-68 ,1969.
5. Amal de silva, “Bus Driver Duty Optimization by Combining Constraint Programming and Linear Programming”, ILOG(S) Pte Ltd. Singapore, 2000.
6. Bodin, L., B. Golden, A. Assad, and M. Ball, “Routing and Scheduling of Vehcles and Crews --- The State of the Art,” Computers & Operations Research, Vol. 10, No. 2, Ch.3.3.3, pp. 125-127, 1983.
7. Beasely J. E and B. Cao, “A Tree Search Algorithm for the Crew Scheduling Problem,” European Journal of Operational Research, vol. 94, no.3, pp. 517-526, 1996.
8. Barnhart, C., and R. Shenoi, "An Approximate Model and Solution Approach for the Long-Haul Crew Pairing Problem," Transportation Science, vol. 32, no. 3, pp. 221-231, August 1998.
9. Brailsford, S. C., C. N. Potts, B. M. Smith, “Constraint Satisfaction Problems:Algorithms and Applications,” European Journal of Operational Research 119, 557-581, 1999.
10. Barták Roman, On-Line Guide to Constraint Programming, http://ktiml.mff.cuni.cz/~bartak/constraints/ 1998.
11. Crainic, T. G. and J. Rouseau, “The Column Generation Principle and the Airline Crew Scheduling Problem,“ INFOR, vol. 25, no. 2, pp. 136-151 ,1987.
12. Dantzig, G. B. and P. Wolfe, “The Decomposition Algorithm for Linear Programming”, Operations Research, vol 8, pp. 101-111, 1960.
13. Desrochers, M. and F. Soumis, “A Column Generation Approach to the Urban Transit Crew Scheduling Problem,” Transportation Science, vol. 23, no. 1, pp. 1-13, 1989.
14. Desrochers, M., J. Gilbert, M. Sauve, F. Soumis, “Crew-Opt:Subproblem Modeling in a Column Generation Approach to Urban Crew Scheduling,” IN: DADUNA e WREN (Eds.) Computer-Aided Transit Scheduling, pp. 395-406. Lecture Notes in Economics and Mathematical System 386. Springer-Verlag, Berlin, 1992.
15. Desrosiers J., Y. Dumas, M. Desrochers, F. SOUMIS, B. Sanso and P. Trudeau, “A Breakthrough in Airline Crew Scheduling,” Proceedings of the 26th Annual Meeting of the Canadian Transportation Research, Québec, pp. 464-478, 1991.
16. Desrosiers J., M. Gamache, F. Soumis and G. Marquis, “A Column Generation Approach for Large-Scale Aircrew Rostering Problems,” Operations Research, vol. 47, no. 2, pp. 247-263, 1999.
17. Graves G.W., R.D. McBride and I. Gershkoff, “Flight Crew Scheduling,” Management Science, vol. 39, no. 6, pp. 736-745, 1993.
18. Gilmore, P. C. and R. E. Gomory, “A Linear Programming Approach to the Cutting-Stock Problem”, Operations Research, vol. 9, pp. 849-859 ,1961.
19. Hillier, F. S. and G. J. Lieberman, Introduction to Operations Research, McGraw-Hill, 1995.
20. Hoffman Karla L. and Padberg M.,”Solving Airline Crew Scheduling Problem by Branch-and-Cut,” Management Science, vol. 39, no. 6, pp. 657-682, 1993.
21. Halatsis C., P. Stamatopoulos, I. Karali, T. Bitsikas, G. Fessakis, A. Schizas, S. Sfakianakis, C. Fouskakis, T. Koukoumpetsos and D. Papageorgiou, "Crew Scheduling Based on Constraint Programming: The PARACHUTE Experience". Proceedings of the 3rd Hellenic-European Conference on Mathematics and Informatics HERMIS ''96, pp. 424-431, Athens, 1996.
22. Haralick, R. and G. Elliott, “Increasing Tree Search Efficiency for Constraint Satisfaction Problems,” Artifcial Intelligence, vol 14, pp. 263-313, 1980.
23. Lavoie, S., M. Minoux, and E. Odier, “A New Approach for Crew Pairing Problems by Column Generation with an Application to Air Transportation,” European Journal of Operational Research, vol. 35, pp. 45-58, 1988.
24. Levine, D. and Argonne, “Application of a Hybrid Genetic Algorithm to Airline Crew Scheduling”, Computers and Operations Research, vol. 23, pp. 547-558, 1996.
25. Lustig, Irvin J., J. F. Puget, “Program Does Not Equal Program: Constraint Programming and Its Relationship to Mathematical Programming,” Interfaces, vol. 31, Issue 6, pp. 29-53, 2001.
26. Minoux, M. “Column Generation Techniques in Combinatorial Optimization:A New Application to Crew Pairing Problems,” Proceedings XXIVth AGIFORMS Symposium, Strabosurg, France, 1984.
27. Marriott K. and P. J. Stuckey , Programming with Constraints, 1998.
28. Marsten, R. E. and F. Shepardson, “Exact Solution of Crew Scheduling Problems Using the Set Partitioning Model: Successful Applications,” Network, vol 11, pp. 165-177, 1981.
29. Nemhauser G.L. and L.A. Wolsey, “Integer and Combinatorial Optimization,” John Wiley & Sons, New York, 1993.
30. Niklas. K., “Application of OR and CP Techniques in a Real World Crew Scheduling System”, proceedings of CP-AI-OR’00, 2000.
31. Pulleyblank W. R, “The Airline Crew Pairing Optimization Problem,” ISTCS, 1996.
32. Pavlopoulou C., A. Gionis, P. Stamatopoulos and C. Halatsis, "Crew Pairing Optimization Based on CLP". Proceedings of the 2nd International Conference on the Practical Applications of Constraint Technology PACT ''96, pp. 191-210, London, 1996.
33. Tallys H. Yunes, Arnaldo V. Moura and Cid C. de Souza, “A Hybrid Approach for Solving Large Scale Crew Scheduling Problems”, August 1999.
34. Vance, P., E.L. Johnson, and G.L. Nemhauser, “Airline Crew Scheduling:A New Formulation and Decomposition Algorithm," Operations Research, vol. 45, no. 2, pp. 188-200, March-April 1997.
35. Vance, P.H., E.L., Johnson, G.L., Nemhauser, M.W.F., Savelsbergh, and Barnhart, C., "Branch-and-Price: Column Generation for Solving Huge Integer Programs," Operations Research, vol. 46, No. 3, pp. 316-329, May-June 1998.
36. Van Hentenryck P. , The OPL Optimization Programming Language, 1999.
37. Wren A. and D. O. Wren,”A Genetic Algorithm for Public Transport Driver Scheduling,“ Computers & Operations Research, vol 22, pp.101-110, 1995。
38. Young R. D., ”A Simplified Primal (All-Integer) Integer Programming Algorithm,” Operations Research vol 16, pp. 750-782, 1968.
39. Yan S., T.T. Tung, and Y.P. Tu, “Optimal Construction of Airline Individual Crew Pairings,” Computers & Operations Research, vol. 29, pp. 341-363, 2002.
40. 沈志展,(指導教授:韓復華),“民航空運排程分析模式之應用”,國立交通大學交通運輸研究所碩士論文,1991。
41. 林錦翌,(指導教授:顏上堯),“空服員排班組合最佳化之研究”,國立中央大學土木工程研究所,1995。
42. 湯敦台,(指導教授:顏上堯),“多基地空服員排班組合最佳化”,中華民國運輸學會第十一屆論文研討會論文集,pp. 73-84,1996。
43. 杜宇平,(指導教授:顏上堯),“空服員排班網路模式之研究”,國立中央大學土木工程學系博士論文,2000。
44. 盧宗成,(指導教授:王晉元),“捷運公司機員排班問題之研究-以台北捷運公司為例”,國立交通大學運輸工程與管理學系碩士論文,1999。
45. 蔡文昉,(指導教授:王晉元),“大眾運輸排班系統之研究”,國立交通大學運輸工程與管理學系碩士論文,2001。
46. 中華航空公司網站,http://www.china-airlines.com/。
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top