Scheduling a triple round robin tournament with minitournaments for the Finnish national youth ice hockey league

This paper presents a method to schedule a triple round robin tournament, which involves minitournaments, each hosted by one team. A key issue is that at the end of the season the number of home games should be balanced over the teams, despite the fact that in minitournament matches only the host team plays at home. This format is played in the Finnish national ice hockey league for players under the age of 20 years, where the problem is further complicated by many other constraints, for example, preassigned matches resulting from away tours that should limit the distances travelled by the teams. To obtain a schedule for this league, we sequentially solve four distinct combinatorial problems. This method allows us to construct a schedule for the 2009–2010 season, which is superior to the official schedule: it has no hard constraint violations, and outperforms the official schedule on three of five soft constraints.     

Maximizing breaks and bounding solutions to the mirrored traveling tournament problem

We investigate the relation between two aspects of round robin tournament scheduling problems: breaks and distances. The distance minimization problem and the breaks maximization problem are equivalent when the distance between every pair of teams is equal to 1. We show how to construct schedules with a maximum number of breaks for some tournament types. The connection between breaks maximization and distance minimization is used to derive lower bounds to the mirrored traveling tournament problem and to prove the optimality of solutions found by a heuristic for the latter.     

A branching scheme for minimum cost tournaments with regard to real-world constraints

Single round robin tournaments are a well-known class of sports leagues schedules. We consider leagues with a set T of n teams where n is even. Costs are associated with each possible match. Moreover, stadium availability, fixed matches, and regions’ capacities are taken into account. The goal is to find the minimum cost tournament among those having the minimum number of breaks and being feasible with regard to these additional constraints. A branching scheme is developed where branching is done by fixing a break for a team. Thus, the focus is on identifying breaks leading to an infeasible home away pattern set in order to avoid the resulting infeasible subtrees of a branch and bound tree.     

Scheduling a triple round robin tournament for the best Danish soccer league

In this paper, we present a solution method for the highly constrained problem of finding a seasonal schedule for the best Danish soccer league. The league differs from most sports leagues, since it plays a triple round robin tournament which leads to an uneven distribution of home and away games. The solution method presented here uses a logic-based Benders decomposition in which the master problem finds home-away pattern sets while the subproblem finds timetables. Furthermore, column generation techniques are used to enhance the speed of the master problem. The computational results show that the solution method is capable of solving the problem within reasonable time and the Danish Football Association has used it for scheduling the 2006/2007 season.     

A branch-and-price algorithm for scheduling sport leagues

A single round robin tournament can be described as a league of a set T of n teams (n even) to be scheduled such that each team plays exactly once against each other team and such that each team plays exactly once per period resulting in a set P of n?1 periods. Matches are carried out at one of the stadiums of both opponents. A team playing twice at home or twice away in two consecutive periods is said to have a break in the latter of both periods. There is a vast field of requests arising in real-world problems. For example, the number of breaks is to be minimized due to fairness reasons. It is well known that at least n?2 breaks must occur. We focus on schedules having the minimum number of breaks. Costs corresponding to each possible match are given and the objective is to minimize the sum of cost of arranged matches. Then, sports league scheduling can be seen as a hard combinatorial optimization problem. We develop a branch-and-price approach in order to find optimal solutions.     

A branching scheme for finding cost-minimal round robin tournaments

Single round robin tournaments are a well known class of sports leagues schedules. We consider leagues with a set T of n teams where n is even. Costs are associated to each possible match. The goal is to find the minimum cost tournament among those having the minimum number of breaks. We pick up structural properties of home–away-pattern sets having the minimum number of breaks. A branching idea using these properties is developed in order to guide branching steps on the first levels of a branch-and-bound tree in order to avoid nodes corresponding to infeasible subproblems.     

Scheduling sports tournaments on a single court minimizing waiting times

We consider a sports tournament for an odd number of teams where every team plays exactly two matches in each round and all matches have to be scheduled consecutively on a single court. We construct schedules for any number of teams minimizing waiting times.     

Construction of Hamilton Path Tournament Designs

