成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	劉哲旭 Liu, Che-Hsu
論文名稱：	列車駕駛員排班與輪班規則之探討─基因演算法之應用 A study on the scheduling and rostering rules of railway drivers─Using Genetic Algorithm
指導教授：	李治綱 Lee, Chi-Kang
學位類別：	碩士 Master
系所名稱：	管理學院 - 交通管理科學系 Department of Transportation and Communication Management Science
論文出版年：	2005
畢業學年度：	93
語文別：	中文
論文頁數：	124
中文關鍵詞：	排班、輪班、規則、基因演算法
外文關鍵詞：	Genetic Algorithm, Scheduling, Rostering, Rule
相關次數：	點閱：76 下載：4
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

　　在司機員排班的問題上，台鐵局依然以人工作業的方式來進行輪班表的制定，排班時所需參考遵守的相關規則，則是與工會長久以來協商所調整的結果。然而台鐵與工會的立場與目標相異，不論哪一方讓步或妥協，以至於改變規則中的某些條件，皆有可能使人事調整產生變化，進而影響整個排班與輪班的結果，其結果好壞卻無法事先得知。

　　本研究的目的，在於建構一套能夠簡化排班與輪班的複雜性，同時考量規則改變所造成的影響之模式，並求解出不同立場與目標下的排輪班結果與影響此結果的關鍵性規則。

　　本研究採用一套雙層的基因演算模式，外層為規則的選擇模式以挑選適合的規則組合；內層為工作班集合產生模式與排輪班模式以求解輪班表。外層以基因演算法建構規則的選擇方式，將挑選到的規則水準投入內層進行求解；內層以自行撰寫的啟發式演算法進行乘務的連結，篩選出具有高度可行性的工作班集合，接著以基因演算法建構排輪班的整合模式，藉此求得最終的輪班表。如此藉由內外兩層基因演算模式的求解與演化機制，求得台鐵與工會各自不同目標下的輪班表，並求得最佳的規則組合與找出最具影響力的關鍵性規則。實證分析中，可得以下結論：

1.規則水準的選擇上，以基因演算法可在不同目標下，產生比台鐵更具效率或更為安全的輪班結果，且僅須調整「平均每日工作時間」之規則。

2.影響效率及安全指標的關鍵性規則，乃在於對「休息時間」的規範與限制，本研究透過自行擬定的兩條新規則說明台鐵在休息時間的定義上，的確有不夠嚴謹之詬病。

　In the problem of railway drivers scheduling, Taiwan Railway Administration (TRA) still plan the rostering table in manual way. The rules which must obey when scheduling are the result of negotiation by TRA and the union. However, their standpoints and goals are quite different, and the effect of changing any rule is hard to know in advance.

　The object of this study is to construct a model which can simplify the complexity of scheduling and rostering, also measure the effect of changing rules, and use it to look for the rostering table in different position and the important rules which cause the effect.

　We establish a Bi-Level Genetic Algorithm (GA), the selection of rules is the upper-level problem, scheduling and rostering are the lower-level problem. In the upper-level, we use GA to select the rules as the input of lower-level. In the lower-level, we construct a heuristic algorithm to produce a set of legal shifts and then use GA to plan the rostering table. In empirical study, we conclude the research as follow:

1. In the problem of selecting rules, using GA can plan a more efficient or a safer rostering table than TRA, only if we change the rule about “average daily work time”.

2. The most important rule that affect and distinguish different goals as efficiency and safety is the restriction about “rest time” which is not carefully designed by TRA.

