Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

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