A metaheuristic algorithm for the carry-over effect value minimization problem in round-robin tournaments

Abstract

Round­robin tournaments are widely used in sports leagues such as football and baseball leagues. The round­robin tournament scheduling problem is one of the most well­known problems in sports scheduling. When creating a schedule for a round­robin tournament, various factors are considered such as travel distance of teams and the number of breaks. Among such factors, the carry­over effect is often considered to evaluate a schedule from the viewpoint of fairness. In this paper, we propose a metaheuristic algorithm for the problem of minimizing the carry-over effect value. For a complete graph whose edges describe all possible matches in a round­robin tournament, we consider a rainbow perfect matching, which we call a base matching, to describe a round of a schedule. By using the circle method, a round­robin tournament schedule can be generated from any base matching. Then we design a metaheuristic algorithm based on iterated local search to search for a “good” base matching, that is, one that generates a round­robin tournament schedule with a low carry­over effect value. We confirmed through computational experiments that our proposed algorithm obtained solutions with carry­over effect values equal to or lower than the best­known values for 15 out of the 17 tested instances with up to 40 teams. In addition, we updated the best­known records for 2 instances.

Keywords

• sports scheduling
• round­robin tournament
• carry­over effect
• rainbow perfect matching
• circle method
• metaheuristic
• iterated local search