第一章  緒論.....................................7
1-1研究動機......................................7
1-2研究目的......................................8
1-3研究範圍與限制................................9
1-4研究方法......................................9
1-5研究步驟與流程...............................10
第二章  文獻回顧................................12
2-1人員排班問題之定義...........................12
2-2人員排班問題的種類...........................13
2-3人員排班問題之演算法.........................17
2-4排輪班規則相關之文獻.........................19
2-5基因演算法...................................21
2-5-1緣起與特性.................................21
2-5-2演算機制...................................22
2-5-3演算程序...................................27
2-6小結.........................................28
第三章  實務與資料說明..........................29
3-1台鐵司機員排班與輪班概念.....................29
3-1-1專有名詞介紹與背景描述.....................29
3-1-2排班與輪班過程說明.........................33
3-2規則變化影響描述.............................36
3-2-1範例一：改變第三條規則.....................36
3-2-2範例二：改變第一條規則.....................38
3-2-3本研究之目的...............................39
3-3台鐵資料分析.................................41
3-3-1乘務資料分析...............................41
3-3-2工作班資料分析.............................45
3-4小結.........................................46
第四章  模式建構................................47
4-1輪班表的分析.................................47
4-2元素的規則設計...............................49
4-2-1乘務的設計.................................52
4-2-2連續乘務的設計.............................54
4-2-3工作的設計.................................54
4-2-4工作班的設計...............................56
4-2-5休息的設計.................................59
4-2-6休憩的設計.................................60
4-2-7休假的設計.................................61
4-2-8規則組合...................................61
4-3外層基因演算模式(規則選擇)...................62
4-3-1編碼方式...................................62
4-3-2適存值.....................................63
4-3-3排序.......................................65
4-3-4選擇.......................................65
4-3-5交配.......................................67
4-3-6突變.......................................68
4-3-7取代.......................................69
4-4內層輪班表求解模式(工作班產生、排班與輪班)...69
4-4-1工作班產生模式.............................69
4-4-2排班與輪班模式.............................73
4-5小結.........................................75
第五章  實證分析................................77
5-1台鐵既有規則分析.............................77
5-1-1台鐵既有規則中不具敏感性的規則.............79
5-2模式參數敏感度測試...........................85
5-2-1交配機率(Pc=1.0 vs. Pc=0.5)................86
5-2-2突變機率(Pm=0.1 vs. Pm=0.05)...............87
5-2-3個體數目與演化代數(P=50，G=40 vs. P=20，G=100)..........................................88
5-2-4選擇型態與交配方式.........................89
5-2-5最終參數設定...............................91
5-3模式求解結果.................................92
5-3-1台鐵既有輪班表與規則說明...................92
5-3-2以效率為目標(輪班週期長度為適存值).........93
5-3-3以安全(穩定)為目標(以工作班開始時間變異為適存值).............................................94
5-3-4綜合整理...................................96
5-3-5多目標(依權重大小區別重視的目標)...........97
5-4小結........................................103
第六章  結論與建議.............................105
6-1結論........................................105
6-2建議........................................105
參考文獻.......................................107
附錄A..........................................110
附錄B..........................................113
附錄C..........................................116
                                    

