臺灣博碩士論文加值系統

摘 要

鐵路司機員排班規劃是屬於鐵路行車服務計畫的後置階段，前置規劃包括了時刻表的產生、運行時空圖以及車輛使用計畫。考慮薪資、合理的工作、休息時間、以及行車作業規定等因素，使得司機員排班問題的困難度加深許多，因此尋求合適演算方法配合電腦快速演算效率來代替人工作業誠屬必要。
本篇研究對象為高雄機務段司機員排班作業，其內容可以分為排班與輪班兩個階段。在排班方面，將問題分為(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
1-1 研究背景 1
1-2 研究目的 3
1-3 研究範圍與限制 3
1-4 研究方法 5
1-5 研究步驟與流程 5
第二章 文獻回顧 8
2-1人員排班的定義 8
2-2人員排班問題的種類 8
2-3 數學背景 9
2-4 人員排班文獻 10
2-5 遺傳演算法 12
2-5-1 緣起與特性 12
2-5-2 演算機制 13
2-5-3 演算程序 17
2-5-4 相關人員排班文獻 18
2-6 小結 21
第三章 台鐵司機員排班與輪班概念 24
3-1專有名詞 24
3-2排班背景與概念 26
3-3 作業規則與限制 31
3-4 車輛運用與排班之相關課題 32
3-5 實務排班與輪班經驗 34
3-5 小結 36
第四章 司機員排班模式 37
4-1 排班模式架構 37
4-2 可行工作班產生模式 37
4-2-1模式概念 37
4-2-2啟發式演算法 39
4-3 工作班選擇模式 45
4-3-1 模式概念 45
4-3-2 數學模式 46
4-3-3 基因演算法 49
4-4 台鐵資料的投入與分析 57
4-4-1 乘務資料 57
4-4-2 站間里程 60
4-4-3 不同車種之乘務工作分析 61
4-4-4 高雄機務段EA、EB工作班資料 62
4-4-5 工作班屬性資料分析 64
4-5 工作班產生模式實證分析 65
4-5-1 可行工作班產生結果 66
4-5-2工作效率策略與乘務分佈控制 67
4-5-3 不同的策略下工作班集合測試 70
4-6 工作班選擇模式實證分析 73
4-6-1 投入資料 73
4-6-2 基因演化參數之敏感度測試 74
4-6-3 各單一目標策略求解 80
4-6-4 多目標權重的決定 84
4-6-5 多目標求解結果 86
4-7 最佳解比較 87
4-8 小結 89
第五章 司機員輪班模式 91
5-1 輪班概念與TSP模式 91
5-2 GA應用於TSP問題 92
5-3 輪班數學模式 94
5-3-1模式概念 94
5-3-2變數說明 95
5-3-3數學模式 96
5-3-4模式說明 97
5-4 基因演算法設計 98
5-5 輪班模式實證分析 105
5-5-1投入資料 105
5-5-2 基因演化參數之敏感度測試 105
5-5-3以台鐵EA、EB工作班集合為投入之求解結果 109
5-5-4以本研究產生的工作班集合為投入之求解結果 110
5-5 小結 111
第六章 結論與建議 113
6-1 結論 113
6-2 建議 114
參考文獻 115
附錄A 117
附錄B 120
附錄C 128
附錄D 137
附錄E 144

參考文獻
[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.