A mathematical programming model for single round-robin tournament problem: A case study of Volleyball Nations League

Journal of Optimization in Industrial Engineering

دوره 15، شماره 2 - شماره پیاپی 33، آذر 2022، صفحه 191-200   

نوع مقاله: Original Manuscript

شناسه دیجیتال (DOI): 10.22094/joie.2022.1891205.1721

نویسندگان

Hamed Jafari^{* 1}؛ Morteza Rajabzadeh²

¹Department of Industrial Engineering, Golpayegan University of Technology, Golpayegan, Iran

²Faculty of Engineering, Mahallat Institute of Higher Education, Mahallat, Iran

چکیده

In this study, a mathematical programming model is developed for a single round-robin tournament problem to provide a schedule for the preliminary round of the Volleyball Nations League. In this setting, the aim is to assign the teams to the pools at each week as well as to specify the host teams of the pools. This schedule is obtained by minimizing the sum of the differences between the total distance traveled by every team and the average of the total distances traveled by all teams. Then, to evaluate the performance of the developed model, it is applied to obtain the optimal schedule for the preliminary round of the Volleyball Men’s Nations League in year 2018. The results indicate that the sum of the travel distance deviations from the average of the total travel distances of all teams obtained from the schedule provided by the mathematical model is significantly lower than that calculated from the schedule presented by the International Volleyball Federation. Moreover, the schedule presented by the International Volleyball Federation leads to a percentage gap of 449.92% in comparison with the optimal schedule provided by the developed model.

کلیدواژه‌ها

Sport scheduling؛ Single round-robin tournament؛ Total travel distance؛ Volleyball Nations League؛ Mathematical programming model

مراجع

Alarcón, F., Durán, G., Guajardo, M., Miranda, J., Muñoz, H., & Ramírez, L. (2017). Operations research transforms the scheduling of chilean soccer leagues and south american world cup qualifiers. Interfaces, 47(1), 52-69.

Atan, T., & Çavdarolu., B. (2018). Minimization of Rest Mismatches in Round Robin Tournaments. Computers & Operations Research, 99, 78-89.

Behnamian, J. (2020). Parallel Jobs Scheduling with a Specific Due Date: Asemi-definite Relaxation-based Algorithm. Journal of Optimization in Industrial Engineering, 13(2), 199-210.

Bhattacharyya, R. (2016). Complexity of the Unconstrained Traveling Tournament Problem. Operations Research Letters, 44(5), 649-654.

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.

Briskorn, D. (2008). Feasibility of home–away-pattern sets for round robin tournaments. Operations Research Letters, 36(3), 283-284.

Briskorn, D. (2009). Combinatorial properties of strength groups in round robin tournaments. European Journal of Operational Research, 192(3), 744-754.

Briskorn, D., & Drexl, A. (2009). A branching scheme for finding cost-minimal round robin tournaments. European Journal of Operational Research, 197(1), 68-76.

Briskorn, D., & Horbach, A. (2012). A Lagrangian approach for minimum cost single round robin tournaments. Computers & Operations Research, 39(3), 718-727.

Briskorn, D., & Knust, S. (2010). Constructing fair sports league schedules with regard to strength groups. Discrete Applied Mathematics, 158(2), 123-135.

Cheung, K.K. (2009). A Benders approach for computing lower bounds for the mirrored traveling tournament problem. Discrete Optimization, 6(2), 189-196.

Cocchi, G., Galligari, A., Nicolino, F.P., Piccialli, V., Schoen, F., & Sciandrone, M. (2018). Scheduling the Italian National Volleyball Tournament. Interfaces, 48(3), 271-284.

De Carvalho, M.A.M., & Lorena, L.A.N. (2012). New models for the mirrored traveling tournament problem. Computers & Industrial Engineering, 63(4), 1089-1095.

De Oliveira, L., & De Souza, C.C., & Yunes, T. (2016). Lower bounds for large traveling umpire instances: New valid inequalities and a branch-and-cut algorithm. Computers & Operations Research, 72, 147-159.

Della Croce, F., & Oliveri, D. (2006). Scheduling the Italian football league: An ILP-based approach. Computers & Operations Research, 33(7), 1963-1974.

