摘 要

鐵路司機員排班規劃是屬於鐵路行車服務計畫的後置階段，前置規劃包括了時刻表的產生、運行時空圖以及車輛使用計畫。考慮薪資、合理的工作、休息時間、以及行車作業規定等因素，使得司機員排班問題的困難度加深許多，因此尋求合適演算方法配合電腦快速演算效率來代替人工作業誠屬必要。
本篇研究對象為高雄機務段司機員排班作業，其內容可以分為排班與輪班兩個階段。在排班方面，將問題分為(1)可行工作班產生與(2)工作班選擇兩個子問題處理，前者以網路產生啟發式方法來排除限制條件並產生合法的工作班組合，再藉由參數控制的方式從所有的工作班組合當中篩選出績效較佳的可行工作班集合；後者則視為一集合涵蓋問題，從可行工作班集合中選擇能涵蓋所有乘務的工作班解集合，基於多目標決策的需要，此步驟以基因演算法為主。在輪班方面，定義為改良式的推銷員旅行問題，在工作班均需執行過一遍的概念下，求取總週期最小等目標，這個階段也以基因演算法來求解。
在實證測試方面，整理了台鐵目前的排班資料與法規，分析其中的要點與限制，並將實際作業上的原則融入演算法中，本研究最終得到以下幾點結論：
(1) 對於實務問題，最佳化方法因模式表達方式的限制，所得到的結論可能不全然是決策者心中的理想結果。
(2) 基因演算法配合啟發式方法能考慮多個決策指標，並在短時間內能得到許多不錯的解，較能反映實務需要。
(3) 研究結果證明可用基因演算等啟發式方法來代替傳統人工作業方式，並能得到不錯效果。

關鍵字：人員排班、人員輪班、基因演算法、集合涵蓋問題、推銷員巡迴問題

Abstract

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 problem of Taiwan Railway Administration in Kaohsiung depot as a case study, including Crew Scheduling and Crew Rostering. In crew scheduling, the problem can be divided into two sections- (1) Shift Generation and (2) Shift Selection. In shift generation, we use a network heuristic to eliminate restrictions and produce a set of legal shifts. By the way of parameter control, potential shifts with high performances are generated. Shift selection is defined as a Set-Covering Problem (SCP). According to the properties of multi-objective, genetic algorithms is applied to choose a suitable shift set to cover all train trips. In crew rostering, we regard it as an improved Traveling Salesman Problem (TSP). In terms of performing all shifts once, we solve the problem under the objective of minimum cycle by genetic algorithms.
In the empirical study, this research integrates TRA’s current data and rules and combines algorithms with operational principles. Finally, we can make up some conclusions as follows:
(1) In real world, optimal methods aren’t an ideal way because of numerous limits of model formulation.
(2) Genetic algorithms accompanied with some heuristics can simultaneously consider multiple performance indices and produce many good solutions in a short time. Consequently, they are more suitable for practical problems.
(3) This research proves that we can use genetic algorithms combined with heuristics to replace traditional manual operations and obtain better results.

Keywords: Crew scheduling, Crew rostering, Genetic algorithms, Set-covering problem, Traveling salesman problem.

參考文獻
[1] 郭彥秀，「鐵路駕駛員排班問題之研究」，國立成功大學交通管理研究所碩士論文，民國八十九年七月。
[2] 杜宇平，「空服員排班網路模式之研究」，國立中央大學土木工程學系博士論文，民國八十九年六月。
[3] 莊凱翔，「求解護理人員排班最佳化之研究—以遺傳演算法求解」，國立成功大學工業管理研究所碩士論文，民國九十年六月。
[4] 廖學昌，「公車客運業人員排班問題之研究—以金門縣公車為例」，國立交通大學交通運輸研究所碩士論文，民國八十七年六月。
[5] 連志平，「警察人員排班問題之研究」，國立交通大學運輸工程與管理系碩士論文，民國八十七年。
[6] 顏上堯、湯敦台，「多基地空服員排班組合最佳化」，中華民國運輸學會第十一屆論文研討會，民國八十五年十二月。
[7] 芹沢邦夫，「乗務員應用」，株式会社—交友社，昭和54年5月。
[8] N. Abboud, M. Inuiguchi, M. Sakawa, and Y. Uemura, Manpower allocation using genetic annealing, European Journal of Operational Research, Vol. 111, 1998, pp.405-420.
[9] J. E. Beasely, and B. Cao, A Tree Search Algorithm for the Crew Scheduling Problem, European Journal of Operational Research, Vol. 94, No. 3, 1996, pp.517-526.
[10] J. E. Beasely, and P. C. Chu, A Genetic Algorithm for the Set Covering Problem, European Journal of Operational Research, Vol. 94, 1996, pp.392-404.
[11] 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.
[12] S. Chatterjee, C. Carrera, and L. A. Lynch, Genetic algorithms and traveling salesman problems, European Journal of Operational Research Vol. 93, 1996, pp.490-510.
[13] M. Gen, and R. Cheng, Genetic algorithms and engineering optimization, John Wiley & Sons, 2000.
[14] D. E. Goldberg, Genetic Algorithm in Search, Optimization and Machine Learning, Addison Wesley, New York, 1989.
[15] Haupt, L. Randy, and S. E. Haupt, Practical genetic algorithms, Wiley, New York, 1998.
[16] A. S. K. Kwan, Train Driver Scheduling. PhD thesis, University of Leeds School of Computer Studies, August 1999.
[17] H. C. Lau, On the Complexity of Manpower Shift Scheduling, Computers Operations Research, Vol.23, No.1, 1996, pp. 93-102.
[18] E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, The Traveling Salesman Problem — A Guided Tour of Combinatorial Optimization, John Wiley & Sons Ltd, 1985.
[19] D. Levine, Application of a Hybrid Genetic Algorithm to Airline Crew Scheduling, Computers Operations Research, Vol. 23, No. 6, 1996, pp.547-558.
[20] Z. Michalewicz, Genetic algorithms + data structures = evolution programs, 3rd rev. and extended ed., Springer-Verlag, 1996.
[21] 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.
[22] L. Qu, and R. Sun, A synergetic approach to genetic algorithms for solving traveling salesman problem, Information Sciences Vol. 117, 1999, pp.267-283.
[23] 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.