鐵路列車駕駛員排班規劃是屬於鐵路行車服務計畫的後置階段，前置規劃包括時刻表的產生、運行時空圖以及車輛使用計畫。考慮薪資、合理的工作、休息時間以及相關的行車作業規定等因素，使得列車駕駛員排班問題的困難度加深許多，因此尋求合適的演算方法配合電腦快速的演算效率來取代傳統人工作業的方式誠屬必要。
本論文研究對象以台鐵高雄機務段列車駕駛員排班作業為主，其排班作業內容可分為排班與輪班兩個階段。本研究則嘗試將排班與輪班兩階段整合為一個階段求解，將問題分為(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.謝欣宏，「台鐵司機員排班與輪班問題之研究--以基因演算法求解」，國立成功大學交通管理研究所碩士論文，民國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。