臺灣博碩士論文加值系統

本研究以台灣鐵路管理局列車長排班與輪班問題為研究對象。列車長排班為鐵道行車服務管理計畫的最後階段，在列車時刻表已在前置的規劃作業中確立的狀況下，如何在遵守工作規則下排出合理的輪班表成為一大難題。傳統人工作業將每日排班與輪班分別施作，除了作業困難以外也可能造成人力的浪費，整合為一階段求解問題可更有效率的規劃人員使用計畫。本研究以台鐵高雄運務段乘務人員排班為例，建立排班及輪班問題整合的整數規劃模式，並設計演算法求解，同時比較傳統作法與整合求解方式之結果，實證研究結果顯示此演算法可運用於實例、且整合模式較能有效運用人力。

Train crew management is an imperative task in a passenger railway system and is typically decomposed into two sub-problems: crew scheduling problem and crew rostering problem. The decomposition can make the problem easier to solve but may produce degraded solutions. In this research, we propose a formulation to integrate these two critical sub-problems and develop a branch-and-price-and-cut (BPC) and a depth-first search-based (DFS-based) algorithm to solve the composite problem. The numerical results show that an integrated framework can yield better solutions than the decomposition strategy. Furthermore, the proposed BPC can solve real-world problems and obtain scheduling/rostering plans that are at least as good as those developed by the rail company. Finally, results also show that the rostering constraints have a more notable effect on the results compared to scheduling constraints in the integrated framework. This type of observation can only be accurately characterized when these two sub-problems are considered in an integrated manner.

Table of Contents
List of Tables iii
List of Figures iv
1. INTRODUCTION 1
1.1 Research Background and Motivation 1
1.2 Research Objective 2
1.3 Research Flow Chart 3
2. LITERATURE REVIEW 5
2.1 Crew Scheduling and Rostering Problem 5
2.2 Proposed Model and Solution Algorithm 7
2.2.1 Crew Scheduling Problem 7
2.2.2 Crew Rostering Problem 7
2.2.3 Integrated Problem 8
2.3 Summary 10
3. MATHEMATICAL FORMULATION 10
3.1 Problem Statement 11
3.2 Rules for Scheduling and Rostering 15
3.3 Mathematical Formulation of Integrated Scheduling and Rostering Problem 16
3.4 Summary 27
4. A BRANCH-AND-PRICE-AND-CUT ALGORITHM 28
4.1 Overall Algorithmic Process 28
4.2 Initial Feasible Solution 30
4.3 Restricted Master Program (RMP) 33
4.4 Pricing Program 36
4.5 Cut Generation 40
5. A DEPTH-FIRST SEARCH BASED ALGORITHM 43
5.1 Depth-First Search algorithm 43
5.2 DFS-based algorithm 45
6. EMPIRICAL STUDY 47
6.1 Validation 47
6.2 Sensitivity analysis 50
7. CONCLUDING REMARKS 54
REFERENCE 55