A Hamilton path tournament design involving n teams and n/2 stadiums, is a round robin schedule on n − 1 days in which each team plays in each stadium at most twice, and the set of games played in each stadium induce a Hamilton path on n teams. Previously, Hamilton path tournament designs were shown to exist for all even n not divisible by 4, 6, or 10. Here, we give an inductive procedure for the construction of Hamilton path tournament designs for n = 2 ^p ≥ 8 teams.     

Efficacy of traditional sport tournament structures

The ranking abilities of some traditional sport tournaments under a variety of initial conditions were analyzed using Monte Carlo procedures. A range of outcome measures were used since a tournament’s efficacy will likely depend upon both its objectives and the playing abilities of its contestants. The traditional knockout (KO) is a weak tournament in its ability to rank all players although it requires fewer games than the round robin (RR). The KO tournament’s efficacy is notably enhanced, however, in some cases beyond that of the RR tournament if double elimination procedures are used and the seeding is reasonably accurate. Under these conditions, we consider the KO structure to be the best available structure for most tournament purposes. A secondary recommendation of this study is that the fourth and fifth placings be reversed in the traditional KO structures for ranking all players in the eight player situation.     

Scheduling a non-professional indoor football league: a tabu search based approach

This paper deals with a real-life scheduling problem of a non-professional indoor football league. The goal is to develop a schedule for a time-relaxed, double round-robin tournament which avoids close successions of games involving the same team in a limited period of time. This scheduling problem is interesting, because games are not planned in rounds. Instead, each team provides time slots in which they can play a home game, and time slots in which they cannot play at all. We present an integer programming formulation and a heuristic based on tabu search. The core component of this algorithm consists of solving a transportation problem, which schedules (or reschedules) all home games of a team. Our heuristic generates schedules with a quality comparable to those found with IP solvers, however with considerably less computational effort. These schedules were approved by the league organizers, and used in practice for the seasons 2009–2010 till 2016–2017.

     

A multi-round generalization of the traveling tournament problem and its application to Japanese baseball

In a double round-robin tournament involving n teams, every team plays 2(n − 1) games, with one home game and one away game against each of the other n − 1 teams. Given a symmetric n by n matrix representing the distances between each pair of home cities, the traveling tournament problem (TTP) seeks to construct an optimal schedule that minimizes the sum total of distances traveled by the n teams as they move from city to city, subject to several natural constraints to ensure balance and fairness. In the TTP, the number of rounds is set at r = 2. In this paper, we generalize the TTP to multiple rounds (r = 2k, for any k ? 1) and present an algorithm that converts the problem to finding the shortest path in a directed graph, enabling us to apply Dijkstra’s Algorithm to generate the optimal multi-round schedule. We apply our shortest-path algorithm to optimize the league schedules for Nippon Professional Baseball (NPB) in Japan, where two leagues of n = 6 teams play 40 sets of three intra-league games over r = 8 rounds. Our optimal schedules for the Pacific and Central Leagues achieve a 25% reduction in total traveling distance compared to the 2010 NPB schedule, implying the potential for considerable savings in terms of time, money, and greenhouse gas emissions.     

Feasibility of home-away-pattern sets for round robin tournaments

A Home-Away-Pattern (HAP) set defines each team’s venue in each period. We consider the decision problem of whether a round robin tournament can be arranged on the basis of a given HAP set. We give a necessary condition which can be checked in polynomial time and conjecture it to be sufficient.     

Approximation algorithms for TTP(2)

We consider the traveling tournament problem, which is a well-known benchmark problem in tournament timetabling. It consists of designing a schedule for a sports league of n teams such that the total traveling costs of the teams are minimized. The most important variant of the traveling tournament problem imposes restrictions on the number of consecutive home games or away games a team may have. We consider the case where at most two consecutive home games or away games are allowed. We show that the well-known independent lower bound for this case cannot be reached and present two approximation algorithms for the problem. The first algorithm has an approximation ratio of ${3/2+\frac{6}{n-4}}$ in the case that n/2 is odd, and of ${3/2+\frac{5}{n-1}}$ in the case that n/2 is even. Furthermore, we show that this algorithm is applicable to real world problems as it yields close to optimal tournaments for many standard benchmark instances. The second algorithm we propose is only suitable for the case that n/2 is even and n????12, and achieves an approximation ratio of 1?+?16/n in this case, which makes it the first ${1+\mathcal{O}(1/n)}$ -approximation for the problem.     

