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

A GENETIC ALGORITHM MODEL FOR MRT TRAIN SERVICE PLANNING

捷運公司為兼顧服務水準與營運成本，重要營運策略之一是規劃良好的列車運行計畫，其主要目的在於規劃最適的營運模式及班距，以滿足系統特性、列車數限制及服務指標規範，並求營運成本最小；但旅客依據列車運行計畫進行路徑選擇的結果，會影響原來預估的服務水準，因此捷運公司須重複修正列車運行計畫，形成了雙層次規劃問題。由於列車運行計畫具有問題規模大、限制式多、不可行解空間區域大等特性，依雙層次規劃問題架構所構建的模式又屬NP-Hard性質，難以保證可求得最佳解，故本研究應用可全域搜尋、容易增加限制式的基因演算法來構建模式求解，並針對列車運行計畫問題特性，設計特殊的尋優策略以加速求解時間及確保求解品質。最後以臺北捷運公司現行高運量系統路網作為實例驗證，探討如何進行營運模式及班距決策，驗證結果顯示本研究模式的穩定性、實用性及求解品質，可作為捷運公司之參考。

The MRT train service plan is a kind of bi-level programming problem. For MRT companies, the decision about service mode and headway is the upper-level problem. The goal is to minimize the operational cost under the constraints of MRT system and service performance index (SPI). The lower-level problem is passengers’ route choice model, for their main concern is to minimize their travel time and cost, which consequently influences the SPI. This study presents a genetic algorithm for MRT train service planning to solve the bi-level programming problem. In addition, the proposed model was tested with the current network of Taipei Rapid Transit Corporation (TRTC). The results suggest that the model and solution algorithm with high stability, feasibility and solution quality is useful for TRTC.