跳到主要內容

臺灣博碩士論文加值系統

(54.224.133.198) 您好!臺灣時間:2022/01/27 03:54
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:楊博凱
研究生(外文):Po-Kai Yang
論文名稱:軌道列車排點模式與求解方法
指導教授:李宇欣李宇欣引用關係
指導教授(外文):Yu-Sin Lee
學位類別:碩士
校院名稱:國立成功大學
系所名稱:土木工程學系碩博士班
學門:工程學門
學類:土木工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:89
中文關鍵詞:求解方法鐵路排點
外文關鍵詞:scheduling model
相關次數:
  • 被引用被引用:5
  • 點閱點閱:654
  • 評分評分:
  • 下載下載:148
  • 收藏至我的研究室書目清單書目收藏:1
  鐵路系統具有運量大以及可靠性佳等優點,成為大眾運輸系統中最重要的運輸系統之一。傳統上鐵路運輸系統均以人工或是半人工方式完成鐵路排點,為了提高效率與品質,發展自動化鐵路排點方法有其重要性。
  本研究的目的為針對鐵路排點問題,利用數學規劃方式建構一數學模式以及求解方法,並針對模式反覆求解過程加入改善求解速度策略。由於列車錯會車計劃與列車運行時間並無絕對的關係,故建立鐵路排點問題模式時可依據問題性質劃分成順序模式與排點模式兩個部分。兩模式間之關係為排點模式依照順序模式所求得之順序,建立限制式並求得所有站間行程之起迄時間,並將所得站間行程之起迄時間轉換成列車事件之先後順序,與順序模式比較其求解結果,不一致的部分將調整兩模式內之相關參數以逐漸改善最佳解。
  研究中並提出三種改善求解速度的方法。其一為產生起始可行順序解,並以此作為順序模式起始基底縮短尋找最佳解的時間。其二為減少排點模式內不必要的順序限制式。任何違反順序模式求解結果會造成懲罰值產生,因此部分順序限制式因違反後產生的懲罰值過高而使排點模式求解後保持相同順序,則此順序限制式可視為不需要並簡化之以加快求解過程。最後因兩模式反覆求解之特性,每回合所得之最佳解可以此作為下一回合的基底解使用,藉以縮短求解時間。由鐵路排點之求解結果皆顯示本研究所提出之數學模式與求解方法具有極大的潛力,可於日後加入更多考慮因素並應用於實務工作。
  The railroad is one of the most important transportation system due to its great capacity and excellent reliability. Traditionally, rail scheduling in transpotation system is done manually or semi-manually. It is thus important to automize the work of rail scheduling in order to improve efficiency and quality.
  This research proposes a mathematical model and a heuristic to solve the rail scheduling problem, and proposes methods to impove the solution speed. Because meet-pass requirements and the arrival and departure times of trains are not strictly related, the rail scheduling problem can be decomposed into two parts, namely the ordering model and the scheduling model. The scheduling model builds its constraints according to the order obtained by solving the ordering model, and outputs the the arrival and departure times for each train. After that, the solution heuristic compares the ordering model and the timing model to identify conflicts between them. These conflicts are resolved by adjusting parameters iteratively in both models.
  The research proposes three methods for improving the speed in solving the problem. The first method is to generate a reasonable initial order according to the meet-pass requirements, and use the order as the initial basis of the ordering model to shorten the solution time. Another method to speed up the solution process is to eliminate certain constraints from the scheduling model. Any violation to these constraints is highly penalized due to the effect of other constraints, therefore they are unlikely to be binding are thus can be eliminated. The third method is to save the optimal basis of each of the two models and use them as the initial basis in the following iteration. Doing so will further cut down the solution time.
  Testing results show that the proposed mathematical models and the solution heuristic have the portential for future use in practice after more consideration factors are added.
摘要 I
Abstract IV
誌謝 V
目錄 VI
表目錄 VIII
圖目錄 IX

第一章 緒論 1
  1.1 概說 1
  1.2 研究動機與目的 1
  1.3 研究方法與流程 2
  1.4 論文架構 3

第二章 文獻回顧 4

第三章 研究問題定義 9
  3.1 鐵路規劃流程 9
  3.2 鐵路排點問題界定與描述 11

第四章 數學模式 15
  4.1 基本假設 15
  4.2 鐵路排點 16
    4.2.1 單軌順序模式 16
    4.2.2 多軌順序模式 20
    4.2.3 多軌順序模式之擴充 24
    4.2.4 排點模式 26
    4.2.5 求解架構 30
    4.2.6 調整權重係數:推廣鬆弛調整法 31
  4.3 改善求解速度之策略 39
    4.3.1 產生起始可行順序解 39
    4.3.2 廣義排點模式精簡策略 46
    4.3.3 前回合基底解之使用與CPLEX相關指令 47

第五章 模式測試 50
  5.1 鐵路排點相關測試 50
    5.1.1 單軌模式之相關測試 50
    5.1.2 多軌模式之正確性測試 52
    5.1.3 多軌模式之相關測試 54
    5.1.4 值與 值之相互關係 56
  5.2 改善求解速度相關測試 57
    5.2.1 產生起始可行順序解之相關測試 58
    5.2.2 廣義排點模式精簡策略之相關測試 59
    5.2.3 前回合基底解之使用 63
    5.2.4 綜合測試 64
  5.3 大規模問題之綜合測試 66

第六章 結論與後續研究 72
  6.1 結論 72
  6.2 後續研究 73

參考文獻 74
附錄A 76
A.1 單軌順序模式 76
A.2 多軌順序模式 77
A.3 排點模式 79
附錄B 83
B.1 符號定義 83
B.2 流程說明 83
簡歷 89
1.B. Adenso-Díaz, M. Oliva González and P. González-Torre, “On-line timetable re-scheduling in regional train services,” Transportation Research-B, vol.33, pp.387-398, 1999.

2.A. A. Assad, “Modelling of rail networks: toward a routing/makeup model,” Transportation Research-B, vol.14, no.3, pp.101-114, 1980.

3.U. Brännlund, P. O. Lindberg, A. Nou and J.-E. Nilsson, “Railway timetabling using lagrangian relaxation,” Transportation Science, vol.32, no.4, pp.358-369, 1998.

4.T. W. Chiang, H. Y. Hau, H. M. Chiang, S. Y. Ko and C. H. Hsieh, “Knowledge-based system for railway scheduling,” Data & Knowledge Engineering, vol.27, pp.289-312, 1998.

5.O. Frank, “Two-way traffic on a single line of railway,” Operations Research, vol.14, pp.801-811, 1966.

6.B. S. Greenberg, R. C. Leachman and R. W. Wolff, “Predicting dispatching delays on a low speed, single track railroad,” Transportation Science, vol.22, no.1, pp.31-38, 1988.

7.S. F. Hallowell and P. T. Harker, “Predicting on-time line-haul performance in scheduled railroad operations,” Transportation Science, vol.30, no.4, pp.364-378, 1996.

8.A. Higgins and E. Kozan, “Modelling train delays in urban networks,” Transportation Science, vol.32, no.4, pp.346-357, 1998.

9.D. Jovanovic and P. T. Harker, “Tactical scheduling of rail operations: the SCAN I system,” Transportation Science, vol.25, no.1, pp.46-64, 1991.

10.D. Kraay, P. T. Harker and B. Chen, “Optimal pacing of trains in freight railroads: model formulation and solution,” Operations Research, vol.39, pp.82-99, 1991.

11.D. R. Kraay and P. T. Harker, “Real-time scheduling of freight railroads,” Transpn. Res.-B. vol.29B, no.3, pp.213-229, 1995.

12.E. R. Petersen, A. J. Taylor and C. D. Martland, “An introduction to computer-assisted train dispatching,” Journal of Advanced Transportation, vol.20, no.1, pp.63-72, 1986.

13.R. L. Sauder and W. M. Westerman, “Computer aided train dispatching: decision support through optimization,” Interfaces, vol.13, pp.24-37, 1983.

14.B. Szpigel, “Optimal train scheduling on a single line railway,” Operations Research. vol. 72, pp.344-351,1973.

15.李治綱,謝汶進,「鐵路列車排點模式之建立」,運輸計劃季刊,第二十五卷第四期,pp.545-564,中華民國85年。

16.李宇欣、吳坤鴻、楊博凱、龐萬潮,「單軌鐵路排點與錯會車模式」,新世紀軌道運輸國際學術研討會,2000年10月。

17.沈進成,「高速鐵路最適停站方式」,國立成功大學交通管理研究所博士論文,民國85年。

18.陳立文,「鐵路列車排程與排點模式」,國立成功大學土木工程研究所碩士論文,民國90年。

19.陳潔如,「考慮轉車之鐵路列車排點模式」,國立成功大學土木工程研究所碩士論文,民國90年。
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top