Constructing fair sports league schedules with regard to strength groups

A single round robin tournament (SRRT) consists of n teams and a set of periods. Matches between the teams have to be scheduled such that each team plays against each other team exactly once and each team plays at most once per period. In order to establish fairness among teams, we consider a partition of the teams into strength groups. Then, the goal is to avoid matches where a team plays against extremely weak or extremely strong teams in consecutive periods. In this paper, we pick up two concepts ensuring different degrees of fairness and address several questions which remained open so far.     

Round robin tournaments and three index assignments

Scheduling a sports league can be seen as a difficult combinatorial optimization problem. We study some variants of round robin tournaments and analyze the relationship with the planar three-index assignment problem. The complexity of scheduling a minimum cost round robin tournament is established by a reduction from the planar three-index assignment problem. Furthermore, we introduce integer programming models. We pick up a popular idea and decompose the overall problem in order to obtain two subproblems which can be solved sequentially. We show that the latter subproblem can be casted as a planar three-index assignment problem. This makes existing solution techniques for the planar three-index assignment problem amenable to sports league scheduling.     

Scheduling the Australian Football League

Generating a schedule for a professional sports league is an extremely demanding task. Good schedules have many benefits for the league, such as higher attendance and TV viewership, lower costs and increased fairness. The Australian Football League is particularly interesting because of an unusual competition format integrating a single round-robin tournament with additional games. Furthermore, several teams have multiple home venues and some venues are shared by multiple teams. This paper presents a 3-phase process to schedule the Australian Football League. The resulting solution outperforms the official schedule with respect to minimizing and balancing travel distance and breaks, while satisfying more requirements.     

Team assignments and scheduling for the NCAA basketball tournament

The National Collegiate Athletic Association (NCAA) organizes a men's basketball tournament every March to determine the national champion for the current season. In organizing the tournament, the emphasis is typically on selection of the most deserving teams to participate and providing a fair, equitable environment in which to play that result in a true, undisputed champion for the season. However, there are growing concerns of dwindling actual attendance at tournament games and increasing financial burden on the NCAA related to reimbursable team travel expenses. In this paper, we describe the development of an integer program designed to optimize team assignments in the sense of minimizing the distance travelled by teams to game sites and the corresponding travel costs. The goal is to increase tournament accessibility to fans as well as lessen the financial impact to the NCAA while maintaining the integrity of the tournament. We test our model against actual tournament assignments from the past 5 years. Results show consistent and significant cost savings and reductions in distance travelled without compromising the fairness and structure of the tournament. Overall, we demonstrate the usefulness of the model in both operational and strategic business decisions.     

Solving mirrored traveling tournament problem benchmark instances with eight teams

A two-phase method based on generating timetables from one-factorizations and finding optimal home/away assignments solved the mirrored traveling tournament problem benchmark instances NL8 and CIRC8 at the Challenge Traveling Tournament Problems homepage http://mat.gsia.cmu.edu/TOURN/.     

Scheduling non-professional table-tennis leagues

In this paper we consider a sports league scheduling problem which occurs in planning non-professional table-tennis leagues. The problem consists in finding a schedule for a time-relaxed double round robin tournament where different hard and soft constraints have to be taken into account. We model the problem as an integer linear program and a multi-mode resource-constrained project scheduling problem, respectively. Based on the second model a heuristic solution algorithm is proposed, which proceeds in two stages using local search and genetic algorithms. Computational results show the efficiency of the approaches.     

On the existence of sports schedules with multiple venues

We give theoretical methods of creating sports schedules where there are multiple venues for the games, and the number of times each team uses each venue should be balanced. A construction for leagues having 2^p?8 teams was given by de Werra, Ekim and Raess. Here we show that feasible schedules exist when the league has an arbitrary even number of teams greater than or equal to 8.