This article was downloaded by: [129.173.243.153] On: 18 November 2021, At: 04:38 Publisher: Institute for Operations Research and the Management Sciences (INFORMS) INFORMS is located in Maryland, USA
INFORMS Journal on Applied Analytics
Publication details, including instructions for authors and subscription information:
http://pubsonline.informs.org
Copyright By PowCoder代写 加微信 powcoder
Scheduling the Italian National Volleyball Tournament
, , Nicolino, Veronica Piccialli, ,
To cite this article:
, , Nicolino, Veronica Piccialli, , (2018) Scheduling the Italian National Volleyball Tournament. INFORMS Journal on Applied Analytics 48(3):271-284. https:// doi.org/10.1287/inte.2017.0932
Full terms and conditions of use: https://pubsonline.informs.org/Publications/Librarians-Portal/PubsOnLine-Terms-and- Conditions
This article may be used only for the purposes of research, teaching, and/or private study. Commercial use or systematic downloading (by robots or other automatic processes) is prohibited without explicit Publisher approval, unless otherwise noted. For more information, contact
The Publisher does not warrant or guarantee the article’s accuracy, completeness, merchantability, fitness for a particular purpose, or non-infringement. Descriptions of, or references to, products or publications, or inclusion of an advertisement in this article, neither constitutes nor implies a guarantee, endorsement, or support of claims made of that product, publication, or service.
Copyright © 2018, INFORMS
Please scroll down for article—it is on subsequent pages
With 12,500 members from nearly 90 countries, INFORMS is the largest international association of operations research (O.R.) and analytics professionals and students. INFORMS provides unique networking and learning opportunities for individual professionals, and organizations of all types and sizes, to better understand and use O.R. and analytics tools and methods to transform strategic visions and achieve better outcomes.
For more information on INFORMS, its publications, membership, or meetings visit http://www.informs.org
INTERFACES Vol. 48, No. 3, May–June 2018, pp. 271–284 http://pubsonline.informs.org/journal/inte/ ISSN 0092-2102 (print), ISSN 1526-551X (online)
Scheduling the Italian National Volleyball Tournament
GuidoCocchi,a AlessandroGalligari,a FedericaPiccaNicolino,a VeronicaPiccialli,b FabioSchoen,a MarcoSciandronea a DINFO, Università degli Studi di Firenze, 50139 I, Italy; b DICII, Università di Vergata, 00173 Rome RM, Italy
Contact: http://orcid.org/0000-0002-2199-9023 (GC); http://orcid.org/0000-0002-8599-642X (AG); http://orcid.org/0000-0002-5192-3388 (FPN);
http://orcid.org/0000-0002-3357-9608(VP); http://orcid.org/0000-0003-1160-7572(FS); http://orcid.org/0000-0002-5234-3174(MS)
Received: July 28, 2016
Revised: January 23, 2017
Accepted: July 31, 2017
Published Online in Articles in Advance: April 10, 2018
https://doi.org/10.1287/inte.2017.0932 Copyright: © 2018 INFORMS
Abstract. In this paper, we present our approach to sports scheduling, a process that led the Italian Volleyball League to adopt our calendar for the 2016–2017 and subsequent seasons. Sports scheduling is a hard combinatorial optimization problem whose solution requires modeling many different aspects of sports, some of which are unique to each sport or nation. The capability of producing a high-quality schedule is important for both balancing undesirable matches among teams and ensuring adequate coverage by televi- sion and other media. Through strong interaction with the Italian Volleyball League, we modeled and solved the problem to optimality using standard mathematical program- ming solvers. We also tested our solution using previous seasons’ tournaments to prove the capability of our model.
History: This paper was refereed.
Keywords: sports scheduling • round-robin tournament • mixed-integer programming • volleyball
Introduction
Sports scheduling in professional sports is a cru- cial task that involves massive investments in players, millions of fans, and television contracts. It usually requires the definition of dates and venues of matches between teams attending a tournament, and represents an important application field of operations research methodologies, as the increasing number of papers on the topic prove; examples include those collected in special issues of Interfaces (2012a and 2012b). The underlying combinatorial optimization problems are usually difficult and challenging, and they have been solved by both exact and approximate approaches. The amount of literature on applications of operations research techniques to sports scheduling is extensive. Knust (2017) maintains a website classifying this lit- erature. Each sports league has its own specific pecu- liarities and the objectives of scheduling must take into account the characteristics of the country in which the tournament will be held, because these character- istics often influence the structure and the rules of the tournament. For example, in large countries, such as Russia or the United States, minimizing the total distance traveled may be one of the main objectives of the schedule. Sports scheduling is intrinsically a
multiobjective optimization problem whose formula- tion is based on the objectives and requirements de- fined by the stakeholders.
In this paper, we present the development and appli- cation of a mixed-integer linear programming (MILP) model to create a regular season schedule for the Italian Volleyball League, which usually comprises 12 or more teams. The teams that can take part in the Italian volley- ball championship are determined by the Italian Vol- leyball League (the league), based on sports achieve- ments and suitable criteria, such as stadium suitability and registration fees. Italy mandates standard require- ments that the tournament schedule must satisfy and others that the league must introduce or modify year by year; however, they always require schedules that are fair and balanced for all teams to maximize both the attractiveness of the tournament and the number of fans who watch on television or attend at an indoor stadium. Travel issues must be considered for slots played on dates close to those of the European com- petitions, which may involve lengthy travel times and in particular slots (e.g., games scheduled on Decem- ber 26). As a result, the schedule must satisfy several hard and soft constraints, which may differ from year to year.
For two decades prior to the 2016–2017 season, the Italian Volleyball League created its schedules using a decision support system to define the matches among teams, after it had built each team’s home- away patterns, according to a two-phase approach. The schedule was determined by trial-and-error tech- niques based on experience. Thus, the Italian Volley- ball League employed a combination of a computer- based system and manual operations. In this paper, we adopt an approach based on operations research methodologies, and we present a mixed-integer linear formulation for scheduling tournaments for the Ital- ian Volleyball League. The schedules were obtained as exact solutions of the MILP problem and were used in partnership with the Italian Volleyball League. More specifically, we tested the solutions we gener- ated using the mathematical programming approach on the 2013–2014, 2014–2015, and 2015–2016 seasons, for which other schedules had been used, and then suc- cessfully applied our solution to produce the official schedule of the 2016–2017 tournament.
We organized this paper as follows. The next sec- tion, Volleyball League Scheduling in Other Countries, pro- vides a brief review of the literature on the schedul- ing of volleyball tournaments. We summarize the main characteristics of the Italian volleyball tournament in Italian Volleyball Tournament Structure. In the Schedule Requirements section, we present the hard and soft con- straints that the schedule must satisfy. The resulting MILP model is defined in the appendix. The results of the practical experience we gained in obtaining the schedule of the new 2016–2017 tournament (used offi- cially by the Italian Volleyball League) are analyzed and discussed in the Computational Results on Current and Past Tournaments section.
Volleyball League Scheduling in
Other Countries
Sports scheduling has been widely considered in the literature for different sports and types of tournaments; Rasmussen and Trick (2008) and Ribeiro (2012) provide surveys, while Kendall et al. (2010) include a bibliog- raphy of scheduling problems in sports. Bonomo et al. (2012) and Meng et al. (2014) consider the scheduling
Cocchi et al.: Scheduling the Italian Volleyball Tournament Interfaces, 2018, vol. 48, no. 3, pp. 271–284, © 2018 INFORMS
of volleyball leagues. Meng et al. (2014) consider the problem of organizing a volleyball tournament, given the number of teams, game days, and courts. They use integer programming to select the number of teams that should be in each division and the number of time slots that are needed. They also consider the referee assignment problem, which they solve using a genetic algorithm, and test their approach on simulated data.
Bonomo et al. (2012) consider the – ball League and formulate its scheduling as a variant of the traveling tournament problem (TTP). The TTP problem consists of scheduling a double round-robin tournament, given a set of n teams and the travel dis- tances matrix, with 2(n − 1) time slots, such that no team plays less than L (typically L 1) or more than U (typically U 3) home (resp. away) matches in a row, no two teams play against each other in two consec- utive time slots, and the total travel distance is min- imized. In addition, no team returns home between consecutive away matches. It is NP-hard when L 1 and U3, or when L1 and U∞; however, its complexity is unknown in the other cases (Thielen and Westphal 2011, Bhattacharyya 2009). Because the teams in the ball League are scat- tered throughout the country and road trips are usu- ally made by bus, the main objective of the league’s scheduling process is to adequately manage travel dis- tances, which they do using different objective func- tions. To optimize distances, the league play is orga- nized based on the coupled format: teams are divided into geographically close couples and the matches are grouped into pairs of temporally close meetings (usu- ally held on Thursdays and Saturdays), which are also grouped into pairs, thus forming a weekend. Each weekend, half of the couples visit a couple from the other half, and each visiting-couple team plays each of the two home-couple teams that are hosting it. On two special weekends, called intra-couple weekends, the two teams in each couple play against each other.
Here, we list the problem constraints.
1. Toensurefairness,thetwotopteamscannotform a couple.
2. A team cannot play more than two consecutive home or two consecutive away weekends (not counting intra-couple weekends), and two couples cannot play each other twice on consecutive weekends; although this constraint is trivially satisfied in a mirrored sched- ule, the schedule may also not be mirrored.
Cocchi et al.: Scheduling the Italian Volleyball Tournament Interfaces, 2018, vol. 48, no. 3, pp. 271–284, © 2018 INFORMS
Disregarding the intra-couple weekend, this prob- lem is a special case of the TTP, with couples replacing teams and pairs of matches (i.e., weekends) replac- ing single matches. Under this arrangement, L 1 and U 2 (i.e., at most, two consecutive home and away weekends). Therefore, defining the schedule consists of both defining the couples and defining the sched- ule. Bonomo et al. (2012) propose a two-stage process: the first stage is coupling (i.e., matching in a complete graph with distances on the edges); the second stage is generating the schedule (i.e., a TTP with six teams). The coupling, which reduces the number of weekends, and the constraints on the home-away games imply that the distribution on the home and away weekends can be deduced in advance: there exists an optimal solution such that the set of tours for each couple consists of a specific number of two-weekend trips and, at most, one single-weekend trip (or exactly one if the number of couples to be visited is odd). Some constraints are added depending, for example, on the unavailability of a team’s stadium on prespecified weekends; for exam- ple, another local sports team has booked the stadium on those dates. In some cases, because of special events, the matches on a prespecified weekend must be played near a specific city.
Italian Volleyball Tournament Structure
In this paper, we consider a tournament played by n teams: each year, the Italian Volleyball League estab- lishes the number of teams (usually an even number) that can take part in the first (Serie A) and second (Serie A2) division; teams can be promoted to the first division because of their sports achievements, or they can be relegated to the second division if a specific requirement, such as financial stability or stadium suit- ability, is not satisfied. Hence, the number of teams can vary; therefore, the model we describe in this paper addresses the case in which the number of teams is even, but it can be easily extended to address an odd number of teams. The Italian Volleyball Championship is structured as a regular phase, which is a double round- robin (DRR) tournament, and a playoff phase. In a DRR tournament, each team plays exactly twice with each other team, once in each half. The second half of the DRR is a mirror of the first half, with home games and away games exchanged. In this paper, we address the regular phase, which is the most difficult to schedule.
The games must be associated with the n − 1 slots for each half. Every team has its venue in its hometown in which the team must play exactly one of the two matches played against each other team. When a team plays at its venue, it plays a home game; at any other venue, it plays an away game.
A home-away pattern is the sequence of home games and away games played by a team during the tourna- ment. Two consecutive home games or away games are defined as a break.
The tournament schedule must establish for each half the pair of teams that must face each other in each slot and the location at which the game will be played. Because the schedule is mirrored, scheduling the first half of the schedule and exchanging home and away games for the second half is sufficient.
The annual Italian Volleyball Championship in- volves n teams (usually 12, but 14 for the 2016–2017 season); therefore, the tournament is made up of 2 · (n−1)slots,n−1inthefirsthalfandn−1inthesec- ond half. These slots usually cover the period from the beginning of October to the end of March. The days on which the matches are played are set, year by year, after a phase in which the league coordinates with other sports’ competitions and with national and inter- national tournaments (e.g., the basketball first divi- sion, the Italian Tournament ( ), the Euro- pean Championship). The preferred day of the week on which to play matches is Sunday; however, because a team might have to share its venue (usually an indoor sport arena) with a team that plays a different sport and for which Sunday is also the preferred day, a game might be shifted to Saturday or sometimes to Wednes- day. If Wednesday is selected, it is called a midweek day; Sundays and Saturdays are called weekend days and are considered equivalent from this perspective. Among the n teams that enter the tournament, some are also involved in other national championships; therefore, they may have some privileges or may have additional requirements to meet.
Each year, a rank based on the placement during the previous season is generated, and the most qual- ified teams (usually from the first ranked to the sixth ranked) are called top teams; these teams usually receive major TV rights, marketing revenue, gate attendance and sponsorship revenue, and significant media cover- age. Table 1, which shows n 14 teams, is an example
Cocchi et al.: Scheduling the Italian Volleyball Tournament Interfaces, 2018, vol. 48, no. 3, pp. 271–284, © 2018 INFORMS
Table 1. All Teams Participating in the 2016–2017 Championship Including Team Name, Team Rank, and a Short Code, Which We Use Throughout the Paper
Index Team Code
1 AZIMUT MODENA
2 CUCINE LUBE CIVITANOVA
3 DIATEC TRENTINO
4 SIR SAFETY CONAD PERUGIA
5 CALZEDONIA VERONA
6 EXPRIVIA MOLFETTA
7 TOP VOLLEY LATINA LT
8 KIOENE PADOVA PD
9 GI GROUP MONZA MB
10 BUNGE RAVENNA RA
11 POWER VOLLEY MILANO MI
12 LPR PIACENZA PC
13 BIOSÌ INDEXA SORA SO
14 TONNO CALLIPO CAL. VIBO VALENTIA VV
TN PG
Super top team
from the 2016–2017 season. In some years, the set of top teams includes a more specific subset of teams, which we call super top teams; for example, the first six teams are ranked as top teams, but only the first four teams are considered super top teams. Each match between two top teams is called a big match; avoiding a big match in specific slots of the season is preferable in some situ- ations. For example, a fundamental rule in scheduling the Italian volleyball tournament is that a big match cannot be scheduled in the first two slots of each half. Each team that shares its venue with another team (e.g., teams from the same city or from the same regional area) should play away each time the other team plays at home. The match in which they play against each other is called a derby. Although breaks must be min- imized, they are allowed in the home-away patterns; however, consecutive breaks are forbidden. A home- away pattern without breaks (i.e., an alternating pat- tern of home and away games) is considered favorable for a team. However, because a maximum of two teams can benefit from alternating patterns, avoiding a sched- ule with alternating patterns is preferable.
Teams that also play in European championships should not be scheduled to play away from their venues in more than two slots. The Italian Volleyball League does not want to prevent fans, particularly fans who have purchased season tickets, from watching home games of their favorite teams.
Each year, the league chooses December 26 as a tour- nament day; this is a special date because the majority
of team supporters can attend the match or see it on television; therefore, ensuring a turnover (i.e., a team plays at home on one December 26 and away on that day the next year) is important, especially for fans. Thus, fans who want to attend their favorite team’s game on December 26 must wait at most two years.
Schedule Requirements
The schedule should satisfy requirements that can be imposed based on tournament structure, television rights, and marketing revenues, and should be orga- nized in such a way that the most influential and attrac- tive teams can take advantage of the benefits (espe- cially near European matches played away) that the schedule provides them, but no team is disadvantaged by the schedule. The Italian Volleyball League imposes many nonflexible requirements on the schedule; the double round-robin structure of the tournament also dictates mandatory constraints (modeled as hard con- straints). Other requirements are not mandatory; there- fore, we model them as soft constraints. Below, we list all the constraints of our model, categorized based on their origins.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com