捷運列車排班問題之研究—以台北捷運淡水-新店線為例

Abstract

本研究探討捷運列車之排班，並以「台北捷運淡水-新店線」為實證對象。研究的主要目的是以台北捷運公司所擬定之列車營運模式為基礎，考量系統特性(列車停靠、終端站折返、軌道號誌…等限制)，提出一有效的求解方法於捷運列車排班，以擬定合適的列車運行時刻表，提升列車排班效率。 本研究將捷運列車排班定義為「調整列車於終端站的折返時間或班次發車時刻，以銜接執行班次並避免列車衝突情形」。首先，針對列車折返銜接執行班次，應用變數產生法(Column Generation Method)的概念，定式主問題為放鬆整數限制與列車數限制之集合分割問題(Set Partitioning Problem)、子問題為最短路徑網路問題，尋找具有較低成本之任務，以求得一個尚未考慮列車衝突的較佳起始時刻表。然後檢查起始時刻表找出列車的衝突，提出兩種演算法來解決列車衝突的情形，以獲得可行的列車運行時刻表。 本研究以實際例題測試所提出的求解方法，以變數產生法所求得的起始時刻表能滿足淡水-新店線所提供的列車數限制，並可充分反應列車排班之現況；而且有列車衝突的情形很少，所以兩種解決衝突演算法都能很快求得可行的列車運行時刻表。求得的可行時刻表不僅能滿足列車運行班距規定與列車數限制，而且不會發生列車因衝突而停等的情況；整個列車排班問題的求解均可在一日24小時內完成，大幅改善列車排班的效率。

This thesis focuses on the Taipei mass rapid transit train scheduling problem, especially the TamShui and Hsintien line. We propose an efficient three-stage algorithm for solving this problem. In the first stage, we adopt the column generation technique to generate all possible promising train schedules. Then, we use branch and bound method to determine which schedules will be selected to yield the initial timetable. In the third stage, we examine the initial timetable and develop two heuristic methods to take care of the conflicts occurred on trains and platform. This algorithm was tested on several realistic examples suggested by the Taipei MRT Company. The test results show the column generation method could generate a not-too-bad initial timetable and the heuristic methods could successfully solve the conflicts occurred and make the final solution feasible. Most importantly, our algorithm could obtain the “pseudo” optimal solution in 20-30 hours in stead of 7 full days under the current operation.