以限制規劃模式構建運動賽程表－以中華職棒大聯盟為例

Constraint Programming Models for Sports Scheduling Problem-A Case Study of Chinese Professional Baseball League

韓復華(Anthony Fu-Wha Han) ； 張文助(Wen-Chu Chang)

《管理與系統》 14卷4期 (2007/10) Pp. 623-646

摘要

運動排程(sports scheduling)的問題在探討如何安排參賽隊伍的比賽時間表與其對應的場地。職業球賽賽制複雜，賽程安排是一個NP-hard的問題。本文針對我國中華職業大聯盟之賽程為個案進行探討。首先將問題列式為一個限制滿足問題(Constraint Satisfaction Problem, CSP)，其次以限制規劃(Constraint programming, CP)模式構建一個三階段求解的啟發式架構，分別依序處理三連戰賽程，四連戰賽程，與場地安排三個子問題。各限制規劃模式構建於ILOG OPL Studio系統，並在Windows XP個人電腦上執行求解。本研究依據中華職棒16年（2005年）六個球隊與十三個場地的實際狀況，求解得到上、下半球季各15週，總共300場比賽的賽程表結果。與實際賽程表比較發現，本研究之結果在求解效率、賽制完整性與主場公平性等各方面均有優越之處，顯示本文建立之模式具實際應用價值。

關鍵字

運動排程 ； 賽程排程 ； 限制滿足問題 ； 限制規劃 ； 中華職棒大聯盟

並列摘要

Sports scheduling is a NP-hard problem particularly for professional sports. This paper is focused on the sports scheduling problem of the Chinese Professional Baseball League (CPBL) in Taiwan. We formulated the problem as a CSP (Constraint Satisfaction Problem), and developed CP (Constraint programming) models to solve it. A three-phase heuristic approach is proposed to first generate partial solutions of the four-game-in-a-week schedule and the three-game-in-a-week schedule, and then to compile a complete solution with stadium assignment. The CP models were built using ILOG OPL Studio system, and the implementation was carried out on a Windows-XP PC with 2.8 GHz CPU. We successfully generated a full-year CPBL schedule in about 30 minutes. The full-year schedule results include two half-year seasons each contains 150 games covering a time period of 15 weeks, with six teams and thirteen stadiums. We also compared our results with the 2005 CPBL official timetable. It is found our results are better than the CPBL timetable in many ways. In terms of solution efficiency, our proposed method took about 30 minutes to generate the results, while the CPBL took about one week. Moreover, our results are also better on the aspects of equal host team advantage, more coverage of stadiums used, etc. Results imply that the proposed CP models are applicable to deal with the real-world CPBL scheduling problem.

並列關鍵字

Sports Scheduling ； Sports Timetabling ； Constraint Satisfaction Problem ； Constraint Programming ； Chinese Professional Baseball League

參考文獻

韓復華、李俊德(2007)。兩階段限制規劃模式求解護理人員輪值問題。管理與系統。14(1)，121-146。

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

Bean, J. C.,Birge, J. R.(1980).Reducing Travelling Costs and Player Fatigue in the National Basketball Association.Interfaces.10(3),98-102.

Brailsford, S. C.,Potts, C. N.,Smith, B. M.(1999).Constraint Satisfaction Problem: Algorithms and Applications.European Journal of Operational Research.119(3),557-581.

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.