Title

高速鐵路車輛指派與檢修排程規劃

Translated Titles

Rolling Stock Rostering and Maintenance Scheduling for High Speed Rail System

Authors

王劭暐

Key Words

高速鐵路 ; 軌道車輛指派 ; 檢修排程 ; 決策支援工具 ; 整數規劃 ; 啟發式演算法 ; High Speed Rail ; Rolling Stock Rostering ; Maintenance Scheduling ; Decision Support Tool ; Integer Programming ; Heuristics Algorithm

PublicationName

臺灣大學土木工程學研究所學位論文

Volume or Term/Year and Month of Publication

2014年

Academic Degree Category

碩士

Advisor

賴勇成

Content Language

繁體中文

Chinese Abstract

軌道運輸的各項營運設備中,車輛是最主要的資源之一,為承載客貨執行運輸服務的基本單元,由於購置價格高、使用週期長,且必須透過定期檢修確保車輛狀況,因此有效率地規劃並使用車輛資源,是軌道營運業者重要的營運規劃項目之一。本研究所探討的「車輛指派規劃」,屬於軌道車輛資源規劃中的日常決策項目之一,藉由給定的車輛運用與檢修計畫,根據各車輛的位置及營運狀態,將車輛與運用行路一一對應,決定各車輛每日的營運與檢修任務內容,並避免違反實務上的限制,如檢修週期規範等。由於此日常規劃作業的複雜性,以及限制的繁瑣,臺灣的軌道營運業者,如臺鐵局、高鐵公司,對於車輛指派規劃作業仍以人工作業規劃為主,人工規劃雖可產生可行的車輛指派計畫,卻難以確保結果的最佳性,規劃過程亦耗時耗力。而過去雖有許多關於車輛資源規劃的文獻,然而不論在問題背景、規劃目標與決策考量的限制因素,皆與本研究所探討的「車輛指派規劃」本質有所不同。 本研究透過文獻回顧與實務規劃流程之探討,歸納出高速鐵路車輛指派規劃的問題架構與主要的考量因素,並分別考量給定與可變動月檢排程的兩種問題背景,建構最佳化決策支援工具,針對兩種問題背景皆分別建立整數規劃模式及啟發式演算法。藉由案例分析證實決策支援工具皆可在實務可接受的時間範圍內,提供比人工規劃較佳的車輛指派計畫,約可提高3~4%的維修到達率。應用本研究提出的決策支援工具,不僅可減低人工規劃作業所需的人力與時間,更可提高車輛運用的效率,並降低不必要的檢修所帶來的檢修成本浪費。

English Abstract

Rolling stock is one of the major resource for railway operators to provide transport service. Due to the high acquiring cost and long life cycle, the efficient usage of rolling stock is one of the key planning goal for railway operators. This study focus on the rolling stock rostering in high speed rail system, which a daily varying decision. Given the rolling stock circulation and maintenance plan, the rostering planner decides the assignment between individual rolling stock and duty according to practical constraints. The decision includes the daily operational and maintenance plan for each rolling stock. Because of the complexity and the uncertainty, railway operators in Taiwan implement rostering plan manually. Although manual plan is feasible and the planning time is acceptable, it can not guarantee the optimality of the results. In addition, the routinely planning process is time consuming. On the other hand, there are several essential differences between the problem in this study and previous literature. Therefore, methods proposed by past studies can not directly applied to our problem. Based on literature review and insight discussion of practical planning process, this study proposed decision support tools for the rolling stock rostering problem. In order to be applied in different decision backgrounds, frameworks for both fixed and variable plans of monthly inspection are presented. For each consideration of inspection, integer programming model and heuristics algorithm are developed to solve the problem. According to the results of case study, the rolling stock utilization rate can be raised by 3~4% using the decision support tool in this study, which decreases the waste of unnecessary maintenance.

