Invited Review
Round robin scheduling – a survey

https://doi.org/10.1016/j.ejor.2007.05.046Get rights and content

Abstract

This paper presents a comprehensive survey on the literature considering round robin tournaments. The terminology used within the area has been modified over time and today it is highly inconsistent. By presenting a coherent explanation of the various notions we hope that this paper will help to obtain a unified terminology. Furthermore, we outline the contributions presented during the last 30 years. The papers are divided into two categories (papers focusing on break minimization and papers focusing on distance minimization) and within each category we discuss the development which has taken place. Finally, we conclude the paper by discussing directions for future research within the area.

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)

  • G. Post et al.

    Sports tournaments, home–away assignments, and the break minimization problem

    Discrete Optimization

    (2006)
  • R.V. Rasmussen et al.

    A Benders approach for constrained minimum break problem

    European Journal of Operational Research

    (2007)
  • C.C. Ribeiro et al.

    Heuristics for the mirrored traveling tournament problem

    European Journal of Operational Research

    (2007)
  • A. Rosa et al.

    Premature sets of 1-factors or how not to schedule round-robin tournaments

    Discrete Applied Mathematics

    (1982)
  • R.A. Russell et al.

    A constraint programming approach to the multiple-venue, sport-scheduling problem

    Computers & Operations Research

    (2006)
  • J.A.M. Schreuder

    Combinatorial aspects of construction of competition dutch professional football leagues

    Discrete Applied Mathematics

    (1992)
  • T.L. Urban et al.

    Scheduling sports competitions on multiple venues

    European Journal of Operational Research

    (2003)
  • S. Urrutia et al.

    Maximizing breaks and bounding solutions to the traveling tournament problem

    Discrete Applied Mathematics

    (2006)
  • T.V. Voorhis

    College basketball scheduling with travel swings

    Computers & Industrial Engineering

    (2005)
  • D. de Werra

    Geography, games and graphs

    Discrete Applied Mathematics

    (1980)
  • D. de Werra

    Scheduling in sports

  • D. de Werra

    Minimizing irregularities in sports schedules using graph theory

    Discrete Applied Mathematics

    (1982)
  • D. de Werra

    Some models of graphs for scheduling sports competitions

    Discrete Applied Mathematics

    (1988)
  • D. de Werra et al.

    A constrained sports scheduling problem

    Discrete Applied Mathematics

    (1990)
  • D. de Werra et al.

    Construction of sports schedules with multiple venues

    Discrete Applied Mathematics

    (2006)
  • M.B. Wright

    Scheduling fixtures for basketball New Zealand

    Computers & Operations Research

    (2006)
  • A. Anagnostopoulos et al.

    A simulated annealing approach to the traveling tournament problem

    Journal of Scheduling

    (2006)
  • B.C. Ball et al.

    Optimal scheduling for even-numbered team athletic conferences

    AIIE Transactions

    (1977)
  • F. Barahona et al.

    An application of combinatorial optimization to statistical physics and circuit layout design

    Operations Research

    (1988)
  • J.C. Bean et al.

    Reducing travelling costs and player fatigue in the national basketball association

    Interfaces

    (1980)
  • T. Benoist, F. Laburthe, B. Rottembourg, Lagrange relaxation and constraint programming collaborative schemes for...
  • Cited by (277)

    • Strategic manipulations in round-robin tournaments

      2023, Mathematical Social Sciences
    • Sailing league problems

      2024, Journal of Combinatorial Designs
    View all citing articles on Scopus
    View full text