捷運列車排班問題之研究-以基因演算法求解

Abstract

在大眾捷運系統營運計畫中，列車排班是其中一項重要工作。以台北捷運公司為例，目前以人工輔以電腦方式進行排班。倘若營運環境改變，就必須耗費多時重新進行列車排班，因此如何有效完成列車排班，乃營運單位所需面對之課題。

本研究的目的在考慮捷運列車營運特性及滿足各項限制條件，指派列車串接各班次，產生一個各列車應服務班次順序的排班結果。本研究發展一以基因演算法為基礎的演算法來進行求解，並以台北捷運文山內湖線實際班表進行實例測試以及相關的敏感度分析。測試結果顯示本演算法能產生可行的捷運列車班表，此外敏感度分析顯示迭代次數與突變發生機率對於目標值的改善並不顯著。

Train scheduling is one of the main tasks for mass rapid transit operations. Taipei Rapid Train Corporation, for example, needs to spend days to make up a new schedule whenever the operation parameters are changed. Thus, an efficient and effective train scheduling system is in need. This research proposed a genetic algorithm based train-scheduling algorithm for assigning a sequent ordered tasks to each train. This algorithm accommodated operations characteristics and various practical constraints.

A real world data from Taipei Metro Wenhu line was used for testing purpose. The testing results indicated that the proposed algorithm is capable of producing feasible train schedules. Furthermore, the sensitivity analysis indicated that the impacts of number of iterations and mutation rate are not significant