鐵路運輸是許多國家的重要運輸模式，因此如何使鐵路運輸系統更有效率一直是許多專家學者努力的目標，本研究將探討鐵路運輸系統中的「列車設計問題」，由於列車由驅動的「動力車」(Locomotive)掛載一些車廂所構成的「車廂集」(Block)所組成，該問題主要分成兩個部分:第一部分求解動力車行駛路徑的「動力車路徑規劃問題」，第二部分則求解如何將車廂集由其起點送至訖點且應由那些動力車掛載以形成列車的「車廂集裝載計畫」。由於車廂集之旅運與轉運成本皆與動力車行駛路徑密切相關，而動力車路徑亦因其起訖站未知而致其可行解空間極大，造成求解十分困難。本研究先針對「動力車路徑規劃問題」提出兩種路徑產生方式，再以產生出來的動力車路徑為基礎，利用整數規劃求解「車廂集裝載計畫」，並試圖藉由新增可改善列車路徑平衡性或合併列車路徑等方式核建立更好的動力車路徑。最後，將新的動力車路徑加入整數規劃模型中，並重新求解。如此反覆地求解整數規劃模型與更新動力車路徑，直至收斂至足夠滿意的結果為止。本研究將從現實鐵路系統中擷取兩筆資料，接著以這兩筆資料為基礎，利用隨機的方式產生其餘測試資料。測試結果顯示，我們所提出的疊代式路徑生成演算法不但可以有效求解，並可容易地將現行的動力車路徑納入考量以設計出更好的列車運行計畫，兼具理論與實務價值。

In the freight railroad industry, how to aggregate freight railcars based on different attributes to create blocks and subsequently combine them to create trains have not changed over the past two centuries. This is called a Train Design Problem (TD), which contains two major components: (1) Train Routing (TR) and (2) Block-to-Train assignment (BTA). TR identifies the origin, destination, and route for each individual train, while BTA seeks the best transportation plan for each block that determines which trains to carry it. Hence, as the solution of TR has changed, so does BTA’s. To calculate the optimum solution of TD, we need to solve TR and BTA iteratively. This paper proposes an iterative solution method, which first solves TR with two procedures, and then solves BTA with an Integer Programming model. With several speeding-up techniques such as column generation procedure and warm start mechanism, our solution approach can identify a good solution in short time. We also give a modification procedure to further improve the solution quality by adding new train routes that reduces the train imbalances or merges different train routes, which in turn enhances practicality of our solution method. Results of computational experiments indicate that our solution method does well in comparison with those in literatures.

Ahuja, R. K., Jha, K. C., & Liu, J. (2007). Solving Real-Life Railroad Blocking Problems. Interfaces, 37(5), 404-419.
Assad, Arjang A. (1980). Models for rail transportation. Transportation Research Part A: General, 14(3), 205-220.
Assad, A. A. (1983). Analysis of rail classification policies. INFOR, 21, 293-314.
Barnhart, Cynthia, Jin, Hong, & Vance, Pamela H. (2000). Railroad Blocking: A Network Design Application. Operations Research, 48(4), 603-614.
Bodin, Lawrence D., Golden, Bruce L., Schuster, Allan D., & Romig, William. (1980). A model for the blocking of trains. Transportation Research Part B: Methodological, 14(1–2), 115-120.
Francis Gorman, Michael. (1998). An application of genetic and tabu searches to the freight railroad operating plan problem. Annals of Operations Research, 78(0), 51-69.
Haghani, Ali E. (1987). Rail freight transportation: A review of recent optimization models for train routing and empty car distribution. Journal of Advanced Transportation, 21(2), 147-172.
Haghani, Ali E. (1989). Formulation and solution of a combined train routing and makeup, and empty car distribution model. Transportation Research Part B: Methodological, 23(6), 433-452.
INFORMS (2011). RAS Problem Solving Competition.
<http://www.informs.org/Community/RAS/Problem-Solving-Competition/2011-RAS-Problem-Solving-Competition>.
Jha, Krishna C., Ahuja, Ravindra K., & Şahin, Güvenç. (2008). New approaches for solving the block-to-train assignment problem. Networks, 51(1), 48-62.
Jin, Jian Gang, Zhao, Jun, & Lee, Der-Horng. (2013). A column generation based approach for the Train Network Design Optimization problem. Transportation Research Part E: Logistics and Transportation Review, 50(0), 1-17.
Keaton, Mark H. (1989). Designing optimal railroad operating plans: Lagrangian relaxation and heuristic approaches. Transportation Research Part B: Methodological, 23(6), 415-431.
Keaton, Mark H. (1992). Designing Railroad Operating Plans: A Dual Adjustment Method for Implementing Lagrangian Relaxation. Transportation Science, 26(4), 263-279.
Newman, Alexandra M., & Yano, Candace Arai. (2000). Scheduling Direct and Indirect Trains and Containers in an Intermodal Setting. Transportation Science, 34(3), 256-270.
Newton, Harry N., Barnhart, Cynthia, & Vance, Pamela H. (1998). Constructing Railroad Blocking Plans to Minimize Handling Costs. Transportation Science, 32(4), 330-345.