進階搜尋


 
系統識別號 U0026-2308201214375600
論文名稱(中文) 台鐵列車服務計畫之研究
論文名稱(英文) Passenger Train Service Plan Optimization:the Application to Taiwan’s Railway System
校院名稱 成功大學
系所名稱(中) 交通管理學系碩博士班
系所名稱(英) Department of Transportation & Communication Management Science
學年度 100
學期 2
出版年 101
研究生(中文) 古宇翔
研究生(英文) Yu-Hsiung Ku
學號 r56991092
學位類別 碩士
語文別 中文
論文頁數 63頁
口試委員 指導教授-林東盈
口試委員-李宇欣
口試委員-鄭永祥
口試委員-李治綱
中文關鍵字 軌道運輸  列車服務計畫  停站模式  台鐵  混合整數規劃 
英文關鍵字 Railroad  Service planning  integer program  Taiwan’s Rail  Mixed integer programming 
學科別分類
中文摘要 軌道運輸於台灣之中長程大眾運輸環境占相當重要的地位,而台鐵之發展歷史最為悠久,由於其多車種、多站等之營運特性,列車運行環境極為複雜,所有列車皆仰賴時刻表進行運轉發車,而制定時刻表之基礎其中一項為列車服務計畫,其為決定各車種列車之停站方式,如何有效率的進行規劃則為重要的課題。
目前台鐵列車停站方式為人工指派之方式進行排定,而本研究以數學規劃之工具建立一混合整數規劃之列車停站模式,再利用套裝軟體CPLEX以及基因演算法求解模式,當問題規模擴增時,CPLEX之求解速度以非線性倍數上升,因此本研究發展演算法以基因演算法、拉氏鬆弛法以及改良之分支界定法所組合成之求解策略求解較大規模之問題,並且進行數值分析。
實驗結果發現建立數學模式進行系統性的規劃求解,與人工指派之方式相較之下,可更為有效率以及彈性地進行各情境之結果比對,而數值分析之結果顯示決策單位可利用控制列車容量之策略來分配旅客搭乘車種之需求,因而產生新的停站方式,以達到降低成本並滿足旅客運輸需求;而在求解小路網問題時,基因演算法以及分支界定結合線性鬆弛法和分支界定結合拉氏鬆弛法表現皆較套裝軟體CPLEX求解之效率佳。
英文摘要 In a passenger railroad system, the service planning problem determines the train stopping strategy, taking into consideration multiple train classes, station types and customer origin-destination (OD) demand, to maximize the profit made by a rail company. The service plan is traditionally decided by rule of thumb, an approach that leaves much room for improvement.
In this paper, we propose an integer program for this service planning problem and provide a systematic approach to determining the optimal passenger service plan for a rail company. Commonly used commercial optimization packages cannot solve this complex problem efficiently, especially when problems of realistic need to be solved. Therefore, we develop solution strategies including genetic algorithm (GA), Lagrangian Relaxations (LR) and improved Branch-and-Bound(B&B).
Numerical results show that formulating mathematical model and solving it systematically is more efficiency and flexibility than manly assigned plan. While the numerical analysis results show that adjusting train capacity of the strategy can allocate the demand and resulting in a new service plan of train to reduce costs and meet the needs of passenger transport. The proposed solution strategies can solve real-world problems that are beyond the reach of commonly used optimization packages.
論文目次 目錄

