篇名 | 限制規劃與整數規劃模式應用之比較:以捷運站務人員輪值問題為例 |
---|---|
卷期 | 20:3 |
並列篇名 | Comparison of Constraint Programming and Integer Programming Models: A Case Example of MRT Crew Rostering Problem |
作者 | 韓復華 、 李俊德 |
頁次 | 229-254 |
關鍵字 | 限制滿足問題 、 限制規劃 、 整數規劃 、 捷運系統 、 人員輪值問題 、 Constraint satisfaction problem 、 Constraint programming 、 Integer programming 、 MRT 、 Crew rostering problem 、 TSSCI |
出刊日期 | 200809 |
人員輪值問題是運輸系統營運普遍面對的複雜限制滿足問題(CSP)。蘇昭銘與張靖(2000)曾將捷運系統站務人員輪值的問題構建為整數規劃(IP)模式,並以小型例題驗證。本研究以臺北捷運公司為個案,對其站務人員的輪值問題同時構建限制規劃(CP)與IP兩種不同類型的模式,並進行求解與比較分析。在問題定義方面,本研究在限制條件中增加小班隔日不接早班的換班規定以符合實務的要求。在CP建模方面,以48種值班型態為基礎,構建站務人員輪值的CP模式;在IP建模方面,則將現有文獻的兩階段IP模式轉換為一階段的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.