限制規劃與整數規劃模式應用之比較：以捷運站務人員輪值問題為例

Comparison of Constraint Programming and Integer Programming Models: A Case Example of MRT Crew Rostering Problem

人員輪值問題是運輸系統營運普遍面對的複雜限制滿足問題（CSP）。蘇昭銘與張靖（2000）曾將捷運系統站務人員輪值的問題構建為整數規劃（IP）模式，並以小型例題驗證。本研究以臺北捷運公司為個案，對其站務人員的輪值問題同時構建限制規劃（CP）與IP兩種不同類型的模式，並進行求解與比較分析。在問題定義方面，本研究在限制條件中增加小班隔日不接早班的換班規定以符合實務的要求。在CP建模方面，以48種值班型態為基礎，構建站務人員輪值的CP模式；在IP建模方面，則將現有文獻的兩階段IP模式轉換為一階段的IP模式。本研究亦設計站務人員3至14人，六個不同情境之數值範例，利用ILOG OPL Studio 3.7軟體求解與測試CP與IP兩類模式。結果顯示，CP模式不論在模式構建的難易度、求解效率與結果上均優於IP模式。當站務人員規模增加至6人時，IP模式已無法求解；而CP模式仍能在合理時間（約11分鐘）內求解出14人的輪值月班表。整體而言，對求解站務人員輪值問題，CP模式應較IP模式更具實際應用之潛力。

The crew rostering problem of a mass rapid transit (MRT) system is a difficult Constraint Satisfaction Problem. Su and Chang (2000) proposed an IP (Integer Programming) model to solve the problem and applied it to several small numerical examples. In this paper, we developed both CP (Constraint Programming) and IP models for the MRT crew rostering problem, and made a comparative study of their performance. For the CP approach, we expanded the rostering constraints and proposed forty-eight patterns to construct a pattern-based CP rostering model. As to the IP approach, we converted the conventional two-phase IP model into a single-phase IP model. We also designed six test problems with different scenarios. The number of crews of the test problems ranges from three to fourteen. Results showed that the CP model performs better than the IP model. The IP model works only for the smallest problem with three crew members. On the other hand, the CP model can easily generate a full-month roster with 14 crew members. As compared to the IP model, we found that the CP model seems to be a more powerful tool for practical applications to the MRT crew rostering problem.