Optimizing the Routing of Trains with Heterogeneous Traffic

在全球因為能源短缺，朝向節能減碳趨勢邁進時，軌道系統容量需求將大幅的增加。然而，世界上多數軌道系統之容量正趨近於飽和。面對運輸需求之增加，如何有效的運用軌道系統資源，協助規劃人員建立有效率又可靠的服務規劃，是目前軌道運輸系統重要的課題之一。一般而言，提升軌道容量的方式可分為兩大類，第一類是在控制與運轉策略中做改變，第二類是在基礎建設上做擴充。因為改善運轉策略的花費較少，成效也比較迅速，所以常會優先考慮。而在此類策略改善方式中，混合列車組成（異質性）對軌道容量影響是十分重要的，不同的車種運行時，彼此間會車與超車會造成可觀的延滯。因此，透過調整列車路徑指派可以降低每個路段上的列車異質性，進而提升軌道容量與降低系統延滯。 本研究建立一套考量異質性的列車路徑指派模式，此模式根據軌道系統資料，決定列車運行時間和維修成本的方程式，估算各種混合列車組成下的運行時間成本和維修成本，再運用數學規畫方法找出最佳的列車路徑指派策略。由於所建構的最佳化模式屬於NP-Hard問題，若使用傳統數學規畫解法無法在CPLEX平台上無法求得整數規劃之最佳解，因此本研究應用Lagrangian Relaxation分解法將最佳化模式分解，結合次梯度法提升最佳化模式求解能力。經過24個結點，40條路段的類九宮格型態路網測試決策程序，大約可節省約3~5%的營運成本。運用此決策工具可協助規劃人員建立有效率且可靠的列車運轉策略，減少異質性造成的衝擊，如此可有效降低列車運行時間，進而降低營運成本；降低運行時間同時也減少延滯發生，間接提升運輸系統之可靠度。Long-term demand for rail traffic worldwide is expected to expand increasingly leading to capacity constraints. Although both infrastructure investment and operational changes can relieve congestion, careful consideration of how operational practices can affect or mitigate demand is critical for cost-effective planning of new capacity, especially considering the high cost to build and maintain infrastructure. A critical aspect of capacity management is to understand the effect of heterogeneous traffic on capacity. Greater heterogeneity on a line increases interference between trains and creates more delay than if all trains have similar characteristics. In this research, we take into account the impact of heterogeneity and present a new optimization framework to identify the optimal train network routing. We also implement Lagrangian Relaxation with Subgradient optimization method to solve this problem efficiently. Computational results show the use of this tool can successfully reduce operational costs by 3 to 5 %. This tool will help service design managers on traffic routing and capacity utilization