An integer programming formulation for scheduling double round-robin tournaments with coupled team pairs

Abstract

In common double round robin (2RR) tournaments, each team has one match per round and must meet each other team twice. Especially for larger numbers of participating teams, this requires nume rous rounds, resulting in long travel distances for the teams. One possibility to relax this problem is to assign more than two teams to the same venue and increase the number of matches played at each round of the tournament. In this work, we consider a 2RR tournament, where pairs of teams are determined before the season. Then, in each round, either two of these pairs meet at the venue of one of the related teams and each team plays the two matches against the teams of the other pair, or the teams of a pair play against each other. This format requires assigning the team pairs in parallel to the scheduling process. We derive a linear integer programming model to minimize the total travel distance of all teams, tackling both problems simultaneously, and incorporate restrictions regarding the distribution of the home-field advantages. Furthermore, we conduct an extensive computational study to examine its computational performance for instances of varying sizes.