運用啟發式變數產生法求解機組人員排班問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：13

、訪客IP：18.116.24.105

姓名

吳柏賢(Po-hsien Wu) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

運用啟發式變數產生法求解機組人員排班問題
(A Heuristic Column Generation to Solve Crew Scheduling Problem)

相關論文

★ 應用失效模式效應分析於產品研發時程之改善	★ 服務品質因子與客戶滿意度關係研究-以汽車保修廠服務為例
★ 家庭購車決策與行銷策略之研究	★ 計程車車隊派遣作業之研究
★ 電業服務品質與服務失誤之探討-以台電桃園區營業處為例	★ 應用資料探勘探討筆記型電腦異常零件-以A公司為例
★ 車用配件開發及車主購買意願探討(以C公司汽車配件業務為實例)	★ 應用田口式實驗法於先進高強度鋼板阻抗熔接條件最佳化研究
★ 以層級分析法探討評選第三方物流服務要素之研究-以日系在台廠商為例	★ 變動良率下的最佳化批量研究
★ 供應商庫存管理架構下運用層級分析法探討供應商評選之研究-以某電子代工廠為例	★ 台灣地區快速流通消費產品銷售預測模型分析研究–以聯華食品可樂果為例
★ 競爭優勢與顧客滿意度分析以中華汽車為例	★ 綠色採購導入對電子代工廠的影響-以A公司為例
★ 以德菲法及層級分析法探討軌道運輸業之供應商評選研究–以T公司為例	★ 應用模擬系統改善存貨管理制度與服務水準之研究-以電線電纜製造業為例

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 ( 永不開放)

摘要(中)

本篇論文主要是在探討運用啟發式變數產生法解決機組人員排班問題，在求解機組人員排班問題中，變數產生法將問題分為主問題及子問題，主問題為集合涵蓋問題，子問題為含資源限制的最短路徑問題，主問題我們運用簡算法進行求解，子問題則運用自行發展的啟發式演算法進行求解，本文的目標在於避免當問題比較大時，運用精確法求解子問題時發生維數災難，為了避免發生維數災難故本文使用啟發式演算法來求解子問題。

摘要(英)

This paper is mainly discussing the use of a heuristic column generation to solve crew scheduling problem. In solving crew scheduling problem column generation will divide the problem into master problem and sub problem. The master problem is set covering problem and the sub problem is a resource constraints shortest path problem. We use simplex method to solve master problem. The sub problem is solved by a heuristic which developed on my own. The objective of this paper is preventing the curse of dimensionality. When the problem is large and solving sub problem by exact method occur the curse of dimensionality. In order to provide the curse of dimensionality we use a heuristic method to solve sub problem.

關鍵字(中)

★ 機組人員排班問題
★ 變數產生法
★ 資源限制最短路徑問題
★ 啟發式演算法

關鍵字(英)

★ Crew scheduling problem
★ Column generation
★ Resource constraint shortest path problem
★ Heuristic approach

論文目次

中文摘要 I
Abstract II
Table of Content III
List of Figures V
List of Tables VI
Chapter 1 Introduction 1
1.1 Background and Motivation 1
1.2 Research Objectives 2
1.3 Research Framework 2
Chapter 2 Literature Review 4
2.1 Crew Scheduling 4
2.1.1 Feasible Crew Pairing 5
2.1.2 Crew Scheduling Network 6
2.2 Set Covering 9
2.3 Problem Formulation 10
2.4 Column Generation 11
2.4.1 Master Problem 14
2.4.2 Sub Problem 15
2.5 Resource Constraints Shortest Path Problem 17
Chapter 3 Methodology 19
3.1 The Crew Scheduling Problem 19
3.2 A Column Generation for the Crew Scheduling Problem 21
3.2.1 A set covering model 21
3.2.2 The Linear Set Covering Solution 22
3.3 A Heuristic Algorithm for solving sub problem 24
3.3.1 Algorithm 1 24
3.3.2 Algorithm 2 26
3.4 Steps for Solving Crew Scheduling Problems 28
3.4.1 An American Airlines Crew Scheduling Example 29
Chapter 4 Experimental Results 53
4.1 Example 1 53
4.2 Example 2 55
4.3 Example 3 57
4.4 Example 4 59
4.5 Computational Analysis 61
Chapter 5 Conclusions and Future Research 64
5.1 Conclusions 64
5.2 Future Research 64
Reference 65

參考文獻