Topic Category 工學院 > 土木工程學研究所
工程學 > 土木與建築工程
Reference
  1. 1. Alfieri, A., Groot, R., Kroon, L., and Schrijver, A. 2006. Efficient Circulation of Railway Rolling Stock. Transportation Science. 40(3): 378-391.
  2. 2. Ben-Khedher, N., Kintanar, J., Queille, C., and Stripling, W. 1998. Schedule Optimization at SNCF: From Conception to Day of Departure. Interfaces. 28(1): 6-23.
  3. 3. Brucker, P., Hurink, J., and Rolfes, T. 2003. Routing of Railway Carriages. Journal of Global Optimization. 27: 313-332.
  4. 4. Budai, G., Maróti, G., Dekker, R., Huisman, D., and Kroon, L. 2010. Rescheduling in passenger railways: the rolling stock rebalancing problem. Journal of Scheduling. 13(3): 281-297.
  5. 5. Cacchiani, V., Caprara, A., and Toth, P. 2010. Solving a real-world train-unit assignment problem. Mathematical Programming. 124(1-2): 207-231.
  6. 6. Cacchiani, V., Caprara, A., and Toth, P. 2012a. A Fast Heuristic Algorithm for the Train Unit Assignment Problem. Proceedings of 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Ljubljana, Slovenia.
  7. 7. Cacchinai, V., Caprara, A., Galli, L., Kroon, L., Maróti, G., and Toth, P. 2012b. Railway Rolling Stock Planning: Robustness Against Large Disruptions. Transportation Science. 46(2): 217-232.
  8. 8. Cacchiani, V., Caprara, A., and Toth, P. 2013. A Lagrangian heuristic for a train-unit assignment problem. Discrete Applied Mathematics. 161: 1707-1718.
  9. 9. Cadarso, L., and Marín, Á. 2010. Robust routing of rapid transit rolling stock. Public Transport. 2(1-2): 51-68.
  10. 10. Cadarso, L., and Marín, Á. 2011. Robust rolling stock in rapid transit networks. Computers & Operations Research. 38: 1131-1142.
  11. 11. Cordeau, J., Soumis, F., and Desrosiers, J. 2000. A Benders Decomposition Approach for the Locomotive and Car Assignment Problem. Transportation Science. 34(2): 133-149.
  12. 12. Cordeau, J., Desaulniers, G., Lingaya, N., Soumis, F., and Desrosiers, J. 2001a. Simultaneous locomotive and car assignment at VIA Rail Canada. Transportation Research Part B. 35: 767-787.
  13. 13. Cordeau, J., Soumis, F., and Desrosiers, J. 2001b. Simultaneous Assignment of Locomotives and Cars to Passenger Trains. Operations Research. 49(4): 531-548.
  14. 14. Fioole, P., Kroon, L., Maróti, G., and Schrijver, A. 2006. A rolling stock circulation model for combining and splitting of passenger trains. European Journal of Operational Research. 174: 1281-1297.
  15. 15. Forbes, M., Holt, J., and Watts, A. 1991. Exact Solution of Locomotive Scheduling Problems. The Journal of the Operational Research Society. 42(10): 825-831.
  16. 16. Giacco, G., D'Ariano, A., and Pacciarelli, D. 2011. Rolling stock rostering optimization under maintenance constraints. Proceedings of 2nd International Conference on Models and Technologies for Intelligent Transportation Systems. Leuven, Belgium.
  17. 17. Giacco, G., D'Ariano, A., and Pacciarelli, D. 2014. Rolling stock rostering optimization under maintenance constraints. Journal of Intelligent Transportation Systems: Technology, Planning, and Operations. 18(1): 95-105.
  18. 18. Hong, S. P., Kim, K. M., Lee, K., and Park, B. H. 2009. A pragmatic algorithm forthe train-set routing: The case of Korea high-speed railway. Omega. 37: 637-645.
  19. 19. Kroon, L., Maróti, G., and Nielsen, L. 2014. Rescheduling of Railway Rolling Stock with Dynamic Passenger Flows. Transportation Science. Article in Advance.
  20. 20. Lingaya., N., Cordeau, J., Desaulniers, G., Desrosiers, J., and Soumis, F. 2002. Operational car assignment at VIA Rail Canada. Transportation Research Part B. 36: 755-778.
  21. 21. Marín, Á., and Cadarso, L. 2009a. The Rapid Transit Routing Problem. Proceedings of 11th International Conference on Advanced Systems for Public Transport. Hong Kong.
  22. 22. Marín, Á., and Cadarso, L. 2009b. An Approach to Rapid Transit Rolling Stock Assignment. Proceedings of 3th International Conference on Railway Operations Modelling and Analysi. Zurich, Switzerland.
  23. 23. Maróti, G. and Kroon, L. 2005. Maintenance Routing for Train Units: The Transition Model. Transportation Science. 39(4): 518-525.
  24. 23. Maróti, G. and Kroon, L. 2007. Maintenance routing for train units: The interchange model. Computers & Operations Research. 34: 1121-1140.
  25. 25. Nielsen, L., Kroon, L., and Maróti, G. 2012. A rolling horizon approach for disruption management of railway rolling stock. European Journal of Operational Research. 220: 496-509.
  26. 26. Otsuki, T., Aisu, H., and Tanaka, T. 2010. A Search-Based Approach to the Railway Rolling Stock Allocation Problem. Lecture Notes in Computer Science. 6509: 131-143.
  27. 27. Peeters, M. and Kroon. L. 2008. Circulation of railway rolling stock: a branch-and-price approach. Computers & Operations Research. 35:538-556.
  28. 28. Radtke, A., Horstel, J., and Schumacher, A. 1996. Optimised rostering and maintaining of high-speed rail systems. Computers in Railways V. 1:403-409.
  29. 29. Rouillon S., Desaulniers, G., and Soumis, F. 2006. An extended branch-and-bound method for locomotive assignment. Transportation Research Part B. 40: 404-423.
  30. 30. Schrijver, A. 1993. Minimum Circulation of Railway Stock. CWI Quarterly. 3: 205-217.
  31. 31. Tsuji, Y., Kuroda, M., Kitagawa, Y. and Imoto, Y. 2012. Ant Colony Optimization Approach for Solving Rolling Stock Planning for Passenger Trains. Proceedings of 2012 IEEE/SICE International Symposium on System Integration. Fukuoka, Japan.
  32. 32. Wright, M. 1989. Applying Stochastic Algorithms to a Locomotive Scheduling Problem. The Journal of the Operational Research Society. 40(2): 187-192.
  33. 33. Xie, M., Mao, B., Ho, T., Chen, Z., and Bai, Y. 2010. Modeling Circulation of Train-Set with Multiple Routing. Journal of Transportation Systems Engineering and Information Technology. 10(3): 50-57.
  34. 34. Zhao, P., Tomii, N., Fukumura, N., and Sakaguchi, T. 2002. An algorithm for train-set scheduling based on probabilistic local search. Computers in Railways VIII. 817-826.
  35. 35. Zhu, C., Liu, D., Cheng L., and Li, H. 2013. Study on Optimization of Railway Passenger Train Sets Assignment. Information Technology Journal. 12: 1251-1256.
  36. 36. Ziarati, K., Soumis, F., Desrosiers, J., Gélinasd, S., and Saintonge, A. 1997. Locomotive assignment with heterogeneous consists at CN North America. European Journal of Operational Research. 97: 281-292.
  37. 37. Ziarati, K., Soumis, F., Desrosiers, J., and Solomon, M. 1999. A Branch-First, Cut-Second Approach for Locomotive Assignment. Management Science. 45(8): 1156-1168.
  38. 38. 范道中,臺鐵車輛調配規劃決策支援模式之研發,國立臺灣大學土木工程學系碩士論文,民國一百零二年。
  39. 39. 曾微雯,研發台灣高速鐵路列車組指派最佳化模式,國立臺灣大學土木工程學系碩士論文,民國一百年。
  40. 40. 劉國著,軌道車輛運用路徑規劃尋優模式之建立,國立臺灣大學土木工程學系碩士論文,民國一百零一年。