Abstract:
This article describes an optimization process used to schedule the First Division of Argentina's professional volleyball league. The teams in the league are grouped into couples, and matches are held on Thursdays and Saturdays. In each pair of consecutive Thursday-Saturday matches, the two teams in each couple play against two teams from another couple. Minimization of travel distances is critical because the teams' home locations are scattered throughout the country and teams do not return to their home sites between consecutive away matches, making this problem a variation of the well-known traveling tournament problem. The coupled format gives rise to two key decisions: (1) how to couple the teams, and (2) how to schedule the matches. We apply integer programming techniques and a tabu search heuristic to solve these questions. The league successfully used the resulting schedules in its 2007-2008, 2008-2009, 2009-2010, and 2010-2011 seasons, reducing the total travel distance while meeting all of the teams' requirements. This is the first application of the traveling tournament problem to a real-world sports league reported in the optimization literature. © 2012 INFORMS.
Registro:
Documento: |
Artículo
|
Título: | An application of the traveling tournament problem: the argentine volleyball league |
Autor: | Bonomo, F.; Cardemil, A.; Durán, G.; Marenco, J.; Sabán, D. |
Filiación: | Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, 1428 Buenos Aires, Argentina Consejo Nacional de Investigaciones Cientificas y Técnicas, 1033 Buenos Aires, Argentina Instituto de Cálculo and Departamento de Matemática, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, 1428 Buenos Aires, Argentina Departamento de Ingeniería Industrial, Facultad de Ciencias Fisicas y Matemáticas, Universidad de Chile, 8370439 Santiago, Chile Instituto de Ciencias, Universidad Nacional de General Sarmiento, 1613 Buenos Aires, Argentina
|
Palabras clave: | Integer programming; Sports scheduling; Team couples; Traveling tournament problem; Volleyball |
Año: | 2012
|
Volumen: | 42
|
Número: | 3
|
Página de inicio: | 245
|
Página de fin: | 259
|
DOI: |
http://dx.doi.org/10.1287/inte.1110.0587 |
Título revista: | Interfaces
|
Título revista abreviado: | Interfaces
|
ISSN: | 00922102
|
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00922102_v42_n3_p245_Bonomo |
Referencias:
- Bartsch, T., Drexl, A., Kroger, S., Scheduling the professional soccer leagues of Austria and Germany (2006) Computers and Operations Research, 33 (7), pp. 1907-1937. , DOI 10.1016/j.cor.2004.09.037, PII S0305054804002606, Operations Research in Sport
- Bhattacharyya, R., (2009) A note on the complexity of traveling tournament problem, p. 2011. , http://www.optimization-online.org/DB_FILE/2009/12/2480.pdf, Accessed June 3
- Briskorn, D., Drexl, A., A branch-and-price algorithm for scheduling sport leagues (2008) J. Oper. Res. Soc., 60 (1), pp. 84-93
- Briskorn, D., Drexl, A., A branching scheme for finding costminimal round robin tournaments (2009) Eur. J. Oper. Res., 197 (1), pp. 68-76
- Briskorn, D., Drexl, A., IP models for round robin tournaments (2009) Comput. Oper. Res., 36 (3), pp. 837-852
- Cardemil, A., Durán, G., Un algoritmo tabú search para el traveling tournament problem (in Spanish) (2004) Revista Ingeniería de Sistemas, 18 (1), pp. 95-115
- Cheung, K., A Benders approach for computing improved lower bounds for the mirrored traveling tournament problem (2009) Discrete Optim., 6 (1), pp. 189-196
- Della Croce, F., Oliveri, D., Scheduling the Italian Football League: An ILP-based approach (2006) Computers and Operations Research, 33 (7), pp. 1963-1974. , DOI 10.1016/j.cor.2004.09.025, PII S0305054804002473, Operations Research in Sport
- Della Croce, F., Tadei, R., Asioli, P., Scheduling a round robin tennis tournament under courts and players availability constraints (1999) Ann. Oper. Res., 92 (1), pp. 349-361
- De Werra, D., Geography, games and graphs (1980) Discrete Appl. Math., 2 (4), pp. 327-337
- De Werra, D., Some models of graphs for scheduling sports competitions (1988) Discrete Appl. Math., 21 (1), pp. 47-65
- Dinitz, J., Stinson, D., A hill-climbing algorithm for the construction of one-factorizations and room squares. SIAM (1987) J. Algebraic Discrete Methods, 8 (3), pp. 430-438
- Durán, G., Guajardo, M., Miranda, J., Sauré, D., Souyris, S., Weintraub, A., Wolf, R., Scheduling the Chilean soccer league by integer programming (2007) Interfaces, 37 (6), pp. 539-552
- Easton, K., Nemhauser, G., Trick, M., The traveling tournament problem: Description and benchmarks (2001) Proc. 7th Internat. Conf. Principles Practice Constraint Programming, , Springer-Verlag, London
- Easton, K., Nemhauser, G., Trick, M., Solving the Travelling Tournament Problem: A combined integer programming and constraint programming approach (2003) Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2740, pp. 100-109
- Easton, K., Nemhauser, G., Trick, M., Sports scheduling (2004) Handbook of Scheduling, 52, pp. 1-52. , CRC Press, Boca Raton, FL, J. Leung, ed
- Fleurent, C., Ferland, J., Allocating games for the NHL using integer programming (1993) Oper. Res., 41 (4), pp. 649-654
- Froncek, D., Scheduling the Czech national basketball league (2001) Congressus Numerantium, 153 (1), pp. 5-24
- Goossens, D., Spieksma, F., Scheduling the Belgian soccer league (2009) Interfaces, 39 (2), pp. 109-118
- Ikebe, Y., Tamura, A., On the existence of sports schedules with multiple venues (2008) Discrete Appl. Math., 156 (10), pp. 1694-1710
- Irnich, S., A new branch-and-price algorithm for the traveling tournament problem (2010) Eur. J. Oper. Res., 204 (2), pp. 218-228
- Kendall, G., Knust, S., Ribeiro, C., Urrutia, S., Scheduling in sports: An annotated bibliography (2010) Comput. Oper. Res., 37 (1), pp. 1-19
- Koch, T., (2010) ZIMPL user guide, , http://zimpl.zib.de, Accessed April 16 2010
- Korte, B., Vygen, J., (2000) Combinatorial Optimization, , Springer- Verlag, Berlin
- Nemhauser, G., Trick, M., (1998) Scheduling a major college basketball conference. Oper. Res., 46 (1), pp. 1-8
- Noronha, T., Ribeiro, C., Durán, G., Souyris, S., Weintraub, A., A branch-and-cut algorithm for scheduling the highlyconstrained Chilean soccer tournament (2007) Lecture Notes in Computer Science, 3867, pp. 174-186. , Springer-Verlag, Berlin
- Nurmi, K., Kyngäs, J., Improving the schedule of the Finnish major ice hockey league (2009) Proc. 2nd Internat. Conf. Math., , Sport, Groningen, The Netherlands
- Nurmi, K., Goossens, D., Bartsch, T., Bonomo, F., Briskorn, D., Durán, G., Kyngäs, J., A framework for a highly constrained sports scheduling problem (2010) Proc. Internat. MultiConference of Engineers and Comput, , Scientists, AIP Press, New York
- Rasmussen, R.V., Scheduling a triple round robin tournament for the best Danish soccer league (2008) European Journal of Operational Research, 185 (2), pp. 795-810. , DOI 10.1016/j.ejor.2006.12.050, PII S0377221707000744
- Rasmussen, R., Trick, M., Round robin scheduling-A survey (2008) Eur. J. Oper. Res., 188 (3), pp. 617-636
- Rey, P., Eliminating redundant solutions of some symmetric combinatorial integer programs (2004) Electronic Notes Discrete Math, 18 (1), pp. 201-206
- Ribeiro, C.C., Urrutia, S., Heuristics for the mirrored traveling tournament problem (2007) European Journal of Operational Research, 179 (3), pp. 775-787. , DOI 10.1016/j.ejor.2005.03.061, PII S0377221705007368
- Russell, R., Leung, J., Devising a cost effective schedule for a baseball league (1994) Oper. Res., 42 (4), pp. 614-625
- Schreuder, J., Combinatorial aspects of construction of competition in Dutch professional football leagues (1992) Discrete Appl. Math., 35 (3), pp. 301-312
- Thielen, C., Westphal, S., Complexity of the traveling tournament problem (2011) Theoret. Comput. Sci., 412 (4-5), pp. 345-351
- Trick, M., (2010) Challenge Traveling Tournament Instances, , http://mat.tepper.cmu.edu/TOURN, Accessed April 16
- Uthus, D., Riddle, P., Guesgen, H., DFS and the Traveling tournament problem (2009) Proc. CPAIOR 2009, , Springer-Verlag, Berlin
- Wright, M.B., Scheduling fixtures for New Zealand Cricket (2005) IMA Journal Management Mathematics, 16 (2), pp. 99-112. , DOI 10.1093/imaman/dpi003, OR in Sport
- Wright, M.B., Scheduling fixtures for Basketball New Zealand (2006) Computers and Operations Research, 33 (7), pp. 1875-1893. , DOI 10.1016/j.cor.2004.09.024, PII S0305054804002461, Operations Research in Sport
Citas:
---------- APA ----------
Bonomo, F., Cardemil, A., Durán, G., Marenco, J. & Sabán, D.
(2012)
. An application of the traveling tournament problem: the argentine volleyball league. Interfaces, 42(3), 245-259.
http://dx.doi.org/10.1287/inte.1110.0587---------- CHICAGO ----------
Bonomo, F., Cardemil, A., Durán, G., Marenco, J., Sabán, D.
"An application of the traveling tournament problem: the argentine volleyball league"
. Interfaces 42, no. 3
(2012) : 245-259.
http://dx.doi.org/10.1287/inte.1110.0587---------- MLA ----------
Bonomo, F., Cardemil, A., Durán, G., Marenco, J., Sabán, D.
"An application of the traveling tournament problem: the argentine volleyball league"
. Interfaces, vol. 42, no. 3, 2012, pp. 245-259.
http://dx.doi.org/10.1287/inte.1110.0587---------- VANCOUVER ----------
Bonomo, F., Cardemil, A., Durán, G., Marenco, J., Sabán, D. An application of the traveling tournament problem: the argentine volleyball league. Interfaces. 2012;42(3):245-259.
http://dx.doi.org/10.1287/inte.1110.0587