捷運司機員排班問題之研究 - 以台北捷運公司為例

Abstract

本研究之目的在於提出一有效的演算法以提升台北捷運公司司機員排班之效率。在研究中，將捷運司機員排班問題建構為集合分割(Set Partitioning)問題模式，並針對此模式設計求解演算法。演算法包含變數產生法(Column Generation)、分支定限法(Branch and Bound)與啟發式解法三階段。 在變數產生法求解階段，將主問題定式為集合涵蓋(Set Covering)問題放鬆整數限制與司機員個數限制後之線性規劃問題，子問題為有限制之最短路徑問題，求解目標主要在產生所有可行之工作班，以找到一較佳之起始可行解。接下來，對於變數產生法求解所得之非整數解結果，利用分支定限法求得整數解。最後，設計一啟發式解法以解決因變數產生法之主問題定式為集合涵蓋問題與放鬆司機員個數限制後，所可能產生之求解結果中任務卡過多，與部份任務卡中有重複涵蓋(Over-Cover)任務之問題。 利用演算法實際求解台北捷運公司司機員排班問題，所需求解時間相較於目前人工方式排班而言已大幅減少，將可提升司機員排班效率。在求解結果中，雖然可能會有少數任務無法排進班表中，但是可比照人工排班現況由領班或助理以備班方式執行。此外，本研究結果可改善人工排班時午班司機員用餐時間過短，而且無法排進班表之任務皆集中在午班用餐時段，所帶給司機員與排班人員的困擾。最後，在需要相同人數的備班司機員來執行那些無法排進班表之任務的情況下，演算法求解結果之總任務卡成本將較人工排班之總任務卡成本為低。

This thesis proposes an algorithm to improve the efficiency for solving the drivers scheduling problem of the Taipei MRT company. We formulate this problem as a set-partitioning problem. A three phases algorithm, column generation, branch-and-bound, and heuristic local search, is then developed for solving this model. First, We use column generation technique to generate all possible promising tasks. Then, branch and bound method is applied to obtain the integer. Finally, we develop a heuristic local search method to eliminate excess workdays and over-cover tasks, since we use the set-covering problem model in the first phase instead of the set-partitioning problem due to the difficulties of obtaining the feasible solution. We use the real cases of the Taipei MRT company as the numerical examples. The results show that our algorithm could get better solutions with higher operational feasibility than the current one does.