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

Abstract

運動排程(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.