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

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

韓復華(Anthony F. Han) ； 李俊德(Chun-Te Li)

《運輸學刊》 20卷3期 (2008/09) Pp. 229-254

https://doi.org/10.6383/JCIT.200809.0229

摘要

本研究亦設計站務人員3至14人，六個不同情境之數值範例，利用ILOG OPL Studio3.7軟體求解與測試CP 與IP 兩類模式。結果顯示，CP模式不論在模式構建的難易度、求解效率與結果上均優於IP模式。當站務人員規模增加至6人時，IP模式已無法求解；而CP模式仍能在合理時間（約11分鐘）內求解出14人的輪值月班表。整體而言，對求解站務人員輪值問題，CP模式應較IP模式更具實際應用之潛力。人員輪值問題是運輸系統營運普遍面對的複雜限制滿足問題(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.

並列關鍵字

constraint satisfaction problem ； Constraint programming ； Integer programming ； MRT ； Crew rostering problem

參考文獻

王國琛(2002)。結合限制規劃與數學規劃求解大型後艙空勤組員排班問題(碩士論文)。交通大學運輸科技與管理學系。

林詩芹(2003)。以限制規劃構建全年無休服務人員排班模式－以客服人員排班為例(碩士論文)。交通大學運輸科技與管理學系。

唐依伶(2003)。以限制規劃求解公平性空服組員派遣問題－以座艙長為例(碩士論文)。交通大學運輸科技與管理學系。

陳春益、趙時樑(2004)。貨櫃碼頭出口儲區門型起重機小車取櫃問題之研究。運輸計劃季刊。33(3)，449-469。

韓復華()。,未出版。