Invited ReviewRound robin scheduling – a survey
Introduction
As long as there has been competitive sport, there has been a need for sports schedules. During the last 30 years, sports scheduling has turned into a research area of its own within the operations research and computer science communities. While it may seem trivial to schedule a tournament, and combinatorial mathematics has methods for scheduling simple tournaments, when additional requirements are added the problem becomes a very hard combinatorial optimization problem. In fact, for many types of problems, instances with more than 20 teams are considered large-scale and heuristic solution methods are often necessary in order to find good schedules.
The challenging problems and the practical applications provide a perfect area for developing and testing solution methods. In the literature we find methods ranging from pure combinatorial approaches to every aspect of discrete optimization, including integer programming (IP), constraint programming (CP), metaheuristic approaches, and various combinations thereof. The solution methods have evolved over time and today methods exist capable of finding optimal or near-optimal solutions for hard practical instances.
In addition to the theoretical gains from developing efficient solution methods capable of solving practical applications, sports scheduling has an economic aspect. Professional sports are big business and the revenue of a sports league may be affected by the quality of the schedule since a substantial part of the revenue often comes from TV networks. The TV networks buy the rights to broadcast the games but in return they want the most attractive games to be scheduled at certain dates.
In this paper we give a comprehensive survey of the sports scheduling literature concerned with scheduling round robin tournaments. The literature is partitioned into papers on break minimization and papers on distance minimization. For both parts we present the main contributions and outline the development which has taken place. In order to keep the paper within reasonable size we have restricted ourselves to papers on round robin tournament problems in which the definition of the home or away status is relevant. This means that the problem of finding balanced tournament designs is not considered but for readers interested in this subject we refer to [7], [8], [20], [21], [29], [30], [45], [52], [60].
The rest of the paper is organized as follows. In Section 2, we present the terminology used within sports scheduling and, in Section 3, the various constraint types are outlined. The literature on break minimization and distance minimization are discussed in Sections 4 1-Factorizations and minimizing breaks, 5 Minimizing travel distance, respectively. Finally, Section 6 gives some concluding remarks and points out directions for future research.
Section snippets
Terminology
In this section, we define the sports scheduling terminology. It is important to stress that the terminology is far from consistent in the literature and some commonly used phrases have multiple meanings. However, to avoid misunderstandings, we will use the definitions from this section throughout the paper although it may conflict with papers to which we refer.
A round robin tournament is a tournament where all teams meet all other teams a fixed number of times. Most sports leagues play a
Constraints
Practical sports scheduling applications are very often characterized by a large number of conflicting constraints arising from teams, TV networks, sports associations, fans and local communities. Consequently, a section discussing the various constraints applicable to a particular sports league has become a standard part of papers considering practical applications since each league has their own special requirements. In this section we will give a short outline of the most typical constraints
1-Factorizations and minimizing breaks
A rich line of research has been to exploit the close relationship between 1-factorizations of graphs with tournaments. When venues are added, this leads to oriented 1-factorizations.
When teams return home after each away game instead of travelling from one away game to the next, alternating patterns of home and away games are usually preferred. Such patterns consider the fans by avoiding long periods without home games and they ensure regular earnings from home games.
The need for alternating
Minimizing travel distance
The minimization of travel distance becomes relevant when teams travel from one away game to the next without returning home. In this setup huge savings can be obtained when long trips are applied and teams located close together are visited on the same trip.
The interest in minimizing travel distances arose from the increasing travel costs due to the oil crises in the 1970s. This led to a request for efficient solution methods capable of finding good solutions for practical applications and a
Conclusion
This paper gives an outline of the terminology used within sports scheduling, it presents an overview of the constraint types used in the literature and it discusses the individual papers on both break minimization and distance minimization. From this survey it becomes clear that huge developments have taken place within the area. The solution methods become better at solving practical applications and the bounds for the benchmark instances of the TTP are improved continuously. Nevertheless,
References (63)
- et al.
Scheduling the professional soccer leagues of Austria and Germany
Computers and Operations Research
(2006) - et al.
Scheduling sports competitions with a given distribution of times
Discrete Applied Mathematics
(1988/1989) - et al.
Sports league scheduling: Graph- and resource-based models
Omega
(2007) - et al.
Minimizing breaks by maximizing cuts
Operations Research Letters
(2003) - et al.
A linear-time algorithm to solve the sports league scheduling problem (prob026 of CSPLib)
Discrete Applied Mathematics
(2004) - et al.
Global constraints for round robin tournament scheduling
European Journal of Operational Research
(2004) - et al.
Balanced home–away assignments
Discrete Optimization
(2006) - et al.
A simulated annealing and hill-climbing algorithm for the traveling tournament problem
European Journal of Operational Research
(2006) - et al.
A polynomial-time algorithm to find an equitable home–away assignment
Operations Research Letters
(2005) - et al.
Semidefinite programming based approaches to the break minimization problem
Computers & Operations Research
(2006)
Sports tournaments, home–away assignments, and the break minimization problem
Discrete Optimization
A Benders approach for constrained minimum break problem
European Journal of Operational Research
Heuristics for the mirrored traveling tournament problem
European Journal of Operational Research
Premature sets of 1-factors or how not to schedule round-robin tournaments
Discrete Applied Mathematics
A constraint programming approach to the multiple-venue, sport-scheduling problem
Computers & Operations Research
Combinatorial aspects of construction of competition dutch professional football leagues
Discrete Applied Mathematics
Scheduling sports competitions on multiple venues
European Journal of Operational Research
Maximizing breaks and bounding solutions to the traveling tournament problem
Discrete Applied Mathematics
College basketball scheduling with travel swings
Computers & Industrial Engineering
Geography, games and graphs
Discrete Applied Mathematics
Scheduling in sports
Minimizing irregularities in sports schedules using graph theory
Discrete Applied Mathematics
Some models of graphs for scheduling sports competitions
Discrete Applied Mathematics
A constrained sports scheduling problem
Discrete Applied Mathematics
Construction of sports schedules with multiple venues
Discrete Applied Mathematics
Scheduling fixtures for basketball New Zealand
Computers & Operations Research
A simulated annealing approach to the traveling tournament problem
Journal of Scheduling
Optimal scheduling for even-numbered team athletic conferences
AIIE Transactions
An application of combinatorial optimization to statistical physics and circuit layout design
Operations Research
Reducing travelling costs and player fatigue in the national basketball association
Interfaces
Cited by (277)
Orthogonal schedules in single round robin tournaments
2023, Operations Research LettersMeasuring competitive balance in sports leagues that award bonus points, with an application to rugby union
2023, European Journal of Operational ResearchFewer teams, more games, larger attendance? Evidence from the structural change in basketball's EuroLeague
2023, European Journal of Operational ResearchStrategic manipulations in round-robin tournaments
2023, Mathematical Social SciencesTournament schedules and incentives in a double round-robin tournament with four teams
2024, International Transactions in Operational ResearchSailing league problems
2024, Journal of Combinatorial Designs