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

Abstract

捷運公司為兼顧服務水準與營運成本，重要營運策略之一是規劃良好的列車運行計畫，其主要目的在於規劃最適的營運模式及班距，以滿足系統特性、列車數限制及服務指標規範，並求營運成本最小；但旅客依據列車運行計畫進行路徑選擇的結果，會影響原來預估的服務水準，因此捷運公司須重複修正列車運行計畫，形成了一個組合最佳化問題。 由於列車運行計畫具有問題規模大、限制式多、不可行解空間區域大等特性，依問題特性所構建的模式屬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.