Durán, G., Guajardo, M., Miranda, J., Sauré, D., Souyris, S., Weintraub, A., & Wolf, R. (2007). Scheduling the Chilean soccer league by integer programming. Interfaces, 37(6), 539-552.

Durán, G., Guajardo, M., & Wolf-Yadlin, R. (2012). Operations research techniques for scheduling Chile's second division soccer league. Interfaces, 42(3), 273-285.

Duran, S., Özener, O.Ö., & Yaki, E. (2014). League scheduling and game bundling in sports industry. Computers & Industrial Engineering, 74, 92-101.

Elf, M., Jünger, M., & Rinaldi, G. (2003). Minimizing breaks by maximizing cuts. Operations Research Letters, 31(5), 343-349.

Erzurumluoglu, A. (2018). Constructing day-balanced round-robin tournaments with partitions. Discrete Applied Mathematics, 235, 81-91.

Guajardo, M., & Jörnsten, K. (2017). The Stable Tournament Problem: Matching sports schedules with preferences. Operations Research Letters, 45(5), 461-466.

Hassani, A., Hosseini, S.M., & Behroozi, F. (2021). Minimizing the operational costs in a flexible flow shop scheduling problem with unrelated parallel machines. Journal of Optimization in Industrial Engineering, 14(1), 169-184.

Horbach, A. (2010). A combinatorial property of the maximum round robin tournament problem. Operations Research Letters, 38(2), 121-122.

Ichim, B., & Moyano-Fernández, J.J. (2017). On the score sheets of a round-robin football tournament. Advances in Applied Mathematics, 91, 24-43.

Irnich, S. (2010). A new branch-and-price algorithm for the traveling tournament problem. European Journal of Operational Research, 204(2), 218-228.

Jafari, H. (2019). Sustainable development by reusing of recyclables in a textile industry including two collectors and three firms: A game-theoretic approach for pricing decisions. Journal of Cleaner Production, 229, 598-610.

Jafari, H. (2020a). Developing a fuzzy model for the nurse scheduling problem. Journal of Operational Research in Its Applications, 17(2), 93-107.

Jafari, H. (2020b). In‌v‌e‌s‌t‌i‌g‌a‌t‌i‌n‌g u‌n‌c‌e‌r‌t‌a‌i‌n‌t‌i‌e‌s i‌n n‌u‌r‌s‌e s‌c‌h‌e‌d‌u‌l‌i‌n‌g p‌r‌o‌b‌l‌e‌m u‌s‌i‌n‌g f‌u‌z‌z‌y m‌a‌t‌h‌e‌m‌a‌t‌i‌c‌a‌l m‌o‌d‌e‌l‌i‌n‌g a‌p‌p‌r‌o‌a‌c‌h. Sharif Journal of Industrial Engineering & Management, 36(1), 77-85.

Jafari, H. (2021). Nurse scheduling problem by considering total number of required nurses as well as nurses’ preferences for working shifts: An algorithmic game-theoretic approach. Scientia Iranica, Inpress.

Jafari, H. (2022). Investigating environmental and economic aspects of sustainability by recycling PET plastic bottles: A game-theoretic approach. Clean Technologies and Environmental Policy, 24(3), 829-842.

Jafari, H., & Haleh, H. (2021). Nurse scheduling problem by considering fuzzy modeling approach to treat uncertainty on nurses’ preferences for working shifts and weekends off. Journal of Optimization in Industrial Engineering, 14(1), 69-78.

Jafari, H., Hejazi, S.R., & Rasti-Barzoki, M. (2020). Game theoretical approach to price a product under two-echelon supply chain containing e-tail selling channel. International Journal of Services and Operations Management, 36(2), 131-160.

Januario, T., & Urrutia, S. (2015). An analytical study in connectivity of neighborhoods for single round robin tournaments. Operations Research and Computing: Algorithms and Software for Analytics, 188-199.

Januario, T., & Urrutia, S. (2016). A new neighborhood structure for round robin scheduling problems. Computers & Operations Research, 70, 127-139.

