:::

詳目顯示

回上一頁
題名:限制規劃與整數規劃模式應用之比較:以捷運站務人員輪值問題為例
書刊名:運輸學刊
作者:韓復華 引用關係李俊德
作者(外文):Han, Anthony F.Li, Chun-te
出版日期:2008
卷期:20:3
頁次:頁229-254
主題關鍵詞:限制滿足問題限制規劃整數規劃捷運系統人員輪值問題Constraint satisfaction problemConstraint programmingInteger programmingMRTCrew rostering problem
原始連結:連回原系統網址new window
相關次數:
  • 被引用次數被引用次數:期刊(0) 博士論文(0) 專書(0) 專書論文(0)
  • 排除自我引用排除自我引用:0
  • 共同引用共同引用:17
  • 點閱點閱:74
人員輪值問題是運輸系統營運普遍面對的複雜限制滿足問題(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.
期刊論文
1.Brailsford, Sally C.、Potts, Chris N.、Smith, Barbara M.(1999)。Constraint Satisfaction Problems: Algorithms and Applications。European Journal of Operational Research,119,557-581。  new window
2.陳春益、趙時樑(20040900)。貨櫃碼頭出口儲區門型起重機小車取櫃問題之研究。運輸計劃,33(3),449-469。new window  延伸查詢new window
3.韓復華、李俊德(20070100)。兩階段限制規劃模式求解護理人員輪值問題。管理與系統,14(1),121-146。new window  延伸查詢new window
4.蘇昭銘、張靖(20001100)。捷運系統站務人員排班模式之研究。運輸學刊,12(2),1-14。new window  延伸查詢new window
5.Christodoulou, N.、Wallace, M.、Kuchenhoff, V.(1994)。Constraint Logic Programming and Its Application to Fleet Scheduling。Information and Decision Technologies,19(3),135-144。  new window
6.Henz, M.、Muller, T.、Thiel, S.(2004)。Global Constraints for Round Robin Tournament Scheduling。European Journal of Operational Research,153(1),92-101。  new window
7.Darmoni, S. J.、Fajner, A.、Mahé, N.、Leforestier, A.、Vondracek, M.、Stelian, O.、Baldenweck, M.(1995)。Horoplan: Computer-assisted Nurse Scheduling Using Constraint Based Programming。Journal of the Society for Health Systems,5(1),41-54。  new window
8.Cheng, B. M. W.、Choi, K. M. F.、Lee, J. H. M.、Wu, J. C. K.(1999)。Increasing Constraint Propagation by Redundant Modeling: An Experience Report。Constraints: An International Journal,4(2),167-192。  new window
9.Lustig, I. J.、Puget, J. F.(2001)。Program Does Not Equal Program: Constraint Programming and Its Relationship to Mathematical Programming。Interfaces,31(6),29-53。  new window
10.韓復華、張文助(2007)。以限制規劃模式構建運動賽程表-以中華職棒大聯盟為例。管理與系統,14(4),623-646。new window  延伸查詢new window
11.Yunes, T. H.、Moura, A. V.、Souza, C. C.(2005)。Hybrid Column Generation Approaches for Urban Transit Crew Management Problems。Transportation Science,39(2),273-288。  new window
會議論文
1.Wong, Y. C.、Chun, H. W.(2003)。Nurse Rostering Using Constraint Programming and Meta-level Reasoning。0。712-721。  new window
2.Guerinik, N.、Van Caneghem, M.(1995)。Solving Crew Scheduling Problems by Constraint Programming。Berlin, Germany。481-498。  new window
3.Kusumoto, S.(1996)。Nurse Scheduling System Using ILOG Solver。0。  new window
4.Halatsis, C.、Stamatopoulos, P.、Karali, I.、Bitsikas, T.、Fessakis, G.、Schizas, A.(1996)。Crew Scheduling Based on Constraint Programming: The PARACHUTE Experience。0。424-431。  new window
5.Shaw, P.(1998)。Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems。0。417-431。  new window
研究報告
1.Gronkvist, M.(2003)。Using Constraint Propagation to Accelerate Column Generation in Aircraft Scheduling。0。  new window
2.韓復華(1995)。休假排班及其人力需求規劃決策支援系統雛形建立。臺北市。  延伸查詢new window
學位論文
1.王國琛(2002)。結合限制規劃與數學規劃求解大型後艙空勤組員排班問題,0。  延伸查詢new window
2.唐依伶(2003)。以限制規劃求解公平性空服組員派遣問題-以座艙長為例,0。  延伸查詢new window
3.林詩芹(2003)。以限制規劃構建全年無休服務人員排班模式-以客服人員排班為例,0。  延伸查詢new window
4.蘇啟超(2004)。飛安查核工作排程與人員排班模式建立,0。  延伸查詢new window
圖書
1.Russell, S.、Norving, P.(2003)。Artificial Intelligence a Modern Approach。Artificial Intelligence a Modern Approach。0:Pearson Education。  new window
2.Williams, H. P.(1999)。Model Building in Mathematical Programming。Model Building in Mathematical Programming。New York, NY。  new window
3.Hillier, F. S.、Lieberman, G. J.(2005)。Introuction to Operations Research。Introuction to Operations Research。New York, NY。  new window
4.Apt, K. R.(2003)。Principles of Constraint Programming。Cambridge:Cambridge University Press。  new window
 
 
 
 
第一頁 上一頁 下一頁 最後一頁 top