How to schedule the Volleyball Nations League

Prologue

It is the beginning of June 2018 when the Italian men volleyball team go undefeated in the first round of the inaugural Volleyball Nations League. They played their three first-round matches in Kraljevo, Serbia, and for the next round of three matches they have to travel, via Belgrade, Rome, Buenos Aires, to reach the next venue in San Juan, Argentina, after more than 24 hours of traveling. Playing only a few days after this trip, their momentum seems lost and they lose two out of their three games, all played within a week, upon which they immediately need to fly to Japan for the third round.

Ultimately, the Italian team had to travel literally across the globe within a time span of four weeks, playing matches against the best volleyball teams in the world. Even though they started off with three victories, they ended eighth and did not qualify for the final stages. In comparison, the French team played all their matches within Europe and emerged as winner of the main event. Later that year however, during the World Championship, the Italian team outperformed the French team.

1Introduction

The above example is just one of many that highlights how travel times, and specifically disparity in travel times, influence results in the Volleyball Nations League (VNL). It is well established within the scientific literature that extensive travelling has a negative impact on sport performance. Although we do not intend to survey the literature on this subject, this finding is reported for various sports ranging from rugby (Lo et al. (2020)) to baseball (Song et al. (2017), and Winter et al. (2009)) and from basketball (Huyghe et al. (2018)) to triathletes (Stevens et al. (2018)); see also the references contained in these papers. We close this paragraph by two quotes: one from an interview with Anne Buijs, professional volleyball player(see Volkskrant (2021)): “It is quite an advantage to play all VNL matches at the same location. In the original schedule we would have travelled from Serbia to Canada to Korea, which makes the schedule very hard for us.”, and one from Samuels (2012) who concludes: “Jet lag and travel fatigue are considered by high-performance athletic support teams to be a substantial source of disturbance to athletes.” This phenomenon is illustrated in the prologue of this paper, and serves as its motivation.

