鐵路為高度計畫性之運輸系統，系統中之資源如人、車、軌道、基地、車站、等之運用，都需要做完善且細緻的規畫。
臺鐵局營運系統，每日開行約950車次之辦客列車。於執行任務時，車輛編組由基地出發，執行完若干車次後回到原基地。車輛編組執行任務需滿足許多限制，包括單一編組最大行駛里程、前後車次間接續時間的需求、清洗檢修時間長度與時間點、任務間回送距離等諸多因素，其複雜性使得將車次任務分配給車輛編組的計畫工作成為一大挑戰。實務上車輛編組計畫之編排任務多以人工完成，以人力的方式完成這一複雜系統的編排，不容易達到最佳的運用效率計畫，因此運用最佳化技術仍有機會達到更高之車輛運用效率。而最佳化之目標則為節省所需使用之車輛編組數與減少車輛空車回送之任務里程。
本研究從臺鐵之車輛編組運用計畫問題中，萃取出重要考量因素與問題並做適當簡化後，以兩階段演算法求解。第一階段建立時空網路並配合一些觀察到的規則，產生出大量的候選運用，之後於第二階段再從中挑出部份品質優良且平均覆蓋所有營業車次組成候選運用群，再以整數規劃模式協助求解該挑選出的優良候選運用群之最佳組合。以真實資料測試之結果顯示，本演算法可解得接近實務應用之解。

Railway is a heavily planned system. The usage of all of the major resources, including crew, train, rolling stock, railway and station need to be planned carefully in order to achieve efficient operation. This work focuses on the optimization of rolling stock circulation. We first identify the key problems and requirements, then we propose a heuristic that is able to yield very good results.
The Taiwan Railways Administration (TRA) offers approximately 950 services daily. All of its rolling stock needs to depart from a depot, and return to the same depot after serving a number of services. Feasible circulation plans for rolling stocks have to cover every service exactly once, and observe a number of regulations, including maximum mileage between regular maintenance, minimum connection time between services, depot capacity, and others. The optimization objective is to minimize the number of train sets needed, and to minimize dead mileage.
In this study, we propose a two-stage heuristic to solve the rolling stock circulation problem. The first stage uses a time-space network to generate candidate train routes. The second stage selects part of the candidate train routes, then we uses an integer program to select the best combination. Numerical testing results indicate that the heuristic is able to produce rolling circulation plans that are very close to those used in reality.

