模擬退火法求解捷運司機員輪班問題 -以台北捷運公司為例

捷運司機員輪班問題是一個複雜的組合優化問題，良好的輪班表有助於提升司機員的執勤效率，間接提升捷運的服務品質。本研究以台北捷運公司淡水段北投車班為研究對象，針對正線執勤司機員之輪值班表產製問題進行求解。本研究發展模擬退火演算法求解能符合台北捷運公司車務排班規定之司機員輪值班表。為能符合現行實務上之需求，本研究將問題分為二階段求解。第一階段為求解司機員排休問題，並加入了休假天數公平性因子，使其在滿足個人預排休假之需求及捷運公司排班規定之休假限制的情況下，仍可對司機員之休假數量具有相當的公平性分配。第二階段求解則處理司機員任務卡之分派問題，目標是在所有任務卡皆完整分配後，讓每一位司機員當月任務卡卡號不重覆，此一做法不僅可平衡每一位司機員之勤務負擔，更同時兼顧到讓所有司機員單月總駕駛時數接近之目的。最後總合二階段之結果即可得出最終所需之司機員輪值班表。為了測試所發展演算法的績效，本研究針對四個實際範例問題進行求解，結果顯示此演算法所產製的輪班表比目前實務運作的輪班表有更好的目標值，且運算時間更短，此一結果達成本研究的目的，也可作為台北捷運公司產製輪班表之參考。

關鍵字

模擬退火法；人員輪班問題；捷運系統

並列摘要

The crew rostering problem of MRT drivers is a complex combinatorial optimization problem. A good rostering can increase crew's efficiency and improves the service quality of MRT. This study solves the crew rostering problem for the Tamsui Section of TRTC. This study develops a simulated annealing (SA) algorithm to obtain the crew roster which is able to satisfy the regulations of TRTC. In order to follow the practical requirements, the solution process consists of two phases. The first phase solves the day-off scheduling problem, which considers the fairness in number of days-off among the drivers. The objective is to fairly allocate days-off to the drivers, while satisfying the regulations of TRCT. The second phase deals with the assignment of duties to the drivers, considering the workload balance among the drivers. The crew roster is obtained by combing the results of the two phases. This study evaluates the performance of the proposed algorithm using four real problem instances of TRTC. The results show that the SA algorithm is able to obtain a better roster for each of the instance in a shorter amount of time. The proposed method can be a useful reference to the crew rostering of TRTC.

並列關鍵字

Simulated Annealing ； Crew Rostering Problem ； Mass Rapid Transit System

參考文獻

1.Beasely, J. E., and B. Cao (1996), “A Tree Search Algorithm for the Crew Scheduling Problem,”European Journal of Operational Research, Vol.94,No.3, pp.517-526.