進階搜尋


 
系統識別號 U0026-0812200910374122
論文名稱(中文) 應用基因演算法於台鐵列車駕駛員排班與輪班整合問題之研究
論文名稱(英文) Application of genetic algorithms for integrated problem of TRA’s driver schedulimg and rostering
校院名稱 成功大學
系所名稱(中) 交通管理學系碩博士班
系所名稱(英) Department of Transportation & Communication Management Science
學年度 91
學期 2
出版年 92
研究生(中文) 張育彰
研究生(英文) Ju-Jang Jang
電子信箱 r5690101@mail.grad.ncku.edu.tw
學號 r5690101
學位類別 碩士
語文別 中文
論文頁數 131頁
口試委員 口試委員-陳信雄
口試委員-郭淑美
口試委員-邱素文
指導教授-李治綱
中文關鍵字 人員輪班  人員排班  集合涵蓋問題  基因演算法  不對稱推銷員巡迴問題 
英文關鍵字 Crew Scheduling  Crew Rostering  Set-Covering Problem  Asymmetric Traveling Salesman Problem  Genetic Algorithms 
學科別分類
中文摘要 鐵路列車駕駛員排班規劃是屬於鐵路行車服務計畫的後置階段,前置規劃包括時刻表的產生、運行時空圖以及車輛使用計畫。考慮薪資、合理的工作、休息時間以及相關的行車作業規定等因素,使得列車駕駛員排班問題的困難度加深許多,因此尋求合適的演算方法配合電腦快速的演算效率來取代傳統人工作業的方式誠屬必要。
本論文研究對象以台鐵高雄機務段列車駕駛員排班作業為主,其排班作業內容可分為排班與輪班兩個階段。本研究則嘗試將排班與輪班兩階段整合為一個階段求解,將問題分為(1)可行工作班集合產生階段與(2)排班與輪班整合求解階段,前者以網路產生啟發式來排除相關的限制條件並產生合法的工作班組合,再藉由控制參數從所有的工作班組合中篩選出績效較佳的可行工作班集合當作下一階段求解搜尋空間﹔在排班與輪班整合求解階段,將排班問題視為一集合涵蓋問題,從可行工作班集合中選擇能涵蓋到所有乘務的工作班解集合﹔輪班方面定義為不對稱的推銷員旅行問題,在所有工作班均需執行過一遍的概念下,求取總週期最小等目標。在這個階段以基因演算法來進行求解,並同時獲得排班表與輪班表。
在實證測試方面,整理了台鐵目前的排班資料與法規,分析其中的要點與限制,並將實際作業上的習慣融入演算法中,本研究最終得到以下幾點結論:
1.基因演算法求解結果雖無法證明其為最佳解,但卻能在短時間內得到許多績效不錯的近似解,較能反映實務上的需求。
2.研究結果證明可用基因演算法等啟發式方法來取代傳統人工作業方式,且能得到不錯的效果。
3.研究結果證明將排班與輪班兩階段整合成一階段是可行的,求解結果也比台鐵佳且不會比分開為兩階段求解來的差,整合求解除了可增加效率外亦可避免分開為兩階段求解可能產生互相衝突的現象發生。
英文摘要 Train driver scheduling is the later stage of operation planning process for railway industry. The preceding planning includes Time tabling, Train diagramming, and Vehicle scheduling. Owing to the restrictions of salary, reasonable working and rest time and driving regulations, train driver problem has become more complex than other kinds of public transportation driver problems. Therefore it’s quite necessary to find out an algorithm combined with rapid computation to replace manual operations.
In this thesis, we perform a driver scheduling problem of Taiwan Railway Administration in Kaohsiung depot as a case study, which includes two stages:Crew Scheduling and Crew Rostering. The main purpose of this research is try to solve these two problems in one stage. In order to do that, we divided the problem into two sections:(1)Shift Generation and (2)Crew Scheduling and Crew Rostering integration. In the first section, a network heuristic is used to eliminate related restrictions and produce a set of legal shifts. By means of control parameters, potential shifts with high performances are generated as searching space in next section. In the second section, crew scheduling problem can be defined as a Set-Covering Problem(SCP), in which select a set of shifts that can cover all trips from feasible shifts produced in section one. In Crew Rostering, we regard it as an Asymmetric Traveling Salesman Problem(ATSP). It can be solved after performing all shifts once, under the objective of minimum total cycle. We use Genetic Algorithms in both problems, and obtain scheduling table and rostering table at the same time.
In empirical study, we sort TRA's current scheduling data and rules, analyzing the main points and restrictions, so as to merge their operational priciples into algorithms. Finally, we conclude this research as follow:
(1) Although the solutions solved by genetic algorithms can not be proved the optimal solutions, but they can produce many good approximate solutions in a short time. Consequently, they are more suitable for practical problems.
(2) The results prove that genetic algorithms combined with heuristics can replace traditional manual operations and obtain better performances.
(3) This research proves that it's worked to integrate crew scheduling and crew rostering into one stage.The results are better than TRA and not worse than the results solved in two stages. Solving integration not only improves efficiency but also prevents possible conflicts that two-stage solving may bring.
論文目次 第一章緒論................................................................................................1
1-1 研究動機及目的...............................................................................1
1-2 研究範圍與限制...............................................................................3
1-3 研究方法...........................................................................................4
1-4 研究步驟與流程...............................................................................5
第二章文獻回顧........................................................................................7
2-1 人員排班問題之定義......................................................................7
2-2 人員排班問題之分類......................................................................7
2-3 人員排班問題演算法之探討..........................................................9
2-4 遺傳演算法......................................................................................12
2-4-1 簡介...........................................................................................12
2-4-2 優點與缺點...............................................................................13
2-4-3 演算機制...................................................................................14
2-4-4 演算程序...................................................................................18
2-4-5 基因演算法有關人員排班相關文獻.......................................19
2-5 小結..................................................................................................33
第三章個案描述與研究方法....................................................................34
3-1 台鐵司機員排班與輪班問題概念..................................................34
3-1-1 專有名詞簡介...........................................................................34
3-1-2 台鐵司機員排班與輪班問題之描述.......................................37
3-1-3 台鐵排班與輪班之相關規則與限制.......................................41
3-1-4 實務排班與輪班經驗...............................................................42
3-1-5 小結...........................................................................................43
3-2 可行工作班集合產生模式之構建..................................................43
3-2-1 模式構建之概念.......................................................................43
3-2-2 可行工作班產生演算法...........................................................44
3-3 基因演算機制之構建......................................................................53
3-3-1 模式概念...................................................................................53
3-3-2 基因演算法設計.......................................................................54
第4 章實證分析........................................................................................66
4-1 台鐵資料投入與分析.......................................................................66
4-1-1 乘務資料....................................................................................66
4-1-2 高雄機務段EA、EB 工作班資料...........................................70
4-1-3 工作班產生實證分析................................................................73
4-2 排班與輪班整合模式之實證分析...................................................75
4-2-1 投入之工作班資料....................................................................75
4-2-2 基因演算參數與方法之敏感度測試........................................77
4-3 GA 求解結果.....................................................................................90
4-3-1 排班結果比較............................................................................91
4-3-2 輪班結果比較............................................................................95
4-4 可行工作班集合與求解結果之探討..............................................96
4-5 小結...................................................................................................103
第五章結論與建議....................................................................................104
5-1 結論..................................................................................................104
5-2 建議...................................................................................................105
參考文獻..............................................................................................107
附錄A..................................................................................................109
附錄B..................................................................................................112
附錄C..................................................................................................120
附錄D..................................................................................................124
參考文獻 1.謝欣宏,「台鐵司機員排班與輪班問題之研究--以基因演算法求解」,國立成功大學交通管理研究所碩士論文,民國91年6月。
2.郭彥秀,「鐵路駕駛員排班問題之研究」,國立成功大學交通管理研究所碩士論文,民國89年7月。
3.廖學昌,「公車客運業人員排班問題之研究—以金門縣公車為例」,國立交通大學交通運輸研究所碩士論文,民國87年6月。
4.莊凱祥,「求解護理人員排班最佳化之研究—以遺傳演算法求解」,國立成功大學工業管理研究所碩士論文,民國90年6月。
5.連志平,「警察人員排班問題之研究」,國立交通大學運輸工程與管理系碩士論文,民國87年。
6.杜宇平,「空服員排班網路模式之研究」,國立中央大學土木工程學系博士論文,民國89年6月。
7.顏上堯、湯敦台,「多基地空服員排班組合最佳化」,中華民國運輸協會第十一界論文研討會,民國85年12月。
8.張劭卿、黃志威、蔡明汶,「台灣地區航空公司組員排班問題特性之研究—以前艙組員排班系統之構建為例」,南區資策會,民國90年。
9.盧宗成,「捷運司機員排班問題之研究-以台北捷運公司為例」,國立交通大學運輸工程與管理學系碩士論文,民國89年6月。
10.王勇華,「人員排班問題啟發式解法之應用」,交通大學土木工程研究所碩士論文,民國82年6月。
11.Buffa, E.S.”An Integrated Work Shift Scheduling System”, Decision Sciences ,1976, pp.620〜630。
12.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。
13.Roy, E.M. and Fred S. ,”Exact Solution of Crew Scheduling Problem Using Set Partitioning Model:Recent Successful Applications”,NETWORKS,Vol.11, 1981,pp.165〜177。
14.Wren,A. and Wren,D.O.”A Genetic Algorithms for Public Transport Driver Scheduling”,Computer Operations Research,Vol. 22,No. 1, 1995,pp.101〜110。
15.Caprara,A.,Fischetti,M.,Toth,P.,and Vigo,D.,”Modeling and Solving the Crew Rostering Problem”,Technical Repprt OR-95-6,DEIS University of Bologna 1995。
16.Gen,M. and Cheng.R.,”Genetic Algorithms and Engineering Design”,John Wiley & Sons,2000。
17.Zbigniew M.,”Genetic Algorithms + Data Structives = Evolution Programs” third,revised and extended edition 1996。
18.Beasley J.E. and Chu P.C.,”A genetic algorithms for the set covering problem”European Journal of Operetional Research 94 (1996) pp.392〜404。
19.Sangit C.and Cecilia C. and Lucy A.L.,”Genetic algorithms and traveling salesman problems”,European Journal of Operetional Research 94 (1996) pp.490〜510。
20.Levine D.,”Application of a Hybrid Genetic Algorithm to Airline Crew Scheduling”Computer Operations Research,Vol. 23,No. 61996,pp. 547〜558。
21.Kwan A.S.K.,”Train Driver Scheduling”,PhD thesis,University of Leeds School of Computer Studies,Auguest 1999。
22.David E.G.,”Genetic Algoruthms in Search,Optimization,and Machine Learning”,The University of Alabam,1953。
23.Tadahik M. and Hisao I. and Hideo T.,”Muti-Objective Genetic Algorithms And Its App;ications To Flowshop Scheduling”, Department of Industrial Engineering, Osaka Prefecture University, Gakuen-cho 1-1, Sakai, Osaka 593 Japan。
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2003-07-07起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2003-07-07起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw