以多元物流模式最佳化鐵路系統營運路線

Optimization of Railway Line Planning Process using Multi-Commodity Flow Model

陳桂豪(Guei-Hao Chen)

指導教授 ： 賴勇成

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

https://doi.org/10.6342/NTU201603553

摘要

傳統鐵路長期以來一直是國內交通運輸的主幹之一，為因應旅客需求的變化，鐵路系統應定期檢視營運路線規劃。一般來說，營運路線規劃課題之目標大致可區分為營運者導向與使用者導向兩大類。在營運者導向層面，其決策目標通常以最小化系統營運所需的成本為依歸，並考量軌道容量、服務需求等限制。在使用者導向方面，通常以旅客之乘車時間最小化為目標建立數學模式，並對轉乘旅客給予懲罰值。過往研究鮮少同時將營運者導向與使用者導向納入決策模式的考量之中。此外，其考慮之營運成本因子主要偏向營運路線之固定與變動成本，並未考慮列車承載率在各路段是否高於ㄧ定的水平。而列車承載率的高低恰好可作為營運業者是否妥善利用運能的績效指標之一，因此本研究除了同時考慮營運者與使用者面相之外也將承載率一併納入決策模式中。
回顧過往文獻，在規劃營運路線時，欲輸入模式的資料皆已包含可行之營運路線與其起訖點，並從給定之集合中進行選擇，而後續的機廠設置也依據營運路線起訖之分佈來進行配置。然而，針對台灣的環島鐵路系統而言，有關營運路線的規劃需先決定端點車站的數量與位置，營運路線之起訖反而成為重要之決策因子。基於此點考量，本研究以多元物流網路建立ㄧ數學模式，以最小化營運者成本、使用者成本與未使用之運能為目標，欲以台灣的環狀鐵路路網為背景規劃出系統營運路線所需的起訖與數量，並同時決定其初步的服務頻率。此外，為了提升求解效率，本研究亦以數學模式為基礎發展出啟發式演算法，透過預先生成潛力路線之集合再從中進行最佳化選定的機制，來加速求解流程。案例分析之結果證實所決策之營運路線起訖與旅客流指派可作為長期鐵路建設發展的規劃參考。

關鍵字

鐵路運輸 ； 營運路線規劃 ； 多元物流模式 ； 混合整數規劃 ； 啟發式演算法

並列摘要

Line planning is one of the crucial procedure in railway operational planning process. Based on the passenger demand, this procedure aims to design appropriate routes and preliminary frequencies of services. Most of past studies on this subject considered only operating cost in terms of operators or transportation costs in terms of passengers. Few studies did combine both types of costs but did not closely check the match between the supply and demand across all segments. This research develops a multi-commodity flow model to determine a set of optimal service lines for a railway system by minimizing the operating cost, transportation cost, and loss in opportunity cost (due to empty seats). To enhance the solution efficiency, a solution algorithm was also developed to facilitate the solution process by separating the process of forming potential lines and the process of choosing the optimal set of service lines. Results of case studies suggest that the proposed models can identify the optimal lines and optimal passenger assignment. Using this line planning optimization process can help TRA design optimal lines corresponding to demand.

並列關鍵字

Rail Transportation ； Line Planning ； Multi-Commodity Flow Model ； Mixed Integer Programming ； Solution Algorithm

參考文獻

Bornd ouml;rfer, R., Gr ouml;tschel, M. and Pfetsch, M. E. 2008. Models for Line Planning in Public Transport. Computer-aided Systems in Public Transport 600: 363–378.

Bornd ouml;rfer, R., Gr ouml;tschel, M. and Pfetsch, M. E. 2007. A Column-Generation Approach to Line Planning in Public Transport. Transportation Science 41(1): 123–132.

Bornd ouml;rfer, R. and Pfetsch, M. E. 2005. Routing in Line Planning for Public Transportation. Operations Research Proceedings 2005: 405–410.

Bussieck, M. R., Lindner, T. and Lubbecke, M. E. 2004. A fast algorithm for near cost optimal line plans. Mathematical Methods of Operation Research 59: 205–220. 


Bussieck, M. R., Kreuzer, P. and Zimmermann, U. T. 1996. Optimal lines for railway systems. European Journal of Operation Research 96(1): 54–63.