The Volleyball Nations League is a tournament organized every year by the FIVB (Fédération Internationale de Volleyball), for both men and women (see https://www.volleyball.world/en/vnl/2021). This tournament was first organized in 2018 to replace the World League/World Grand Prix as annual volleyball tournament. There are 16 teams participating in the tournament which consists of multiple phases. In the first phase, lasting for five weeks, all 16 teams play a single round robin, i.e., each team meets each other team once. The best 6 teams then qualify for the second phase, where out of two groups of three, four teams emerge to play cross finals. Our interest is exclusively on the first phase.

In the first phase of the VNL tournament, teams play in rounds. In each round, each team is in a group consisting of 4 teams, and each team in a group plays a match against its three fellow group members. After 5 rounds, each of the 16 teams has played all the other teams exactly once, and a ranking is made based on the results in this single round robin tournament. All 6 matches in a single group are held at the same venue, however, every round has its 4 groups played out in different venues. As it is a disadvantage to have traveled more than your opponent going into a match, our main interest lies in minimizing a measure that captures the imbalance in travel times between opposing teams.

A priori, it is not clear how a round robin schedule that can be decomposed in groups is obtained. In fact, finding a schedule that fits this VNL-format is related to the so-called Social Golfer Problem (SGP). In this problem we are given gp golfers and w rounds (where g, p, w are positive integers), and the SGP-question is whether it is possible to let the gp golfers play in g groups of p golfers in each of the w rounds, in such a way that every pair of golfers plays in the same group in at most one round, see Triska & Musliu (2012), Liu et al. (2019), Dotú & van Hentenryck (2005). This question is far from innocent: only for restricted sets of values for g, p, w the answer to this question is known. For instance, when g = p = w - 1, solutions are known to exist when g is a prime power - and no other solution to these type of instances has been found, nor has it been proven that these are the only instances for which a solution can exist (Harvey & Winterer (2005)).

Of course, in the context of the Volleyball Nations League, each golfer corresponds to a team (and groups remain groups and rounds remain rounds). Since the Volleyball Nations League has g = p = 4 and w = 5, it follows that the answer to the SGP-question is affirmative, and hence a schedule for the VNL that consists of 5 rounds, each round consisting of 4 groups, is known to exist. In this paper, we introduce the Traveling Social Golfer Problem (TSGP), as a generalization of the SGP; the TSGP allows us to take fairness, as measured by the difference in travel times between opposing teams, into account. Recent other variations of the SGP are discussed in Miller et al. (2021) and Lester (2021).

A well-known problem related to the TSGP that also focusses on distances is the Travelling Tournament Problem (TTP), see Easton et al. (2003) for a precise description. In contrast to our problem, in the TTP pairs of teams meet in the venue of one of the two opposing teams. Moreover, the objective in the TTP is to minimize total travel distance; difference in travel time between opposing teams is not considered in the TTP. We refer to Goerigk & Westphal (2016) and Durán et al. (2019) for an overview concerning the TTP.

A number of studies has been devoted to the scheduling of national volleyball leagues where mainly for cost reasons, the objective is to minimize total travel time. We mention Bonomo et al. (2012) who model the Argentine national volleyball league as an instance of the Traveling Tournament Problem, and Cocchi et al. (2018) who investigate the Italian volleyball league. Further, Raknes & Pettersen (2018) study the Norwegian Volleyball League; one of their models, motivated by a cost-objective, is devoted to minimizing total travel distance in that league. These leagues are organized in the format of a Double Round Robin, and as such differ from the VNL.

2The Traveling Social Golfer Problem (TSGP)

3The complexity of Venue Assignment

In this section, we formally establish the complexity of Venue Assignment. Given that feasible schedules to the (N = k², k)-TSGP exist, Theorem 2.1 implies that our task of finding an optimal solution to (N, k)-TSGP is reduced to finding an optimal venue assignment. Clearly, this is related to the differences in traveled distance between two opposing teams, which in turn follows from the venues that are selected in each round.

In an extreme case, if only a single venue v is given (with multiplicity c_v = k (k + 1)), then all matches in all groups in all rounds are played in the same venue, and there is no travel distance. However, in general, the set of venues V and their pairwise distances, are instrumental in finding good venue assignments. Of course, we assume that ∑_v∈Vc_v = k (k + 1). We now give a formal description.

Problem 3.1. Venue Assignment (VA)

Input. A value k∈ℕ , a set of venues V, an integral multiplicity c_v for v ∈ V, and a distance matrix d (v, w) for each v, w ∈ V.

Output. For r ∈ {1, …, k + 1}, subsets U_r ⊂ V with |U_r| = k, such that ∀v ∈ V, c_v = | {r : v ∈ U_r} | that minimizes:

To establish the hardness of Venue Assignment, we use the following decision problem.

Problem 3.2. Longest Hamiltonian Path on a Complete Graph (LHP)

Input. A complete graph G = (H, E), |H| = n with nonnegative, symmetric weights w (h₁, h₂) for each h₁, h₂ ∈ H, and an integer B.

Question. Does there exist a Hamiltonian Path (h_i1, …, h_in) in G such that ∑j=1n-1w(hij,hij+1)≥B ?

LHP is well-known to be NP-complete.

Theorem 3.1. Venue-Assignment is NP-Hard.

Proof. We prove this statement by a reduction from Longest Hamiltonian Path on a Complete Graph.

Given an instance of LHP, with vertex set H = {h₁, …, h_n} and weights w:H×H→ℝ , we construct an instance of the decision problem corresponding to VA, using a parameter K, in the following way.

We choose k : = n - 1. Further, the set of venues V consists of V = V₁ ∪ V₂, where V₁ : = H and |V₂| : = n - 2. For each v ∈ V₁, c_v : =1 and for each v ∈ V₂, c_v : = n. Let D=maxh1,h2∈Hw(h1,h2) and define a symmetric distance function d in the following way:

Notice that the resulting distances satisfy the triangle inequality when the instance of LHP does. Finally, we set K : = k² · 2D - B, and ask whether there exists a venue assignment with unfairness at most K. We have now specified an instance of the decision version of VA.

Let us argue that if there exists a solution to VA with unfairness at most K, LHP is a yes-instance, and vice versa.

To find a solution to any instance of VA, we need to find U_r ⊂ V for each r ∈ {1, …, k + 1} such that ∀v ∈ V, c_v = | {r : v ∈ U_r} |. As we know that for all v ∈ V₂, c_v = k + 1, we see that any feasible solution must have V₂ ⊂ U_r for each round r. Moreover, as c_v = 1 for v ∈ V₁, we get that any feasible solution must schedule every venue v ∈ V₁ exactly once. Thus, any feasible solution to VA consists of U_r = V₂ ∪ v_ir with v_ir ∈ V₁ and vir=vir′⇔r=r′ . In other words, any feasible solution to VA corresponds to an ordering (v_i1, …, v_ik+1) of the venues in V₁. Given such an ordering, we obtain the following expression for the unfairness of a schedule S that uses the ordering (v_i1, …, v_ik+1):

Let us now suppose that the instance of LHP is a yes-instance, implying the existence of a Hamiltonian Path such that ∑j=1n-1d(hij,hij+1)≥B . We choose as the ordering of venues in V₁ the sequence of nodes in this Hamiltonian path. We find:

Finally, suppose there exists a schedule S whose unfairness is bounded by K, we obtain:

Thus, solving this instance of the decision version of VA is equivalent to solving the corresponding instance of LHP, which implies that VA is NP-Hard. □

4The VNL in practice: about the home-venue-property

Motivated by the current practice in the VNL, we incorporate the following issue in our problem formulation: each venue has a team that considers this venue as its home-venue. Next, in any feasible schedule for the VNL it must be the case that when a venue is hosting a group, the group must contain the team for which this venue is the home-venue. And in case there are multiple venues that are the home-venue of the same team, it is a fact that those venues are never a host of a group in the same round. Thus, each venue is a home venue to a single team; however, a team can have multiple home venues. In the context of the VNL, this property specifies that each venue always hosts a group that contains the national team; this team can be regarded as the home playing team, or host nation. As an aside, it is interesting to note here that Alexandros et al. (2012) find the presence of (a significant) home advantage in volleyball matches played in Italian and Greek national leagues.

We will refer to solutions having the property that the venue hosting a group is the home-venue for some member of the group, as the home-venue property. A relevant question now becomes:

Do feasible schedules satisfying the home-venue property exist?

In fact, solving the Venue Assignment problem does not automatically lead to a schedule that satisfies the home-venue property. In other words, it is not true that, when given an assignment of venues to rounds, a schedule is guaranteed to exist such that every venue is a home venue. Then, in such a case, a venue hosts a group of teams, none of which plays home. Example 4.1 shows how a feasible solution of the Venue-Assignment problem cannot be extended to a solution having the home-venue property.

Example 4.1. Let N = 4 be the number of teams with group size k = 2, and let V be the set of home venues. All countries t have a venue v_t ∈ V, where for countries t = 1, 2, their venue has a multiplicity of 2 and the other venues have a multiplicity of 1, i.e., c_v1 = c_v2 = 2 and c_v3 = c_v4 = 1. Solving the corresponding instance of Venue-Assignment can result in a solution as is given in Table 2.

The venue assignment in Table 2 clearly satisfies the given multiplicities. However, it is impossible to schedule match (t₁, t₂) in any round when restricting teams to play at their home venue whenever it is scheduled in a round. Moreover, venue assignments satisfying the given multiplicities yielding a feasible schedule do exist for the given example.

Thus, we see that solving the Venue-Assignment alone is not necessarily the same as solving the VNL-problem in practice.

However, and perhaps surprisingly, the following theorem shows that for the particular dimensions of the VNL (N = 16, k = 4), a Venue-Assignment can always be extended to a solution for the Volleyball Nations League.

Theorem 4.1. Let N = 16 be the number of teams and k = 4 the group size. Let V be the set of venues, with corresponding multiplicities c_v (v ∈ V) such that each team has at least one home venue, and all venues need to be scheduled at least once (never with two venues of the same team hosting simultaneously), i.e., c_v ≥ 1 for each v ∈ V, and ∑_v∈Vc_v = 20. Then any solution of the corresponding Venue-Assignment instance, can be extended to a feasible solution of the VNL-instance satisfying the home-venue property.

Proof. We organize the proof as follows. First, we specify the groups (called our ‘blueprint’). Second, we provide a partial designation of home venues. Then we consider the possibilities that exist for the vector c_v, and for each of these possibilities, we consider the set of distributions over the rounds. Finally, we outline how, for each of these distributions, we can arrive at a solution that satisfies the home-venue property.

Consider Table 3, where column “R_i” stands for Round i, i = 1, …, 5, and where each number from {1, …, 16} stands for a team. We refer to this composition of groups as a ‘blueprint’, and we will argue that, for any possible set of multiplicities, and for any distribution of these multiplicities over the rounds, this blueprint can be turned into a venue assignment satisfying the home-venue property, and hence into a nation assignment.

Of course, Table 3 does not constitute a feasible solution, as it has not been specified for each group which team plays at its home-venue. This clearly depends on the multiplicities; in Table 4, we provide a partial specification of the teams that play at their home-venue.

In fact, Table 4 provides an initial assignment such that each team is the host in exactly 1 group, i.e., each of the numbers 1, …, 16 occurs once.

We will now identify all possibilities for c_v, the vector of multiplicities. Without loss of generality, we can assume that the entries in this vector are non-increasing. As stipulated in Theorem 4.1, we have c_v ≥ 1 for each v ∈ V, and ∑_v∈Vc_v = 20, which implies that there exist 5 distinct possibilities for the first four entries of c_v, namely:

It is important to realize that, for each of these possibilities, the distribution of the multiplicities over the rounds may differ, and that each of these distributions should be considered separately. As an example, consider the case where (c₁, c₂, c₃, c₄) = (3, 3, 1, 1). One possible solution of the Venue Assignment problem is that there are three rounds where the venues of both team 1 and team 2 are host. Another possible solution of the Venue Assignment problem is that in rounds 1, 2, 3, the venue of team 1 is host, whereas in rounds 3, 4, 5 the venue of team 2 is host. We refer to each such solution as a distribution. We call two distributions distinct when no permutation of the rounds maps one distribution to the other.

Given a particular choice for (c₁, c₂, c₃, c₄), it is not immediately clear how many pairwise distinct distributions exist. Let D (c₁, c₂, c₃, c₄) denote the set of pairwise distinct distributions compatible with (c₁, c₂, c₃, c₄). By a case analysis, we claim that |D (5, 1, 1, 1) |=1, |D (4, 2, 1, 1) |=2, |D (3, 3, 1, 1) |=3, |D (3, 2, 2, 1) |=11, and |D (2, 2, 2, 2) |=17. In fact, Table 5 displays the sets D (c₁, c₂, c₃, c₄).

We now describe how Table 5 can be read such that it provides a feasible solution satisfying the home-venue property for each distribution. To do so, we use the labels A, B, C, D for those teams whose home venues have a multiplicity higher than 1.

Each entry of Table 5 should be interpreted in the following way:

In this way, Table 5 gives, for every possible venue assignment, a schedule that satisfies the home-venue property, thereby completing the proof. □

Thus, Table 5 can be read as an instruction of how to find a feasible schedule satisfying the home-venue property for any solution of the Venue Assignment problem.

As an example, consider the distribution (ABC, AB, AC, - , -) which is an element of D (3, 2, 2, 1). The corresponding entries in the third column of Table 5 imply that in R₁, teams 1, 7 and 8 act as host. Next the fourth column corresponding to this distribution, contains “R₁ : 6”, implying that team 6 also acts as host in R₁. Continuing in this way, it follows that teams 1, 12, 10, and 7 act as hosts in R₂, teams 1, 16, 9, and 8 act as hosts in R₃, teams 3, 11, 5, and 15 act as hosts in R₄, and teams 2, 4, 13, and 14 act as hosts in R₅. It is interesting to observe that in each of the schedules needed in the proof of Theorem 4.1, the composition of the groups as specified in the blueprint from Table 3 is identical.

Lastly, we like to point out that a nation might have multiple venues where it can/must host. In the proof of the previous theorem, we assumed every nation to have one venue with a specific multiplicity. When there are multiple venues, when calculating the travel distance it matters which one is used to host a group. To address this, we solve the Venue Assignment on the complete set of all venues, with the restriction that venues from the same nation cannot host in the same round. For the Nation Assignment however, it does not matter which venues are used specifically - in this stage, we only assign nations to groups, in such a way that a host nation will be scheduled to play in its own venue(s). Hence, when solving the Nation Assignment using the blueprint, we may assume that every nation has exactly one venue.

5Solving real-life instances of the VNL

In Section 5.1, we give an integer programming formulation of the Venue-Assignment Problem. Section 5.2 presents the outcomes.

5.1An Integer Programming Formulation

Let x_v,r be the binary variables that indicate whether venue v ∈ V hosts a group in round r ∈ {1, …, 5} = R. Further, we need real variables s_v,w,r (capturing distances between venues v and w acting as host in rounds r and r + 1), m_v,r (capturing the largest distance traveled to venue v in round r), and K_v,r (capturing the difference in travel distance to venue v in round r). Let Δ=maxv,wd(v,w) , and let W ⊂ V × V be the set of pairs of venues that cannot both host a group in the same round. The following IP minimizes u: the sum of the difference in travel distances per group, over the groups.

(12)

min∑v∈V∑r∈RKv,r

(13)

s.t.∑v∈Vxv,r=k∀r∈R,

(14)

∑r∈Rxv,r=cv∀v∈V,

(15)

xv,r+xw,r≤1∀r∈R, ∀(v,w)∈W,

(16)

sv,w,r≥dv,w(xv,r+xw,r-1-1)∀v,w∈V, ∀r∈R\1,

(17)

sv,w,r≤min(dv,wxv,r,dv,wxw,r-1)∀v,w∈V, ∀r∈R\1,

(18)

mv,r≥sv,w,r∀v,w∈V, ∀r∈R\1,

(19)

Kv,r≥mv,r-sv,w,r-D(1-xw,r-1)∀v,w∈V, ∀r∈R\1,

(20)

xv,r∈{0,1},Kv,r≥0∀v∈V,r∈R.

First, observe that (12) captures the objective function, minimizing u = ∑_v,rK_v,r. Next, constraints (13) ensure that in every round, k venues are host; constraints (14) ensure that every venue hosts as often as required; constraints (15) ensure that two venues that should not host simultaneously, will not host simultaneously. Auxiliary variables s_v,w,r are at least as large as d_v,w, the distance traveled between venues w, v in rounds r - 1 and r if these venues host in the respective rounds, by constraints (16), but never larger than d_v,w by constraints (17). The variables m_v,r equal the maximum distances traveled to venue v in round r (can equal zero 0 if v does not host in round r), as defined by (18), and K_v,r resembles the difference in traveled distances towards v in round r compared to the maximum travel distance, where the terms -D · (1 - x_w,r-1) in (19) nullify any influence caused by distances between a venue that does not host in round r - 1.

Fig. 1

Optimal venues per round, VNL Men 2018.

6Conclusion

We have introduced the Travelling Social Golfer Problem (TSGP), generalizing the well-known Social Golfer Problem, to model the scheduling of the Volleyball Nations League. The TSGP allows us to model the unfairness of a schedule that focusses on minimizing the differences in travel time between opposing teams. We show that this problem can be decomposed into two subproblems, Venue Assignment and Nation Assignment, and we argue that solving the Venue Assignment determines the amount of unfairness. We describe the home-venue property that is present in real-life solutions, and we show that, for the specific dimensions of the VNL, such solutions always exist. Finally, we model the problem as an integer program, and solve the real-life instances of 2018 and 2019. The results show that large improvements in fairness are possible, without increasing total travel time.