混合限制規劃法及數學規劃法求解大眾捷運系統司機員排班與輪值問題

Abstract

司機員排班與輪值問題為大眾捷運系統營運時所面臨的重要議題之一。前者主要為求解涵蓋每日所有列車任務的最小勤務成本組合；後者則為制定司機員輪值表，確保輪值期內每日所有勤務均有司機員值勤。排班及輪值結果除直接影響人事成本外，規劃的勤務及輪值表內容亦將決定是否有給與司機員足夠的休息時間，避免疲勞駕駛而影響營運安全及顧客對企業之滿意度。

於實務上，捷運司機員排班與輪值除需滿足法規與公司規定外，另亦需儘量滿足司機員期望。在考量複雜的硬、軟限制下，即難以單純運用最佳化方法來求解，故本研究即提出運用限制規劃法與數學規劃法來建構相關模式。於司機員排班問題上，本研究先建構勤務產生限制規劃模式，產生滿足所有排班硬限制之可行勤務，並利用集合涵蓋模式求解最小勤務成本組合。此外，並依據可行勤務規模運用不同求解程序來求解最佳解。輪值問題則利用兩階段程序求解無固定班別的非週期性司機員輪值表。首先於第一階段利用目標規劃排休模式求解具休假公平之排休表。第二階段則運用勤務指派限制規劃模式，以第一階段結果為基礎，將每日勤務指派給需工作的司機員，並同時考量早班勤務、極早班勤務與長短班勤務公平分配軟限制。

本研究依據高雄捷運前鎮車班的實際資料與相關排班及輪值規定，求解3種車班表的最佳勤務組合與司機員月輪值表。於排班結果上，本研究除平日班表可節省2個勤務外，3種班表的勤務均較手排結果可較集中於8小時班並使用較少的加班勤務。此外，依據本研究勤務結果，輪值表可節省2位司機員即可涵蓋每日所有任務。於輪值表的休假公平性上，相較於手排輪值表，本研究可同時滿足司機員總休假數及總例假休假數公平性。而在早班、極早班與長短班勤務公平性上，亦可藉由限制規劃法的搜尋策略與範圍限制式來達到均勻分配的結果。運用本研究提出之有效率且具彈性的排班與輪值模式，規劃人員可快速地測試多種不同方案，尋找最合適的勤務與輪值表結果做為決策依據。

The article addresses driver scheduling and rostering problems for mass rapid transit (MRT) systems. The driver scheduling problem is to find a minimum cost of duties to cover all tasks for each timetable, and the driver rostering problem is to generate a roster to ensure each duty in a rostering horizon can be assigned to a driver. These problems are very important for MRT systems because of the results will affect labor costs and operational safety such as driver fatigue.

In real-world operations, the driver scheduling and rostering problems have to satisfy complex hard and soft rules. Such rules are complicated and difficult to follow through optimization methods alone. In this article, we propose a hybrid approach with constraint programming (CP) and mathematical programming (MP) models to solve these problems. The approach of the driver scheduling problem involves a CP model for duty generation, a set covering problem (SCP) model for duty optimization, and alternative ways to identify the final solution in different situation. For driver rostering problem, a two-phase heuristic approach is proposed to generate an acyclic roster. The first phase uses a goal programming (GP) model to solve the off-day scheduling. And the second phase applies a CP model to assign duties to drivers.

We applied our models to solve a case problem for the KRTC. Case application results using real-work data showed that our scheduling approach is capable of reducing the number of duties from 29 to 27 for the weekday timetable, and duties for each timetable can be more centralized in 8 hour shifts and less overtime shifts. According to the duties, we can save two drivers and our rostering approach can generate more equitable rosters such as the number of weekend-off, very early shifts etc. Given the efficient and flexible models, the manager can test different situations quickly to find more suitable duties and a roster.