鐵路運輸系統是陸地上最重要的運輸系統之一。目前多數鐵路運輸系統在正常運轉時均需要乘務人員隨車值勤。乘務人員排班問題指派乘務人員至所有需要人員執勤的鐵路旅程段，為鐵路系統運營時的重要議題之一。基於不同鐵路系統各自的特性，乘務人員排班問題各有不同的實務規則。為適應各式乘務人員排班問題，目前的研究中仍以不同的數學模式解決此問題。
本研究提出一個能表現所有鐵路乘務人員排班問題共通性的數學模型，標準化的樣板形式呈現所需要的限制式，使問題得以參數化。應用時則可利用標準程序將樣板展開為具體的限制式。本研究以兩個鐵路的乘務人員排班之實務規則測試此數學模型之可行性，並以其中一系統的測資探討可能影響求解效率之因素。經檢視，文獻中所見之實務規則亦不出樣板所能表現之範圍。
測試結果發現本數學模型在求解不同規則、不同規模問題時會有各種求解績效。整體而言需要人員執勤的乘務段數量低於50時，可在短時間內得到最佳解或一定品質的排班結果。運用此方法，配合排班問題與樣板之間以及樣板與限制式之間的自動化轉換程序，可大幅提高研究工作以及實務應用的效率。

The railway transportation system is one of the most significant modes of land transportation. Currently, most railway systems require crew members to be on board during regular operations. The crew scheduling problem involves the assignment of crew members to all railway journey segments that require personnel duty, making it a crucial issue in railway system operations. Due to the diverse characteristics of different railway systems, there are various practical rules associated with the crew scheduling problem. Current research addresses this issue using different mathematical models to accommodate the variations.

This study introduces a mathematical model that captures the common aspects of all crew scheduling problems in railways. By presenting the required constraints in a standardized template form, the problem can be parameterized. During application, the template can be unfolded into specific constraints using standard procedures. The feasibility of this mathematical model is tested with the practical rules of crew scheduling for two railway systems. The study also explores factors that could influence solution efficiency using the test data from one of the systems. Upon examination, it is noted that the practical rules found in literature fall within the scope that the template can represent.

The test results reveal that the performance of this mathematical model varies when solving problems with different rules and scales. Generally, when the number of crew duty segments is less than 50, optimal or certain quality scheduling results can be obtained within a short time. The application of this approach, in conjunction with the automated conversion process between scheduling problems and templates, as well as between templates and constraints, can significantly enhance the efficiency of both research work and practical applications.

[1] E. Abbink, D. Huisman, and L. Kroon, "Railway crew management," Handbook of optimization in the railway industry, pp. 243-264, Art no., 2018.
[2] 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, Art no., 2011.
[3] 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, Art no., 2016.
[4] M. Banihashemi and A. Haghani, "A new model for the mass transit crew scheduling problem," Computer-aided scheduling of public transport, pp. 1-15, Art no., 2001.
[5] L. Bengtsson, R. Galia, T. Gustafsson, C. Hjorring, and N. Kohl, "Railway crew pairing optimization," in Algorithmic Methods for Railway Optimization: International Dagstuhl Workshop, Dagstuhl Castle, Germany, June 20-25, 2004, 4th International Workshop, ATMOS 2004, Bergen, Norway, September 16-17, 2004, Revised Selected Papers: Springer, pp. 126-144, 2007.
[6] 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, no. 1-4, pp. 177-201, Art no., 2004.
[7] 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, Art no., 2007.
[8] 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, Art no., 2001.
[9] 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, Art no., 2015.
[10] 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, Art no., 2013.
[11] S. Chen, Y. Shen, X. Su, and H. Chen, "A Crew Scheduling with Chinese Meal Break Rules," Journal of Transportation Systems Engineering and Information Technology, vol. 13, no. 2, pp. 90-95, Art no., 2013/04/01/ 2013, doi: https://doi.org/10.1016/S1570-6672(13)60105-1.
[12] K.-L. Chew, J. Pang, Q. Liu, J. Ou, and C.-P. Teo, "An optimization based approach to the train operator scheduling problem at Singapore MRT," Annals of operations Research, vol. 108, no. 1-4, pp. 111-122, Art no., 2001.
[13] U. Derigs, D. Malcherek, and S. Schäfer, "Supporting strategic crew management at passenger railways—model, method and system," Public transport, vol. 2, pp. 307-334, Art no., 2010.
[14] R. Elizondo, V. Parada, L. Pradenas, and C. Artigues, "An evolutionary and constructive approach to a crew scheduling problem in underground passenger transport," Journal of Heuristics, vol. 16, pp. 575-591, Art no., 2010.
[15] A. T. Ernst, H. Jiang, M. Krishnamoorthy, H. Nott, and D. Sier, "An Integrated Optimization Model for Train Crew Management," Annals of Operations Research, vol. 108, no. 1, pp. 211-224, Art no., 2001/11/01 2001, doi: 10.1023/A:1016019314196.
[16] Z. Feng and X. Ruihua, "Study on model and algorithm for urban rail transit crew scheduling system," in 2010 International Conference On Computer Design and Applications, vol. 5: IEEE, pp. V5-213-V5-216, 2010.
[17] 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, Art no., 2001.
[18] L. R. Ford, "Network flow theory," in Technical report. Santa Monica, California: Rand Corporation, pp. -923, 1956.
[19] R. Freling, R. M. Lentink, and M. A. Odijk, "Scheduling Train Crews: A Case Study for the Dutch Railways," in Computer-Aided Scheduling of Public Transport, S. Voß and J. R. Daduna Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 153-165, 2001.
[20] A. Froger, O. Guyon, and E. Pinson, "A set packing approach for scheduling passenger train drivers: the French experience," in RailTokyo2015, Tokyo, Japan, Mar 2015.
[21] 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, Art no., 2019.
[22] C. G. Guillermo and M. R. L. José, "Hybrid algorithm of tabu search and integer programming for the railway crew scheduling problem," in 2009 Asia-Pacific Conference on Computational Intelligence and Industrial Applications (PACIIA), vol. 2: IEEE, pp. 413-416, 2009.
[23] A. F. Han and E. C. Li, "A constraint programming-based approach to the crew scheduling problem of the Taipei mass rapid transit system," Annals of Operations Research, vol. 223, no. 1, pp. 173-193, Art no., 2014, doi: 10.1007/s10479-014-1619-1.
[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, Art no., 2014.
[25] 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, Art no., 2020, doi: 10.1016/j.ejor.2019.06.016.
[26] 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, Art no., 2019.
[27] 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, Art no., 2011.
[28] 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, Art no., 2012.
[29] 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.
[30] 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, Art no., 2011.
[31] B. Vaidyanathan and R. K. Ahuja, "Crew scheduling problem," in Handbook of operations research applications at railroads: Springer, pp. 163-175, 2015.
[32] 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, Art no., 2007, doi: 10.1147/rd.513.0325.