軌道運輸於台灣之中長程大眾運輸環境占相當重要的地位，而台鐵之發展歷史最為悠久，由於其多車種、多站等之營運特性，列車運行環境極為複雜，所有列車皆仰賴時刻表進行運轉發車，而制定時刻表之基礎其中一項為列車服務計畫，其為決定各車種列車之停站方式，如何有效率的進行規劃則為重要的課題。
目前台鐵列車停站方式為人工指派之方式進行排定，而本研究以數學規劃之工具建立一混合整數規劃之列車停站模式，再利用套裝軟體CPLEX以及基因演算法求解模式，當問題規模擴增時，CPLEX之求解速度以非線性倍數上升，因此本研究發展演算法以基因演算法、拉氏鬆弛法以及改良之分支界定法所組合成之求解策略求解較大規模之問題，並且進行數值分析。
實驗結果發現建立數學模式進行系統性的規劃求解，與人工指派之方式相較之下，可更為有效率以及彈性地進行各情境之結果比對，而數值分析之結果顯示決策單位可利用控制列車容量之策略來分配旅客搭乘車種之需求，因而產生新的停站方式，以達到降低成本並滿足旅客運輸需求；而在求解小路網問題時，基因演算法以及分支界定結合線性鬆弛法和分支界定結合拉氏鬆弛法表現皆較套裝軟體CPLEX求解之效率佳。

In a passenger railroad system, the service planning problem determines the train stopping strategy, taking into consideration multiple train classes, station types and customer origin-destination (OD) demand, to maximize the profit made by a rail company. The service plan is traditionally decided by rule of thumb, an approach that leaves much room for improvement.
In this paper, we propose an integer program for this service planning problem and provide a systematic approach to determining the optimal passenger service plan for a rail company. Commonly used commercial optimization packages cannot solve this complex problem efficiently, especially when problems of realistic need to be solved. Therefore, we develop solution strategies including genetic algorithm (GA), Lagrangian Relaxations (LR) and improved Branch-and-Bound(B&B).
Numerical results show that formulating mathematical model and solving it systematically is more efficiency and flexibility than manly assigned plan. While the numerical analysis results show that adjusting train capacity of the strategy can allocate the demand and resulting in a new service plan of train to reduce costs and meet the needs of passenger transport. The proposed solution strategies can solve real-world problems that are beyond the reach of commonly used optimization packages.

1. 蕭國文 (2010)，「臺鐵機務成本實務運用與分析」，台鐵資料季刊第344期，頁53-70。
2. Bodin, L. D., Golden, B. L., Schuster, A. D., & Romig, W. (1980). A model for the blocking of trains. Transportation Research Part B: Methodological, 14(1–2), 115-120.
3. Bussieck, M. (1998). Optimal lines in public rail transport. Braunschweig, Techn. University, Diss., 1998.
4. Caimi, G., Burkolter, D., Herrmann, T., Chudak, F., & Laumanns, M. (2009). Design of a Railway Scheduling Model for Dense Services. Networks and Spatial Economics, 9(1), 25-46.
5. Caprara, A., Fischetti, M., & Toth, P. (2002). Modeling and Solving the Train Timetabling Problem. Operations Research, 50(5), 851-861.
6. Caprara, A., Galli, L., Kroon, L., Maróti, G., & Toth, P. (2010). Robust Train Routing and Online Re-scheduling Proceedings of the 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (Vol. 14, pp. 24-33).
7. Carey, M., & Carville, S. (2003). Scheduling and platforming trains at busy complex stations. Transportation Research Part A: Policy and Practice, 37(3), 195-224.
8. Carey, M., & Lockwood, D. (1995). A Model, Algorithms and Strategy for Train Pathing. The Journal of the Operational Research Society, 46(8), 988-1005.
9. Chang, Y. H., Yeh, C. H., & Shen, C. C. (2000). A multiobjective model for passenger train services planning: application to Taiwan's high-speed rail line. Transportation Research Part B: Methodological, 34(2), 91-106.
10. Claessens, M. T., van Dijk, N. M., & Zwaneveld, P. J. (1998). Cost optimal allocation of rail passenger lines. European Journal of Operational Research, 110(3), 474-489.
11. Cordeau, J., Toth, P., & Vigo, D. (1998). A Survey of Optimization Models for Train Routing and Scheduling. Transportation Science, 32(4), 380-404.
12. Crainic, T. G., & Rousseau, J. (1986). Multicommodity, multimode freight transportation: A general modeling and algorithmic framework for the service network design problem. Transportation Research Part B: Methodological, 20(3), 225-242.
13. D'Ariano, A. (2008). Improving real-time train dispatching: models, algorithms and applications. TRAIL Research School.
14. Deb, K., & Agrawal, R. (1995). Simulated Binary Crossover for Continuous Search Space. Complex Systems, 9, 115–148.
15. Deb, K., & Goyal, M. (1996). A combined genetic adaptive search (GeneAS) for engineering design. Computer Science and Informatics, 26(4), 30-45.
16. Desaulniers, G., & Hickman, M. D. (2007). Chapter 2 Public Transit. In B. Cynthia & L. Gilbert (Eds.), Handbooks in Operations Research and Management Science (Vol. Volume 14, pp. 69-127): Elsevier.
17. Fisher, M. L. (1981). The Lagrangian Relaxation Method for Solving Integer Programming Problems. Management Science, 27(1), 1-18.
18. Gorman, M. F. (1998). An application of genetic and tabu searches to the freight railroad operating plan problem. Annals of Operations Research, 78(0), 51-69.
19. Higgins, A., Kozan, E., & Ferreira, L. (1997). Modelling the number and location of sidings on a single line railway. Computers & Operations Research, 24(3), 209-220.
20. Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor.
21. Jovanovic, D. (2008). Improving railroad on-time performance : models, algorithms and applications. TRAIL Thesis Series T2008/6, The Netherlands.
22. Jovanovic, D., & Harker, P. T. (1990). A Decision Support System for Train Dispatching: An Optimization-based Methodology. Journal of the Transportation Research Forum, 31(1), 25-37.
23. Jovanovic, D., & Harker, P. T. (1991). Tactical Scheduling of Rail Operations: the SCAN I System. Transportation Science, 25(1), 46-64.
24. Kraay, D., & Harker, P. T. (1995). Real-time scheduling of freight railroads. Transportation Research Part B: Methodological, 29(3), 213-229.
25. Kraay, D., Harker, P. T., & Chen, B. (1991). Optimal Pacing of Trains in Freight Railroads: Model Formulation and Solution. Operations Research, 39(1), 82-99.
26. Lawler, E. L., & Wood, D. E. (1966). Branch-and-Bound Methods: A Survey. Operations Research, 14(4), 699-719.
27. Schöbel, A., & Scholl, S. (2006). Line Planning with Minimal Traveling Time. Paper presented at the 5th Workshop on Algorithmic Methods and Models for Optimization of Railways, Dagstuhl, Germany.
28. Zwaneveld, P. J., Kroon, L. G., & Ambergen, H. W. (1996). A decision support system for routing trains through railway stations. The 1996 5th International Conference on Computer Aided Design, Manufacture and Operation in the Railway and other Advanced Mass Transit Systems, COMPRAIL, 217–226.
29. Zwaneveld, P. J., Kroon, L. G., & van Hoesel, S. P. M. (2001). Routing trains through a railway station based on a node packing model. European Journal of Operational Research, 128(1), 14-33.