鐵路運輸系統運行需要乘務人員隨車值勤。乘務人員的適當排班因需要滿足多樣化的行車需求和複雜的排班規則，同時又影響營運效率，成為鐵路運營運中的重要挑戰。本研究以國營臺灣鐵路股份有限公司（下稱臺鐵）的乘務人員排班為目標，開發混合整數規劃數學模型。該模型考慮了臺鐵系統各種排班規則以及便乘與外站過夜時特殊工作時間計算方式，並以求解最佳化乘務人員的配置。減少總人力需求、縮小工作時間差異、減少加班時數為最佳化目標。
鐵路乘務人員排班問題具有NP-Hard性質，求解不易。本研究提出「多輪求解演算法」，透過多次迭代逐步改善解的品質，縮短求解時間並獲得高品質的可行解。為了驗證模型與演算法的適用性，本研究以臺鐵真實乘務數據進行測試，涵蓋小規模問題、嘉義運務段列車長排班，以及全臺車勤服務人員排班等情境。
測試結果顯示，該數學模型在不同問題規模下均具備良好的求解性能，可在短時間內提供高品質的排班方案。此外並以測試數據分析重排數量、求解回合數和目標函數設計等因素對求解效能的影響。研究並發現目標函數表述方式的小幅度差異有可能對求解速度造成顯著影響，可作為其他問題研究參考。

Railway operations require crew members to be on duty with the trains. Proper crew scheduling, which must meet diverse operational demands and complex scheduling rules while impacting operational efficiency, is a significant challenge in railway management. This study focuses on the crew scheduling of State-owned Taiwan Railway Corporation,Ltd (referred to as TR), a state-owned enterprise, by developing a mixed-integer programming (MIP) mathematical model. This model incorporates various scheduling rules of the TR system and includes special work-time calculations for deadhead travel and overnight stays at non-home bases, aiming to optimize crew allocation. The optimization objectives are to reduce overall manpower needs, minimize discrepancies in work hours, and decrease overtime.
The railway crew scheduling problem is NP-Hard, making it challenging to solve. This study proposes a multi-round algorithm that iteratively improves solution quality through multiple iterations, shortening solution time and yielding high-quality feasible solutions. To validate the model and algorithm's applicability, real crew data from TR is tested across different scenarios, including small-scale problems, the Chiayi district conductor scheduling, and full TR train attendant scheduling across Taiwan.
The test results show that the mathematical model performs well across different problem scales, providing high-quality scheduling solutions within a short time. Additionally, analysis of factors like reordering quantity, iteration rounds, and objective function design based on test data reveals their effects on solution efficiency. The study also finds that slight differences in the expression of the objective function can significantly impact solution speed, offering insights for other studies on similar problems.