1.Bach, L., Dollevoet, T., ＆ Huisman, D. (2016). Integrating Timetabling and Crew Scheduling at a Freight Railway Operator. Transportation Science, 50(3), 878-891.
2.Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., ＆ Vance, P. H. (1998). Branch-and-Price: Column Generation for Solving Huge Integer Programs. Operations Research, 46(3), 316-329. doi: 10.1287/
3.Bartholdi, J. J. (1981). A Guaranteed-Accuracy Round-Off Algorithm for Cyclic Scheduling and Set Covering. Operations Research, 29(3), 501-510.
4.Bianco, L., Bielli, M., Mingozzi, A., Ricciardelli, S., ＆ Spadoni, M. (1992). A Heuristic-Procedure for the Crew Rostering Problem. European Journal of Operational Research, 58(2), 272-283.
5.Bussieck, M. R., Winter, T., ＆ Zimmermann, U. T. (1997). Discrete optimization in public rail transport. Mathematical Programming, 79, 415-444.
6.Caprara, A., Fischetti, M., Guida, P. L., Toth, P., ＆ Vigo, D. (1999). Solution of large-scale railway crew planning problems: the Italian experience. Computer-Aided Transit Scheduling, Proceedings, 471, 1-18.
7.Caprara, A., Fischetti, M., Toth, P., Vigo, D., ＆ Guida, P. L. (1997). Algorithms for railway crew management. Mathematical Programming, 79(1-3), 125-141.
8.Caprara, A., Toth, P., Vigo, D., ＆ Fischetti, M. (1998). Modeling and solving the crew rostering problem. Operations Research, 46(6), 820-830.
9.Chu, S. C. K., ＆ Chan, E. C. H. (1998). Crew scheduling of light rail transit in Hong Kong: From modeling to implementation. Computers ＆ Operations Research, 25(11), 887-894.
10.Ernst, A. T., Jiang, H., Krishnamoorthy, M., Nott, H., ＆ Sier, D. (2001). An integrated optimization model for train crew management. Annals of Operations Research, 108(1-4), 211-224.
11.Ernst, A. T., Jiang, H., Krishnamoorthy, M., ＆ Sier, D. (2004). Staff scheduling and rostering: A review of applications, methods and models. European Journal of Operational Research, 153(1), 3-27.
12.Freling, R., Lentink, R. M., ＆ Wagelmans, A. P. M. (2004). A decision support system for crew planning in passenger transportation using a flexible branch-and-price algorithm. Annals of Operations Research, 127(1-4), 203-222.
13.Ghoseiri, K., Szidarovszky, F., ＆ Asgharpour, M. J. (2004). A multi-objective train scheduling model and solution. Transportation Research Part B-Methodological, 38(10), 927-952.
14.Hoffmann, K., Buscher, U., Neufeld, J. S., ＆ Tamke, F. (2017). Solving Practical Railway Crew Scheduling Problems with Attendance Rates. Business ＆ Information Systems Engineering, 59(3), 147-159.
15.Huisman, D. (2007). A column generation approach for the rail crew re-scheduling problem. European Journal of Operational Research, 180(1), 163-173.
16.Huisman, D., Kroon, L. G., Lentink, R. M., ＆ Vromans, M. J. C. M. (2005). Operations Research in passenger railway transportation. Statistica Neerlandica, 59, 467-497.
17.Jutte, S., Albers, M., Thonemann, U. W., ＆ Haase, K. (2011). Optimizing Railway Crew Scheduling at DB Schenker. Interfaces, 41(2), 109-122.
18.Kohl, N., ＆ Karisch, S. E. (2004). Airline Crew Rostering: Problem Types, Modeling, and Optimization. Annals of Operations Research, 127, 223-257.
19.Kwan, R. S. K. (2011). Case studies of successful train crew scheduling optimisation. Journal of Scheduling, 14(5), 423-434.
20.Lezaun, M., Perez, G., ＆ de la Maza, E. S. (2007). Rostering in a rail passenger carrier. Journal of Scheduling, 10(4-5), 245-254.
21.Lin, D. Y. (2014). A Dantzig-Wolfe decomposition algorithm for the constrained minimum cost flow problem. Journal of the Chinese Institute of Engineers, 37(5), 659-669.
22.Liu, M., Haghani, A., ＆ Toobaie, S. (2010). Genetic Algorithm-Based Column Generation Approach to Passenger Rail Crew Scheduling. Transportation Research Record(2159), 36-43.
23.Möller, J. (2002). Seminar on Algorithms and Models for Railway Optimization Crew scheduling. University of Konstanz, ller-seminar.
24.Nishi, T., Sugiyama, T., ＆ Inuiguchi, M. (2014). Two-level decomposition algorithm for crew rostering problems with fair working condition. European Journal of Operational Research, 237(2), 465-473.
25.Potthoff, D., Huisman, D., ＆ Desaulniers, G. (2010). Column Generation with Dynamic Duty Selection for Railway Crew Rescheduling. Transportation Science, 44(4), 493-505.
26.Rezanov, N. J., ＆ Ryan, D. M. (2010). The train driver recovery problem-A set partitioning based model and solution method. Computers ＆ Operations Research, 37(5), 845-856.
27.Saddoune, M., Desaulniers, G., Elhallaoui, I., ＆ Soumis, F. (2012). Integrated Airline Crew Pairing and Crew Assignment by Dynamic Constraint Aggregation. Transportation Science, 46(1), 39-55. doi: 10.1287/trsc.1110.0379
28.Souai, N., ＆ Teghem, J. (2009). Genetic algorithm based approach for the integrated airline crew-pairing and rostering problem. European Journal of Operational Research, 199(3), 674-683. doi: 10.1016/j.ejor.2007.10.065
29.Taiwan-Railway-Administration. (2013). Specific Costs and Results of Various Countries. Statical Report of TRA. 2014, from http://www.railway.gov.tw/Upload/intro/file/YearReport/t65.pdf
30.Taiwan-Railway-Administration. (2017). Volume of Passenger Traffic. Statical Report of TRA. 2018, from https://www.railway.gov.tw/Upload/UserFiles/10703tt1.pdf
31.Tarjan, R. (1972). Depth-First Search and Linear Graph Algorithms. SIAM Journal on Computing, 1(2), 146-160.
32.Veelenturf, L. P., Potthoff, D., Huisman, D., ＆ Kroon, L. G. (2012). Railway crew rescheduling with retiming. Transportation Research Part C-Emerging Technologies, 20(1), 95-110.