第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究方法與步驟 2
1.4 研究架構 2
第二章 文獻回顧 5
2.1 路線選擇問題 5
2.1.1 旅客運輸之列車路線規劃 6
2.1.2 貨運路網之路線規劃 6
2.2 列車排程問題 7
2.2.1 列車排程的策略面 7
2.2.2 列車排程的營運面 8
2.3 路線選擇及排程之組合問題 10
2.4 演算法 11
2.4.1 基因演算法 11
2.4.2 分支界定法 12
2.4.3 拉氏鬆弛法 13
2.5 小結 13
第三章 模式建構 14
3.1 問題描述 14
3.2 模式的基本假設 14
3.3 符號說明 15
3.4 建構數學模式 17
3.5 小結 19
第四章 求解策略 20
4.1 利用套裝軟體(CPLEX)求解問題 20
4.2 基因演算法 20
4.2.1 問題特性 22
4.2.2 編碼 23
4.2.3 產生母代 24
4.2.4 配適值之評估 24
4.2.5 選擇與複製(selection & reproduction) 24
4.2.6 交配(crossover) 24
4.2.7 突變(mutation) 27
4.2.8 停止條件 28
4.2.9 編碼改良 28
4.2.10 交配機制 30
4.2.11 突變機制 31
4.3 B&B-LP algorithm 32
4.3.1 分支界定法(Branch-and-Bound, B&B) 32
4.3.2 初始化 34
4.3.3 求解線性子問題 35
4.3.4 可行解之判斷 35
4.3.5 分支(branching) 36
4.3.6 修剪(prune) 38
4.3.7 界定(bounding) 40
4.3.8 分支界定法之停止條件 40
4.4 B&B-LR-GA algorithm 41
4.4.1 拉氏鬆弛法(Lagrangian Relaxation, LR) 43
4.4.2 鬆弛容量限制式 44
4.4.3 拉氏問題之數學模式 44
4.4.4 更新拉氏乘數 45
4.4.5 拉氏鬆弛法之停止條件 46
4.4.6 B&B-LR-GA停止條件 46
4.5 小結 46
第五章 實證研究 47
5.1 小規模問題以CPLEX及各演算法求解 47
5.1.1 各演算法之比較 51
5.1.2 旅客需求敏感度分析 52
5.1.3 列車容量敏感度分析 54
5.1.4 列車成本敏感度分析 56
5.2 求解實際路網之結果分析 57
5.3 小結 58
第六章 結論與建議 60
參考文獻 61

圖目錄

圖1.1 研究架構 4
圖4.1 基因演算法流程 21
圖4.2 染色體之表示方式 22
圖4.3 實例之染色體 23
圖4.4 染色體之資料型態 23
圖4.5 單平面交配示意圖 25
圖4.6 單平面交配部分區段 25
圖4.7 多平面交配示意圖 26
圖4.8 多平面交配部分區段 26
圖4.9 突變發生之變動情況 27
圖4.10 二元編碼染色體交配後易產生不可行解之情況 29
圖4.11 整數編碼之染色體 29
圖4.12 B&B-LP流程 33
圖4.13決策樹之初始化 34
圖4.14 決策樹之分支 37
圖4.15 針對問題特性之分支法 38
圖4.16 決策樹搜尋至最底層時之修剪策略 39
圖4.17 子問題不可行時之節點跳動情形 40
圖4.18 決策樹已無節點可繼續搜尋時之情形 41
圖4.19 B&B-LR-GA流程 43
圖5.1 演算法收斂情形 52
圖5.2 在需求變動下利潤變化之趨勢 54
圖5.3 當成本變動下利潤之變化趨勢 56

表目錄