[1] 交通部. "臺鐵(國情簡介-交通運輸) - 行政院全球資訊網." [Online]. Available: https://www.ey.gov.tw/state/A44E5E33CDA7E738/1f34ef94-2ff5-40ab-b526-e2fedd358a36
[2] E. Khmeleva, A. A. Hopgood, L. Tipi, and M. Shahidan, "Rail-freight crew scheduling with a genetic algorithm," in International Conference on Innovative Techniques and Applications of Artificial Intelligence: Springer, pp. 211-223, 2014.
[3] E. Abbink, D. Huisman, and L. Kroon, "Railway crew management," Handbook of optimization in the railway industry, pp. 243-264, 2018.
[4] G. Şahin and B. Yüceoğlu, "Tactical crew planning in railways," Transportation Research Part E: Logistics and Transportation Review, vol. 47, no. 6, pp. 1221-1243, 2011.
[5] S. Pang and M.-C. Chen, "Optimize railway crew scheduling by using modified bacterial foraging algorithm," Computers & Industrial Engineering, vol. 180, p. 109218, 2023.
[6] A. Balakrishnan, A. Kuo, and X. Si, "Real-time decision support for crew assignment in double-ended districts for US freight railways," Transportation Science, vol. 50, no. 4, pp. 1337-1359, 2016.
[7] S. T. Board. "Annual report financial data 2021." U.S. Department of Transportation, Washington, DC. [Online]. Available: https://www.stb.gov/reports-data/economic-data/annual-report-financial-data/
[8] A. Caprara, L. Kroon, M. Monaci, M. Peeters, and P. Toth, "Passenger railway optimization," Handbooks in operations research and management science, vol. 14, pp. 129-187, 2007.
[9] J. E. Beasley and B. Cao, "A tree search algorithm for the crew scheduling problem," European Journal of Operational Research, vol. 94, no. 3, pp. 517-526, 1996.
[10] J. Heil, K. Hoffmann, and U. Buscher, "Railway crew scheduling: Models, methods and applications," European journal of operational research, vol. 283, no. 2, pp. 405-425, 2020.
[11] A. T. Ernst, H. Jiang, M. Krishnamoorthy, B. Owens, and D. Sier, "An annotated bibliography of personnel scheduling and rostering," Annals of Operations Research, vol. 127, no. 1, pp. 21-144, 2004.
[12] A. Caprara, M. Fischetti, P. Toth, D. Vigo, and P. L. Guida, "Algorithms for railway crew management," Mathematical programming, vol. 79, pp. 125-141, 1997.
[13] A. T. Ernst, H. Jiang, M. Krishnamoorthy, and D. Sier, "Staff scheduling and rostering: A review of applications, methods and models," European journal of operational research, vol. 153, no. 1, pp. 3-27, 2004.
[14] M. Desrochers and F. Soumis, "A column generation approach to the urban transit crew scheduling problem," Transportation science, vol. 23, no. 1, pp. 1-13, 1989.
[15] J. Desrosiers, Y. Dumas, M. M. Solomon, and F. Soumis, "Time constrained routing and scheduling," Handbooks in operations research and management science, vol. 8, pp. 35-139, 1995.
[16] E. M. Morgado and J. P. Martins, "Scheduling and managing crew in the Portuguese railways," Expert Systems with Applications, vol. 5, no. 3-4, pp. 301-321, 1992.
[17] M. E. Parker, A. Wren, and R. S. Kwan, "Modelling the Scheduling of Itain Drivers," in Computer-Aided Transit Scheduling: Proceedings of the Sixth International Workshop on Computer-Aided Scheduling of Public Transport: Springer, pp. 359-370, 1995.
[18] A. Wren, R. S. Kwan, and M. E. Parker, "Scheduling of rail driver duties," WIT Transactions on The Built Environment, vol. 7, 1994.
[19] M. A. Boschetti, A. Mingozzi, and S. Ricciardelli, "An exact algorithm for the simplified multiple depot crew scheduling problem," Annals of Operations Research, vol. 127, pp. 177-201, 2004.
[20] A. A. Ceder and S. Hassold, "Applied analysis for improving rail-network operations," Journal of Rail Transport Planning & Management, vol. 5, no. 2, pp. 50-63, 2015.
[21] S. Chen and Y. Shen, "An improved column generation algorithm for crew scheduling problems," Journal of Information and Computational Science, vol. 10, no. 1, pp. 175-183, 2013.
[22] S. Jütte and U. W. Thonemann, "Divide-and-price: A decomposition algorithm for solving large railway crew scheduling problems," European Journal of Operational Research, vol. 219, no. 2, pp. 214-223, 2012.
[23] M. Fuentes, L. Cadarso, and Á. Marín, "A hybrid model for crew scheduling in rail rapid transit networks," Transportation Research Part B: Methodological, vol. 125, pp. 248-265, 2019.
[24] R. Hanafi and E. Kozan, "A hybrid constructive heuristic and simulated annealing for railway crew scheduling," Computers & Industrial Engineering, vol. 70, pp. 11-19, 2014.
[25] K. Hoffmann and U. Buscher, "Valid inequalities for the arc flow formulation of the railway crew scheduling problem with attendance rates," Computers & Industrial Engineering, vol. 127, pp. 1143-1152, 2019.
[26] S.-H. Huang, T.-H. Yang, and R.-T. Wang, "Ant colony optimization for railway driver crew scheduling: from modeling to implementation," Journal of the Chinese Institute of Industrial Engineers, vol. 28, no. 6, pp. 437-449, 2011.
[27] B. Vaidyanathan, K. C. Jha, and R. K. Ahuja, "Multicommodity network flow approach to the railroad crew-scheduling problem," IBM Journal of Research and Development, vol. 51, no. 3.4, pp. 325-344, 2007.
[28] A. Kumar, B. Vaidyanathan, K. C. Jha, and R. K. Ahuja, "Railroad Crew Scheduling," ed, 2009.
[29] Y. Shen, K. Peng, K. Chen, and J. Li, "Evolutionary crew scheduling with adaptive chromosomes," Transportation Research Part B: Methodological, vol. 56, pp. 174-185, 2013.
[30] A. Azadeh, M. H. Farahani, H. Eivazy, S. Nazari-Shirkouhi, and G. Asadipour, "A hybrid meta-heuristic algorithm for optimization of crew scheduling," Applied Soft Computing, vol. 13, no. 1, pp. 158-164, 2013.
[31] E. Balas and A. Ho, Set covering algorithms using cutting planes, heuristics, and subgradient optimization: a computational study. Springer, 1980.
[32] A. Caprara, "Timetabling and assignment problems in railway planning and integer multicommodity flow," Networks, vol. 66, no. 1, pp. 1-10, 2015.
[33] P. Alefragis, P. Sanders, T. Takkula, and D. Wedelin, "Parallel integer optimization for crew scheduling," Annals of Operations Research, vol. 99, pp. 141-166, 2000.
[34] A. Froger, O. Guyon, and E. Pinson, "A set packing approach for scheduling passenger train drivers: the French experience," in RailTokyo2015, 2015.
[35] S. Dauzère-Pérès, D. De Almeida, O. Guyon, and F. Benhizia, "A Lagrangian heuristic framework for a real-life integrated planning problem of railway transportation resources," Transportation Research Part B: Methodological, vol. 74, pp. 138-150, 2015.
[36] A. Caprara, M. Monaci, and P. Toth, "A global method for crew planning in railway applications," Computer-Aided Scheduling of Public Transport, pp. 17-36, 2001.
[37] R. Borndörfer, C. Schulz, S. Seidl, and S. Weider, "Integration of duty scheduling and rostering to increase driver satisfaction," Public Transport, vol. 9, pp. 177-191, 2017.
[38] J. Desrosiers and M. E. Lübbecke, "A primer in column generation," in Column generation: Springer, pp. 1-32, 2005.
[39] E. J. Abbink, L. Albino, T. Dollevoet, D. Huisman, J. Roussado, and R. L. Saldanha, "Solving large scale crew scheduling problems in practice," Public Transport, vol. 3, pp. 149-164, 2011.
[40] Y. Shen and S. Chen, "A column generation algorithm for crew scheduling with multiple additional constraints," Pacific Journal of Optimization, vol. 10, no. 1, pp. 113-136, 2014.
[41] M. Liu, A. Haghani, and S. Toobaie, "Genetic algorithm–based column generation approach to passenger rail crew scheduling," Transportation research record, vol. 2159, no. 1, pp. 36-43, 2010.
[42] J. García, F. Altimiras, A. Peña, G. Astorga, and O. Peredo, "A binary cuckoo search big data algorithm applied to large-scale crew scheduling problems," Complexity, vol. 2018, 2018.
[43] H. Snijders and R. L. Saldanha, "Decision support for scheduling security crews at Netherlands Railways," Public Transport, vol. 9, pp. 193-215, 2017.
[44] R. S. Kwan and A. Kwan, "Effective search space control for large and/or complex driver scheduling problems," Annals of Operations Research, vol. 155, no. 1, pp. 417-435, 2007.
[45] R. S. Kwan, "Case studies of successful train crew scheduling optimisation," Journal of Scheduling, vol. 14, no. 5, pp. 423-434, 2011.
[46] T. Nishi, Y. Muroi, and M. Inuiguchi, "Column generation with dual inequalities for railway crew scheduling problems," Public transport, vol. 3, pp. 25-42, 2011.
[47] W. Zhou, X. Yang, L. Deng, and J. Qin, "Crew scheduling considering both crew duty time difference and cost on urban rail system," Promet-Traffic&Transportation, vol. 28, no. 5, pp. 449-460, 2016.
[48] K. Hoffmann, U. Buscher, J. S. Neufeld, and F. Tamke, "Solving practical railway crew scheduling problems with attendance rates," Business & Information Systems Engineering, vol. 59, no. 3, pp. 147-159, 2017.
[49] J. Janacek, M. Kohani, M. Koniorczyk, and P. Marton, "Optimization of periodic crew schedules with application of column generation method," Transportation Research Part C: Emerging Technologies, vol. 83, pp. 165-178, 2017.
[50] A. K. Khosravi, M. T. Tamannaei, and M. Reisi-Nafchi, "A comprehensive approach for railway crew scheduling problem (case study: Iranian railway network)," International Journal of Transportation Engineering, vol. 4, no. 3, pp. 197-210, 2017.
[51] K. Peng and Y. Shen, "A variable iterated greedy algorithm based on grey relational analysis for crew scheduling," Scientia Iranica, vol. 25, no. 2, pp. 831-840, 2018.
[52] M. Banihashemi and A. Haghani, "A new model for the mass transit crew scheduling problem," in Computer-aided scheduling of public transport: Springer, pp. 1-15, 2001.
[53] A. Ç. Suyabatmaz and G. Şahin, "Railway crew capacity planning problem with connectivity of schedules," Transportation Research Part E: Logistics and Transportation Review, vol. 84, pp. 88-100, 2015.
[54] Z. Ercsey and Z. Kovács, "Multicommodity network flow model of a human resource allocation problem considering time periods," Central European Journal of Operations Research, pp. 1-19, 2023.
[55] 宋孟恒, "鐵路人員排班通用樣板模式," 碩士, 土木工程學系, 國立成功大學, 台南市, 2023. [Online]. Available: https://hdl.handle.net/11296/fx89p5
[56] M. Fischetti, A. Lodi, S. Martello, and P. Toth, "A polyhedral approach to simplified crew scheduling and vehicle scheduling problems," Management Science, vol. 47, no. 6, pp. 833-850, 2001.