整合限制規劃與數學規劃求解大眾捷運系統司機員排班問題

COMBINING CONSTRAINT PROGRAMMING AND MATHEMATICAL PROGRAMMING TO SOLVE THE CREW SCHEDULING PROBLEM FOR MASS RAPID TRANSIT SYSTEMS

司機員排班問題為大眾捷運系統營運時所面臨的重要議題之一。本研究將司機員於用餐完得以直接簽退之彈性納入考量，在滿足實務限制下，運用限制規劃法與數學規劃法來分別構建司機員任務產生模式與任務優化模式。前者主要產生符合所有排班營運限制之可行任務；後者主要求解涵蓋每日列車勤務的最小任務成本組合，其結果不僅攸關系統營運時的人事成本，更直接決定司機員的休息時間是否足夠，進而影響系統的營運安全。於案例分析上，本研究以國內某軌道營運機構之實際資料與相關排班規定為例進行測試，相較於人工排班結果，透過本研究所提出之兩階段求解架構能夠確實地節省人事成本，以較少任務數涵蓋所有列車勤務，且規劃人員亦可快速地測試多種不同方案，並提供決策單位作為司機員排班規劃之參考。

This paper addresses the crew scheduling problem for mass rapid transit systems. The problem aims to find a duty arrangement with minimal cost that covers all tasks satisfying the scheduling and operating rules. We employ a hybrid approach to solve the problem with a constraint programming model for duty generation and a mathematical programming model for duty optimization. We apply the models to a real-world MRT company in Taiwan. The results show that the proposed solution approach is more efficient than manual scheduling process and can achieve 3% savings of labor cost.