1.黃冠捷，「鐵路車輛編組運用之最佳化」，國立成功大學土木工程研究所碩士論文，民國102年。
2.Peeters, M. and L. Kroon, “Circulation of railway rolling stock: a branch-and-price approach”, Computers & operations research, Vol. 35, No. 2, 2008, pp. 538-556.
3.Brucker, P., J.L. Hurink, and T. Rolfes, “Routing of railway carriages: A case study”, Osnabrücker Geschriften zur Mathematik, 1999.
4.Alfieri, A., R. Groot, L. Kroon, and A. Schrijver, “Efficient circulation of railway rolling stock”, Transportation Science, Vol. 40, No. 3, 2006, pp. 378-391.
5.Budai, G., G. Maróti, R. Dekker, D. Huisman, and L. Kroon, “Rescheduling in passenger railways: the rolling stock rebalancing problem”, Journal of scheduling, Vol. 13, No. 3, 2010, pp. 281-297.
6.Farahani, R.Z., N. Asgari, N. Heidari, M. Hosseininia, and M. Goh, “Covering problems in facility location: A review”, Computers & Industrial Engineering, Vol. 62, No. 1, 2012, pp. 368-407.
7.Schilling, D.A., V. Jayaraman, and R. Barkhi, “A review of covering problems in facility location”, Computers & Operations Research, 1993.
8.Toregas, C., R. Swain, C. ReVelle, and L. Bergman, “The location of emergency service facilities”, Operations Research, Vol. 19, No. 6, 1971, pp. 1363-1373.
9.Lan, G., G.W. DePuy, and G.E. Whitehouse, “An effective and simple heuristic for the set covering problem”, European journal of operational research, Vol. 176, No. 3, 2007, pp. 1387-1403.
10.Balas, E. and M.C. Carrera, “A dynamic subgradient-based branch-and-bound procedure for set covering”, Operations Research, Vol. 44, No. 6, 1996, pp. 875-890.
11.Beasley, J.E. and K. Jörnsten, “Enhancing an algorithm for set covering problems”, European Journal of Operational Research, Vol. 58, No. 2, 1992, pp. 293-300.
12.Fisher, M.L. and P. Kedia, “Optimal solution of set covering/partitioning problems using dual heuristics”, Management science, Vol. 36, No. 6, 1990, pp. 674-688.
13.Chvatal, V., “A greedy heuristic for the set-covering problem”, Mathematics of operations research, Vol. 4, No. 3, 1979, pp. 233-235.
14.Jacobs, L.W. and M.J. Brusco, “Note: A local‐search heuristic for large set‐covering problems”, Naval Research Logistics (NRL), Vol. 42, No. 7, 1995, pp. 1129-1140.
15.Aickelin, U., “An indirect genetic algorithm for set covering problems”, Journal of the Operational Research Society, 2002, pp. 1118-1126.
16.Beasley, J.E. and P.C. Chu, “A genetic algorithm for the set covering problem”, European Journal of Operational Research, Vol. 94, No. 2, 1996, pp. 392-404.
17.Ohlsson, M., C. Peterson, and B. Söderberg, “An efficient mean field approach to the set covering problem”, European Journal of Operational Research, Vol. 133, No. 3, 2001, pp. 583-595.
18.Balas, E. and M.W. Padberg, “Set partitioning: A survey”, SIAM review, Vol. 18, No. 4, 1976, pp. 710-760.
19.Chu, P. and J.E. Beasley, “Constraint handling in genetic algorithms: the set partitioning problem”, Journal of Heuristics, Vol. 4, No. 4, 1998, pp. 323-357.
20.Garfinkel, R.S. and G.L. Nemhauser, “The set-partitioning problem: set covering with equality constraints”, Operations Research, Vol. 17, No. 5, 1969, pp. 848-856.
21.Delorme, J., Contribution à la résolution du problème de recouvrement: méthodes de troncatures, Université de Paris VI, 1974.
22.Gomory, R.E., “An algorithm for integer solutions to linear programs”, Recent advances in mathematical programming, Vol. 64, 1963, pp. 260-302.
23.Koncal, R.D. and H.M. Salkin, “Set covering by an all integer algorithm: computational experience”, Journal of the ACM, Vol. 20, No. 2, 1973, pp. 189-193.
24.Lewis, M., G. Kochenberger, and B. Alidaee, “A new modeling and solution approach for the set-partitioning problem”, Computers & Operations Research, Vol. 35, No. 3, 2008, pp. 807-813.
25.Kumar, S.N. and R. Panneerselvam, “A survey on the vehicle routing problem and its variants”, Intelligent Information Management, Vol. 4, No. 3, 2012, pp. 66-74.
26.Toth, P. and D. Vigo, “An overview of vehicle routing problems”, The vehicle routing problem, Society for Industrial and Applied Mathematics, 2001, pp. 1-26.
27.Baldacci, R., E. Hadjiconstantinou, and A. Mingozzi, “An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation”, Operations Research, Vol. 52, No. 5, 2004, pp. 723-738.
28.Surekha, P. and S. Sumathi, “Solution to multi-depot vehicle routing problem using genetic algorithms”, World Applied Programming, Vol. 1, No. 3, 2011, pp. 118-131.
29.Ho, W., G.T. Ho, P. Ji, and H.C. Lau, “A hybrid genetic algorithm for the multi-depot vehicle routing problem”, Engineering Applications of Artificial Intelligence, Vol. 21, No. 4, 2008, pp. 548-557.
30.Homberger, J. and H. Gehring, “A two-phase hybrid metaheuristic for the vehicle routing problem with time windows”, European Journal of Operational Research, Vol. 162, No. 1, 2005, pp. 220-238.
31.Berger, J., M. Barkaoui, and O. Braysy, “A route-directed hybrid genetic approach for the vehicle routing problem with time windows”, Infor-Information Systems and Operational Research, Vol. 41, No. 2, 2003, pp. 179-194.