應用基因演算法於捷運列車運行計畫之研究

Mass Transit Operational Route Design Using Genetic Algorithm

林誌銘(Chih-Ming Lin)

指導教授 ： 王晉元

國立交通大學/管理學院/運輸科技與管理學系/博士(2009年)

https://doi.org/10.6842/NCTU.2009.00189

摘要

捷運公司為兼顧服務水準與營運成本，重要營運策略之一是規劃良好的列車運行計畫，其主要目的在於規劃最適的營運模式及班距，以滿足系統特性、列車數限制及服務指標規範，並求營運成本最小；但旅客依據列車運行計畫進行路徑選擇的結果，會影響原來預估的服務水準，因此捷運公司須重複修正列車運行計畫，形成了一個組合最佳化問題。
由於列車運行計畫具有問題規模大、限制式多、不可行解空間區域大等特性，依問題特性所構建的模式屬NP-hard性質，難以保證可求得最佳解，故本研究應用可全域搜尋、容易增加限制式的基因演算法來求解，提出了適合列車運行計畫的網路構建方式、二個快速的可行啟始解產生法、三個交配運算子及一個突變運算子；在敏感度分析後採用適合的交配率及突變率組合，及比較執行結果後找出適合的啟始解產生法與交配運算子的組合，並藉由基因修補機制、特殊的適合度函數及檢測重複機制來加速尋優過程，使得演算法能兼顧求解品質及速度。
最後，藉由臺北捷運公司高運量系統路網的實例驗證，探討如何進行營運模式及班距決策，驗證結果顯示本演算法具有穩定性、實用性及良好求解品質，可作為捷運公司之參考。

關鍵字

捷運系統 ； 列車運行計畫 ； 基因演算法

並列摘要

The mass transit operational route design problem (MTORDP) is a NP-hard problem and difficult to solve for a global optimum solution. This thesis proposes a genetic algorithm for solving the MTORDP. In the proposed algorithm, two smart algorithms are designed to generate initial feasible solution rapidly. An adequate network model, a gene repairing strategy and a redundancy checking mechanism were developed to minimize the computation time. Improved fitness function was embedded with the passenger assignment model and utilized to improve the quality of the solution. The proper combination of crossover operators and mutation operators was decided for the MTORDP.
The proposed algorithm was tested with the current MRT network in Taipei as a specimen. Results indicate that the proposed algorithm is effective in solving real-world problems.

並列關鍵字

Mass transit systems ； Operational Route Design ； Genetic algorithm

參考文獻

[27]李治綱，謝汶進，「應用雙層次規劃於高速鐵路列車服務設計之研究」，運輸計劃季刊，第三十一卷第一期，95-120頁，民國91年3月。

[31]張學孔，郭瑜堅，「都市旅次總成本模式構建之研究」，運輸計劃季刊，第三十六卷第二期，147~182頁，96年6月。

[9]周義華，黃勵君，「捷運系統最適營運路線設計之研究」，中華民國運輸學會第十五屆研討會論文集，民國89年12月。

[2]Guan, J. F., Yang, H., and Wirasinghe, S. C., “Simultaneous Optimization of Transit Line Configuration and Passenger Line Assignment,” Transportation Research Part B, Vol. 40, Issue 10, pp. 885-902, 2006.

[7]Guihaire, V., and Hao, J. K., “Transit Network Design and Scheduling: A Global Review,” Transportation Research Part A, Vol. 42, Issue 10, pp. 1251-1273, 2008.