1.張育彰，「應用基因演算法於台鐵列車駕駛員排班與輪班整合問題之研究」，國立成功大學交通管理研究所碩士論文，民國92年6月。
2.謝欣宏，「台鐵司機員排班與輪班問題之研究--以基因演算法求解」，國立成功大學交通管理研究所碩士論文，民國91年6月。
3.郭彥秀，「鐵路駕駛員排班問題之研究」，國立成功大學交通管理研究所碩士論文，民國89年7月。
4.杜宇平，「空服員排班網路模式之研究」，國立中央大學土木工程學系博士論文，民國89年6月。
5.莊凱祥，「求解護理人員排班最佳化之研究—以遺傳演算法求解」，國立成功大學工業管理研究所碩士論文，民國90年6月。
6.楊光宗，「警察派出所人員排班問題之研究」，國立海洋大學航運管理學研究所碩士論文，民國91年7月。
7.林詩芹，「以限制規劃構建全年無休服務人員排班模式-以客服人員排班為例」，國立交通大學運輸科技與管理學研究所碩士論文，民國92年6月。
8.蔡文昉，「大眾運輸排班系統之研究」，運輸工程與管理研究所，民國90年6月。
9.廖學昌，「公車客運業人員排班問題之研究—以金門縣公車為例」，國立交通大學交通運輸研究所碩士論文，民國87年6月。
10.Abboud, N., M. Inuiguchi, M. Sakawa, and Y. Uemura, “Manpower Allocation Using Genetic Annealing”, European Journal of Operational Research 111, 1998, 405-420.
11.Atlason, J., M.A. Epelman, and S.G. Henderson, “Call Center Staffing with Simulation and Cutting Plane Methods”, Annals of Operations Research 127, Special Issue on Staff Scheduling and Rostering, 2004, 333-358.
12.A. Wren, and D. O. Wren, “A Genetic Algorithm for Public Transport Driver Scheduling”, Computers Operations Research, Vol. 22, No. 1, 1995, PP. 101-110.
13.Bard, J., C. Binici, and A. de Silva, “Staff Scheduling at the United States Postal Service”, Computers and Operations Research 30(5), 2003, 745-771.
14.Barry Galef, Marc Shapiro, “Crash Course in Measurement: Developing Methods to Estimate Changes in Crash Probability for Commercial Truck Drivers Under New Hours of Service Regulations”, TRB Annual Meeting, 2005.
15.Beasely, J. E. and Cao, B., “A tree Search Algorithms for the Crew Scheduling Problem”, European Journal of Operational Research, Vol. 94, No. 3, 1996, pp. 517-526.
16.Caprara, A., M. Fischetti, P. Toth, D. Vigo, and P. Guida, “Algorithms for Railway Crew Management”, Mathematical Programming 79(1-3), 1997, 125-141.
17.Chu, S.C.K., and Chan, E.C.H., “Crew scheduling of light rail transit in Hong Kong from modeling to implementation”, Computers Operations Research, Vol. 25, No. 11, 1998, pp. 887-894.
18.D. Levine, “Application of a Hybrid Genetic Algorithm to Airline Crew Scheduling”, Computers Operations Research, Vol. 23, No. 6, 1996, pp. 547-558.
19.Ernst, A., P. Hourigan, M. Krishnamoorthy, G. Mills, H. Nott, and D. Sier., “Rostering Ambulance Officers”, In Proceedings of the 15th National Conference of the Australian Society for Operations Research, Gold Coast, 1999, PP. 470-481.
20.Ernst, A., H. Jiang, M. Krishnamoorthy, and D. Sier., “Staff Scheduling and Rostering: A Review of Applications, Methods and Models”, European Journal of Operations Research 153, 2004, 3-27
21.Eveborn, P. and M. Ronnqvist, “Scheduler-A System for Staff Planning”, Annals of Operations Research 128, Special Issue on Staff Scheduling and Rostering, 2004, 21-45.
22.Fahle, T. and S. Bertels, “A Hybrid Setup for a Hybrid Scenario: Combining Heuristic for the Home Health Care Problem”, Working Paper, 2002.
23.Hao, G., K.K. Lai, and M. Tan, “A Neural Network Application in Personnel Scheduling”, Annals of Operations Research 128, Special Issue on Staff Scheduling and Rostering, 2004, 65-90.
24.H. T. Ozdemir, and K. M. Mohan, “Flight graph based genetic algorithm for crew scheduling in airline”, Information Sciences Vol. 133, 2001, pp. 165-173.
25.Laurence R. Hartley, Pauline Arnold, “Managing Fatigue in the Road Transport Industry: An Occupational Safety and Health Solution”, Stress, Workload, and Fatigue, 2001, 531-549.
26.Mould, G., “Case Study of Manpower Planning for Clerical Operations”, Journal of the Operational Research Society 47(3), 1996, 358-368.
27.Sang-Woo Park, Aviroop Mukherjee, Frank Gross, Paul P. Jovanis Ph. D., “Safety Implications of Multi-day Schedules for Truck Drivers: Comparison of Field Experiments and Crash Data Analysis”, TRB Annual Meeting, 2005.
28.Vairaktarakis, G., X. Cai, and C. Lee, “Workforce Planning in Synchronous Production Systems”, European Journal of Operational Research 136(3), 2002, 551-572.
29.Weir, J.D. and E.L. Johnson, “A Three-Phase Approach to Solving the Bidline Problem”, Annals of Operations Research 127, Special Issue on Staff Scheduling and Rostering, 2004, 283-308.
30.網站資料，http://www.ranknfile-ue.org/index.html

校內：立即公開
校外：2005-08-05公開

簡易檢索 / 詳目顯示

相關論文