鐵路為高度計畫性之運輸系統。營運中所需要之人員、車輛、路線容量等主要資源，均需要在事先做縝密之計畫，方能達到高效率運轉之目標。本研究以臺灣鐵路管理局之車輛編組運用計畫為研究對象，探討其最佳化之相關課題。論文首先瞭解實務作法以及考量因素，明確定義問題，並整理編排車輛編組運用計畫時所應考慮之重要因素。
臺鐵為一高度複雜之系統，每日開行約1000趟車次。所使用之車輛必須由基地出發，執行若干車次之任務後再回到原基地。一個可行的車輛編組運用計畫需要滿足多項要求，包括兩次檢修之間的最大行駛里程、車次間之最小接續時間、基地容量，以及其他。雖然班表已經給定，但實務上於編排車輛編組運用計畫之階段，仍有機會小幅度調整車次之行點以達到更高之車輛運用效率。而最佳化之目標則為最小化所使用之編組數以及儘量減少回送距離。
本研究首度研究臺鐵系統之車輛編組運用問題。在適當簡化考慮因素之後，提出三階段求解方法。第一階段使用時空網路以產生多數之候選運用，之後在第二階段使用線性規畫模式微幅調整給定之班表行點。最後第三階段則構建整數規畫模式以求解候選運用之最佳組合。測試結果顯示該方法能夠解得接近真實車輛編組運用計畫之解。

The railway system relies heavily on planning. Usage of all of the major resources, crew, rolling stock, and railway capacity requires careful planning to achieve high operation efficiency. In this study we focus on the optimization of rolling stock circulation. Taking the Taiwan Railways Administration (TRA) system as the topic, we first define the problem and identify some of the most important factors that should be taken into consideration.
The TRA is a complex system offering approximately 1000 daily services. Its rolling stock has to depart from a depot, execute a number of services, and return to the same depot. A feasible plan has to comply with a number of regulations, including maximum mileage between regular maintenance, minimum connection time between services, depot capacity, and others. While the timetable is given, in practice it is still possible to slightly alter the arrival and departure times to achieve better rolling stock efficiency. The optimization goal is to minimize the number of train set used, as well as to minimize deadheading mileage.
As a first attempt to study the rolling stock circulation problem for TRA, in this work we simplify the requirements and propose a three-stage method to solve the problem. The first stage uses a time-space network to obtain a number of candidate train routes. The second stage employes a linear program to adjust the given timetable, and the final stage uses an integer program to select the best combination among the candidate routes. Numerical testing indicated that the obtained plan is comparible with the real plans.

1.Ahuja, R.K., et al., Solving real-life locomotive-scheduling problems. Transportation Science, 2005. 39(4): p. 503-517.
2.Barnhart, C. and L. Hatay, Deadhead selection for the long-haul crew pairing problem. Operations Research, 1995. 43(3 M3 - Article): p. 491.
3.Booler, J.M.P., The Solution of a Railway Locomotive Scheduling Problem. The Journal of the Operational Research Society, 1980. 31(10): p. 943-948.
4.Budai, G., et al., Rescheduling in passenger railways: the rolling stock rebalancing problem. Journal of Scheduling;Jun2010, Vol. 13 Issue 3, p281, 2009.
5.Cordeau, J.-F., et al., Simultaneous locomotive and car assignment at VIA Rail Canada. Transportation Research Part B: Methodological, 2001. 35(8): p. 767-787.
6.Deng, G.-F. and W.-T. Lin, Ant colony optimization-based algorithm for airline crew scheduling problem. Expert Systems with Applications, 2011. 38(5): p. 5787-5793.
7.Desaulniers, G., et al., Crew pairing at Air France. European Journal of Operational Research, 1997. 97(2): p. 245-259.
8.Dijkstra, E.W., A note on two problems in connexion with graphs. Numerische Mathematik, 1959. 1(1): p. 269-271.
9.Forbes, M.A., J.N. Holt, and A.M. Watts, Exact solution of locomotive scheduling problems. Journal of the Operational Research Society, 1991. 42(10): p. 825-831.
10.Hoffman, K.L. and M. Padberg, Solving a Large-Scaled Crew Pairing Problem by Using a Genetic Algorithm. Management Science, 1993. 39(6 M3 - Article): p. 657-682.
11.Levine, D., Application of a hybrid genetic algorithm to airline crew scheduling. Computers and Operations Research, 1996. 23(6 SPEC. ISS.): p. 547-558.
12.Lingaya, N., et al., Operational car assignment at VIA Rail Canada. Transportation Research Part B: Methodological, 2002. 36(9): p. 755-778.
13.Maróti, G. and L. Kroon, Maintenance routing for train units: The interchange model. Computers & Operations Research, 2007. 34(4): p. 1121-1140.
14.Maroti, G.K., L.G., Maintainance Routing for Train Units: the transition model. Transportation Science, 2005.
15.Nielsen, L.K., L. Kroon, and G. Maróti, A rolling horizon approach for disruption management of railway rolling stock. European Journal of Operational Research, 2012. 220(2): p. 496-509.
16.Peeters, M. and L. Kroon, Circulation of railway rolling stock: a branch-and-price approach. Computers & Operations Research, 2008. 35(2): p. 538-556.
17.Vaidyanathan, B., et al., Real-life locomotive planning: New formulations and computational results. Transportation Research Part B: Methodological, 2008. 42(2): p. 147-168.
18.Wright, M.B., Applying Stochastic Algorithms to a Locomotive Scheduling Problem. The Journal of the Operational Research Society, 1989. 40(2): p. 187-192.
19.Xie, M., et al., Modeling Circulation of Train-Set with Multiple Routing Journal of Transportation Systems Engineering and Information Technology, 2010. 10(3): p. 50-57.
20.Yan, S. and J.-C. Chang, Airline cockpit crew scheduling. European Journal of Operational Research, 2002. 136(3): p. 501-511.
21.Yu, G., Operations Research in the Airline Industry. Springer; 1998 edition (1 Dec 1997), 1998
22.Zeghal, F.M. and M. Minoux, Modeling and solving a Crew Assignment Problem in air transportation. European Journal of Operational Research, 2006. 175(1): p. 187-209.
23.Ziarati, K., et al., Locomotive assignment with heterogeneous consists at CN North America. European Journal of Operational Research, 1997. 97(2): p. 281-292.
24.交通部臺灣鐵路管理局行車實施要點，民國99年。
25.交通部臺灣鐵路管理局車輛檢修程序，民國95年。
26.交通部臺灣鐵路管理局-車種配置基地及固定使用組(輛)數 。民國一0一年七月。
27.交通部臺灣鐵路管理局-編組運用計畫。民國九十九年十二月。
28.交通部臺灣鐵路管理局-編組運用計畫。民國一百年十二月。
29.吳美玲，「列車班表之穩定化」，碩士論文，國立成功大學土木工程研究所，台南，民國一O一年。
30.交通部鐵路行車規則，民國九十五年。
31.臺灣鐵路管理局動力車統計表，年份不詳。
32.杜宇平，顏上堯,「空服員排班網路模式之研究」，博士論文，國立中央大學土木工程研究所, 民國八十九年。
33.蔣阿集, 動力機車檢修規章。民國九十年八月。