表4.1 可行解判斷後搜尋動作 36
表5.1 列車停靠站數準則 48
表5.2 各車種之成本參數 49
表5.3 岡山至橋頭各站票價 50
表5.4 岡山至橋頭等各站單日起訖需求 51
表5.5 各需求下列車停站之情形 53
表5.6 調整容量狀況下列車停站之情形 55
表5.7 自強號停站與實際班表停站之比較 57
參考文獻 1. 蕭國文 (2010),「臺鐵機務成本實務運用與分析」,台鐵資料季刊第344期,頁53-70。
2. Bodin, L. D., Golden, B. L., Schuster, A. D., & Romig, W. (1980). A model for the blocking of trains. Transportation Research Part B: Methodological, 14(1–2), 115-120.
3. Bussieck, M. (1998). Optimal lines in public rail transport. Braunschweig, Techn. University, Diss., 1998.
4. Caimi, G., Burkolter, D., Herrmann, T., Chudak, F., & Laumanns, M. (2009). Design of a Railway Scheduling Model for Dense Services. Networks and Spatial Economics, 9(1), 25-46.
5. Caprara, A., Fischetti, M., & Toth, P. (2002). Modeling and Solving the Train Timetabling Problem. Operations Research, 50(5), 851-861.
6. Caprara, A., Galli, L., Kroon, L., Maróti, G., & Toth, P. (2010). Robust Train Routing and Online Re-scheduling Proceedings of the 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (Vol. 14, pp. 24-33).
7. Carey, M., & Carville, S. (2003). Scheduling and platforming trains at busy complex stations. Transportation Research Part A: Policy and Practice, 37(3), 195-224.
8. Carey, M., & Lockwood, D. (1995). A Model, Algorithms and Strategy for Train Pathing. The Journal of the Operational Research Society, 46(8), 988-1005.
9. Chang, Y. H., Yeh, C. H., & Shen, C. C. (2000). A multiobjective model for passenger train services planning: application to Taiwan's high-speed rail line. Transportation Research Part B: Methodological, 34(2), 91-106.
10. Claessens, M. T., van Dijk, N. M., & Zwaneveld, P. J. (1998). Cost optimal allocation of rail passenger lines. European Journal of Operational Research, 110(3), 474-489.
11. Cordeau, J., Toth, P., & Vigo, D. (1998). A Survey of Optimization Models for Train Routing and Scheduling. Transportation Science, 32(4), 380-404.
12. Crainic, T. G., & Rousseau, J. (1986). Multicommodity, multimode freight transportation: A general modeling and algorithmic framework for the service network design problem. Transportation Research Part B: Methodological, 20(3), 225-242.
13. D'Ariano, A. (2008). Improving real-time train dispatching: models, algorithms and applications. TRAIL Research School.
14. Deb, K., & Agrawal, R. (1995). Simulated Binary Crossover for Continuous Search Space. Complex Systems, 9, 115–148.
15. Deb, K., & Goyal, M. (1996). A combined genetic adaptive search (GeneAS) for engineering design. Computer Science and Informatics, 26(4), 30-45.
16. Desaulniers, G., & Hickman, M. D. (2007). Chapter 2 Public Transit. In B. Cynthia & L. Gilbert (Eds.), Handbooks in Operations Research and Management Science (Vol. Volume 14, pp. 69-127): Elsevier.
17. Fisher, M. L. (1981). The Lagrangian Relaxation Method for Solving Integer Programming Problems. Management Science, 27(1), 1-18.
18. Gorman, M. F. (1998). An application of genetic and tabu searches to the freight railroad operating plan problem. Annals of Operations Research, 78(0), 51-69.
19. Higgins, A., Kozan, E., & Ferreira, L. (1997). Modelling the number and location of sidings on a single line railway. Computers & Operations Research, 24(3), 209-220.
20. Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor.
21. Jovanovic, D. (2008). Improving railroad on-time performance : models, algorithms and applications. TRAIL Thesis Series T2008/6, The Netherlands.
22. Jovanovic, D., & Harker, P. T. (1990). A Decision Support System for Train Dispatching: An Optimization-based Methodology. Journal of the Transportation Research Forum, 31(1), 25-37.
23. Jovanovic, D., & Harker, P. T. (1991). Tactical Scheduling of Rail Operations: the SCAN I System. Transportation Science, 25(1), 46-64.
24. Kraay, D., & Harker, P. T. (1995). Real-time scheduling of freight railroads. Transportation Research Part B: Methodological, 29(3), 213-229.
25. Kraay, D., Harker, P. T., & Chen, B. (1991). Optimal Pacing of Trains in Freight Railroads: Model Formulation and Solution. Operations Research, 39(1), 82-99.
26. Lawler, E. L., & Wood, D. E. (1966). Branch-and-Bound Methods: A Survey. Operations Research, 14(4), 699-719.
27. Schöbel, A., & Scholl, S. (2006). Line Planning with Minimal Traveling Time. Paper presented at the 5th Workshop on Algorithmic Methods and Models for Optimization of Railways, Dagstuhl, Germany.
28. Zwaneveld, P. J., Kroon, L. G., & Ambergen, H. W. (1996). A decision support system for routing trains through railway stations. The 1996 5th International Conference on Computer Aided Design, Manufacture and Operation in the Railway and other Advanced Mass Transit Systems, COMPRAIL, 217–226.
29. Zwaneveld, P. J., Kroon, L. G., & van Hoesel, S. P. M. (2001). Routing trains through a railway station based on a node packing model. European Journal of Operational Research, 128(1), 14-33.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2014-08-29起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2014-08-29起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw