以限制規劃模式求解運動賽程表

A constraint programming approach to the sports scheduling problem

10.6646/CYPEJ.201712_(11).0011

蔡宗憲(Chung-Hsien Tsai)；陳宇倫(Yu-Lun Chen)；徐錦興(Jin-Xing Xu)

運動排程 ； 三連戰賽制 ； 虛擬球隊 ； 限制滿足問題 ； Sports Scheduling ； Tri-consecutive Game Model ； Virtual Team ； Constraint Satisfaction Problem

中原體育學報

11期（2017 / 12 / 01）

106 - 116

繁體中文

研究建構限制規劃模式(Constraint Programming，CP)求解滿足場地與時間限制條件的賽程表。目標是使19支參賽隊伍在兩座場地（三面球場）出賽的次數相同，且各隊在單日多重賽時受隔場限制的條件相同，達到機會均等的公平原則。三連戰制度的創設為本文之特點，作用於集中出賽場次，降低賽程延誤的可能性。在求解過程中加入若干虛擬球隊滿足限制條件，使產出之賽程表符合實際的需求，顯示研究所採用的模式確能有效率的解決運動排程問題。

The purpose of this paper is to create the single round robin tournament schedules for 19 teams that satisfy venues availability and various timing restrictions. To this end, a constraint programming approach is employed as the methodology to solve the problem. The proposed schedule is reasonably fair to each team, thus games between team and team are assigned at three venues on specific time with evenly spaced throughout the season. By introducing a tri-consecutive game model, the schedule for individual teams is concentrated; the delay of games is therefore reduced significantly which is a valuable property when real sports leagues are considered. Results imply that after several virtual teams are added to the scheduling process to meet all the requirements, the constraint programming approach achieves feasible solution efficiently for the sports scheduling problem.

1. 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.
2. Easton, Kelly,Nemhauser, George,Trick, Michael(2002).Solving the Traveling Tournament Problem: A Combined Integer Programming and Constraint Programming Approach.Practice and theory of automated timetabling IV
3. Miyashiro, R.,Matsui, T.(2004).A polynomial -time algorithm to find an equitable home-away assignment.Operations Research Letters,33(3),235-241.
4. Musaraganyi, C.(1998).Book Review: OPTIMIZATION AND COMPUTATION LOGIC, McAloon, K. and Tretkoff C., New York: Wiley-Interscience, 1996.Journal of Multi-Criteria Decision Analysis,7(3),178.
5. Nemhauser, G. L.,Trick, M. A.(1998).Scheduling a Major College Basketball Conference.Operations Research,46(1),1-8.
6. Rasmussen, RV,Trick, M.A.(2007).A Benders approach for the constrained minimum break problem.European Journal of Operational Research,177(1),198-213.
7. Russell, R.A,Urban, T.L.(2004).A constraint programming approach to the multiple-venue, sport-scheduling problem.Computers & Operations Research,33(7),1895-1906.
8. Su, L.H.,Chiu, Y.,Cheng, T.C.E.(2013).Sports tournament scheduling to determine the required number of venues subject to the minimum time slots under given formats.Computers & Industrial Engineering,65,226-232.