Januario, T., Urrutia, S., Ribeiro, C.C., & De Werra, D. (2016). Edge coloring: A natural model for sports scheduling. European Journal of Operational Research, 254(1), 1-8.

Kendall, G., Knust, S., Ribeiro, C.C., & Urrutia, S. (2010). Scheduling in sports: An annotated bibliography. Computers & Operations Research, 37(1), 1-19.

Khelifa, M., & Boughaci, D. (2015). A variable neighborhood search method for solving the traveling tournaments problem. Electronic Notes in Discrete Mathematics, 47, 157-164.

Knust, S. (2008). Scheduling sports tournaments on a single court minimizing waiting times. Operations Research Letters, 36(4), 471-476.

Knust, S., & Lücking, D. (2009). Minimizing costs in round robin tournaments with place constraints. Computers & Operations Research, 36(11), 2937-2943.

Knust, S., & Von Thaden, M. (2006). Balanced home–away assignments. Discrete Optimization, 3(4), 354-365.

Kostuk, K.J., & Willoughby, K.A. (2012). A decision support system for scheduling the Canadian Football League. Interfaces, 42(3), 286-295.

Lewis, R., & Thompson, J. (2011). On the application of graph colouring techniques in round-robin sports scheduling. Computers & Operations Research, 38(1), 190-204.

Lim, A., Rodrigues, B., & Zhang, X. (2006). A simulated annealing and hill-climbing algorithm for the traveling tournament problem. European Journal of Operational Research, 174(3), 1459-1478.

Miyashiro, R., & Matsui, T. (2005). A polynomial-time algorithm to find an equitable home–away assignment. Operations Research Letters, 33(3), 235-241.

Rasmussen, R.V. (2008). Scheduling a triple round robin tournament for the best Danish soccer league. European Journal of Operational Research, 185(2), 795-810.

Rasmussen, R.V., & Trick, M.A. (2007). A Benders approach for the constrained minimum break problem. European Journal of Operational Research, 177(1), 198-213.

Rasmussen, R.V., & Trick, M.A. (2008). Round robin scheduling–a survey. European Journal of Operational Research, 188(3), 617-636.

Ribeiro, C.C., & Urrutia, S. (2012). Scheduling the Brazilian soccer tournament: Solution approach and practice. Interfaces, 42(3), 260-272.

Saur, M.C., Starr, K., Husted, M., & Newman, A.M. (2012). Scheduling softball series in the rocky mountain athletic conference. Interfaces, 42(3), 296-309.

Suksompong, W. (2016). Scheduling asynchronous round-robin tournaments. Operations Research Letters, 44(1), 96-100.

Thielen, C., & Westphal, S. (2011). Complexity of the traveling tournament problem. Theoretical Computer Science, 412(4-5), 345-351.

Toffolo, T.A., Wauters, T., Van Malderen, S., & Berghe, G.V. (2016). Branch-and-bound with decomposition-based lower bounds for the Traveling Umpire Problem. European Journal of Operational Research, 250(3), 737-744.

Trick, M.A., Yildiz, H., & Yunes, T. (2012). Scheduling major league baseball umpires and the traveling umpire problem. Interfaces, 42(3), 232-244.

Urrutia, S., & Ribeiro, C.C. (2004). Minimizing travels by maximizing breaks in round robin tournament schedules. Electronic Notes in Discrete Mathematics, 18, 227-233.

Urrutia, S., & Ribeiro, C.C. (2006). Maximizing breaks and bounding solutions to the mirrored traveling tournament problem. Discrete Applied Mathematics, 154(13), 1932-1938.

Van’t Hof, P., Post, G., & Briskorn, D. (2010). Constructing fair round robin tournaments with a minimum number of breaks. Operations Research Letters, 38(6), 592-596.

Westphal, S. (2014). Scheduling the German basketball league. Interfaces, 44(5), 498-508.

Yavari, S., Azab, A., Fazle Baki, M., Alcelay, M., & Britt, J. (2020). Machine scheduling for multitask machining. Journal of Optimization in Industrial Engineering, 13(2), 1-15.

Zeng, L., & Mizuno, S. (2012). On the separation in 2-period double round robin tournaments with minimum breaks. Computers & Operations Research, 39(7), 1692-1700.