研發台灣高速鐵路列車組指派最佳化模式

Development of an Operational Train-Set Assignment Model for Taiwan High Speed Rail

曾微雯(Wei-Wen Zeng)

指導教授 ： 賴勇成

國立臺灣大學/工學院/土木工程學研究所/碩士(2011年)

https://doi.org/10.6342/NTU.2011.10436

摘要

車輛為軌道運輸系統中最昂貴的設備之一，如何有效的運用此項資產，對軌道系統整體營運而言極為重要。在實務操作上，軌道車輛運用指派規劃必須根據維修需求、車站容量等限制條件，指派軌道車輛以滿足使用需求，但因車輛指派問題的複雜性，目前實務界仍多半以人工安排為主。雖然經驗豐富的軌道從業人員，有能力安排一個可行且不錯的短期車輛運用規劃，但並無法進一步確認其為最佳規劃。此外，從長遠的角度而言，短期規劃因為考慮的時程較短，所得之結果可能為一近視解（myopic decision），而非全域最佳解（global optimum）。因此，為提升軌道車輛使用效率，並增強長期規劃之有效性，應建立一決策分析工具，來自動化的產生最佳軌道車輛指派計劃，以改善傳統人工安排與規劃之不足。
本研究主要以台灣高鐵實務作業流程為基礎，以混合整數規劃與啟發式演算法，建構最佳化之列車組指派工具，為評估模式應用之可行性，並將以高鐵之實際資料進行測試，進而提升自動化模式之準確性與可靠度。此最佳化模式除可幫助軌道產業提高運轉效率、降低營運成本外，亦可同步增加系統運作之可靠度及營運績效。

關鍵字

軌道運輸 ； 軌道車輛運用 ； 決策分析系統 ； 混和整數規劃 ； 啟發式演算法

並列摘要

Railway rolling stock is one of the most expensive assets of a railroad agency or company. Therefore, efficient utilization of rolling stock is a very important objective pursued in practice. The rolling stock assignment process aims to assign appropriate equipments to cover a given set of utilization schedule with considerations to practical requirements, such as maintenance, station capacity, and rules for circulation. Due to the complexity of this task, this process is still made manually in practices. Experienced railroaders can generally create a good and feasible plan; however, there is no guarantee of the optimality of the solution. Also, considering only short-term process may lead to a myopic decision away from the global optimum. Consequently, there is a need to develop a decision support system to automatically generate the optimal rolling stock assignment.
This study aims to develop a train-set assignment system for Taiwan High Speed Rail by using Mixed Integer Programming and Heuristic Method. The model can not only help railway agencies utilize their rolling stock efficiently but also be better able to provide reliable service to their customers, and return on shareholder investment.

並列關鍵字

railway transportation ； rolling stock ； decision support system ； mixed integer programming ； heuristic algorithm

參考文獻

2. Alfieri, A., Groot, R., Kroon, L., and Schrijver, A. (2006), “Efficient Circulation of Railway Rolling Stock,” Transportation Science, Vol. 40, No. 3, pp. 378-391.

3. Booler, J. M. P. (1980), “The solution of a Railway Locomotive Scheduling Problem,” Journal of Operational Research Society, Vol. 31, pp. 943-948.

5. Cordeau, J. F., Soumis, F., and Descrosiers, J. (2000), “A Bender Decomposition Approach for the Locomotive and Car Assignment Problem,” Transportation Science, Vol. 34, No. 2, pp. 133-149.

7. Dejax, P. J. and Crainic, T. G. (1987), “A Review of Empty Flows and Fleet Management Models in Freight Transportation,” Transportation Science, Vol. 21, No. 4, pp. 227-247.

9. Maróti, G., and Kroon L. (2007), “Maintenance routing for train units：The interchange model,” Computers & Operations Research, Vol. 34, pp. 1121-1140.