Arabeyre, J. P., Fearnley, J., Steiger, F. C., & Teather, W., “The airline crew scheduling problem: A survey”, Transportation Science, Vol. 3 no.2, pp.140-163, 1969
Avella, P., Boccia, M., & Sforza, A., “A penalty function heuristic for the resource constrained shortest path problem.” European Journal of Operational Research, vol. 142, no. 2, pp.221-230, 2002
Beasley JE, Christofides N. “An algorithm for the resource constrained shortest path problem.” Networks, vol. 19, pp. 379–94, 1989.
Borndörfer, R., Schelten, U., Schlechte, T., & Weider, S. “A column generation approach to airline crew scheduling.” Operation Research Proceedings, Springer Berlin Heidelberg, pp. 343-348, 2005.
Dantzig, G. B., & Wolfe, P., “Decomposition principle for linear programs.” Operations Research, vol. 8, no. 1, pp. 101-111, 1960
Desrochers, M., & Soumis, F. “A column generation approach to the urban transit crew scheduling problem.” Transportation Science, vol. 23 no.1, pp.1-13, 1989.
Dijkstra, E.W., “A note on two problems in connexion with graphs” Numerische Mathematik, pp. 269-271, 1959.
Dror M. “Note on the complexity of the shortest path models for column generation in VRPTW” vol. 42, no. 5, pp.977–8., Operations Research 1994.
Dumitrescu, I., & Boland N. “Improved preprocessing, labeling and scaling algorithms for the weight-constrained shortest path problem.” Networks, vol. 42, no. 3, pp. 135–53, 2003.
Fu, L., Sun, D., & Rilett, L. R.,“Heuristic shortest path algorithms for transportation applications: State of the art” Computer and Operation Research vol: 33, pp. 3324-3343, 2006
Gerbracht, “A new algorithm for very large crew pairing problems” AGIFORS Proceedings, vol. 18, pp. 315–341, 1978.
Gueguen, C., Dejax, P., Gendreau, M., & Feillet, D., “An Exact Algorithm for the Elementary Shortest Path Problem with Resource Constraints: Application to some Vehicle Routing Problems” Networks, vol. 44, no. 3, pp. 216-229, 2004.
Handler, GY., & Zang, I., “A dual algorithm for the constrained shortest path problem.” Networks, vol. 10, pp. 293–310, 1980.
Holmberg, K., & Yuan, D., “A multicommodity network-flow problem with side constraints on paths solved by column generation.” INFORMS Journal on Computing, vol. 15, no. 1, pp.42-57, 2003.
Ioachim, I., Gelinas, S., Soumis, F., & Desrosiers, J., “A Dynamic Programming Algorithm for the Shortest Path Problem with Time Windows and Linear Node Costs,” Networks, Vol. 31, no. 3, pp. 193-204, 1997.
Jaffe, JM. “Algorithms for finding paths with multiple constraints.” Networks, vol. 14, pp. 95–116, 1984.
Jütte, S., & Thonemann, U. W., “Divide-and-price: A decomposition algorithm for solving large railway crew scheduling problems.” European Journal of Operational Research, vol. 219, no. 2, pp. 214-223, 2012
Lavoie, S., Minoux, M., & Odier. E., “A new approach for crew pairing problems by column generation with an application to air transportation”, European Journal of Operational Research, vol. 35 no.1, pp.45-58, 1988.
Mehlhorn, K., & Ziegelmann, M., “Resource Constrained shortest paths: in: Paterson M, editor. 7th annual European Symposium on Algorithms.” Lecture notes in computer science, vol. 1879. Springer-Verlag, Berlin., pp. 326–37, 2000.
Muter, İ., Birbil, Ş. İ., Bülbül, K., Şahin, G., Yenigün, H., Taş, D., & Tüzün, D., “Solving a robust airline crew pairing problem with column generation.” Computers & Operations Research, vol. 40, no. 3, pp. 815-830, 2013.
Nemhauser G.L. and L.A. Wolsey, “Integer and Combinatorial Optimization,” John Wiley& Sons, New York, 2014.
Rasmussen, M. S., Justesen, T., Dohn, A., & Larsen, J. “The home care crew scheduling problem: Preference-based visit clustering and temporal dependencies.” European Journal of Operational Research, vol. 219.no. 3, pp. 598-610, 2012
Ritish P.W. Oemraw, “ An Algorithm for Special Case Shortest Path Problems with Resource Constraints and Time-Based Costs” Adriana Gabor Remy Spliet, 2011
Rubin, J., “A technique for the solution of massive set covering problems, with application to airline crew scheduling”, Transportation Science, vol. 7, no.1, pp.34-48, 1973.
Vance, P., E.L. Johnson, & G.L. Nemhauser, “Airline Crew Scheduling：A NewFormulation and Decomposition Algorithm” Operations Research, vol. 45, no. 2, pp.188-200, March-April 1997.
Wolsey, L.A., “Integer Programming” Wiley, 1998
Yan, Shang-Yao, Tseng, Chih-Hwang, “An Integrated Study on Single-Fleet Routing and Flight Scheduling” Transportation Planning Journal, vol. 28, no. 4, pp.635-658, 1999

指導教授

葉英傑(Ying-chieh Yeh)

審核日期

2015-11-13

推文