Hybridizing biogeography-based optimization and integer programming for solving the travelling tournament problem in sport scheduling

Abstract

Combining metaheuristics with exact methods improves solution quality by efficiently exploring promising regions and refining the obtained solutions. This paper introduces a novel hybrid approach that combines exact methods and metaheuristics to address the Traveling Tournament Problem (TTP) in sports scheduling. The TTP, a critical aspect of sports management, aims to create a tournament schedule that minimizes the total travel distance of participating teams, which is essential for controlling league management costs and maximizing revenue. However, its complex optimization requirements and tournament structure make it highly challenging to solve efficiently. Our hybrid approach combines exact methods with the Biogeography-Based Optimization (BBO) metaheuristic to tackle both the TTP and its variant, the Unconstrained Traveling Tournament Problem (UTTP). We introduce a novel relaxation technique to enhance the efficiency of the Integer Linear Programming (ILP) formulation for the TTP. This technique involves fixing the schedule for a subset of teams and employing an ILP solver to optimize the schedule for the remaining teams. This relaxation technique is seamlessly integrated into the BBO operators. We evaluate the effectiveness of our method using publicly available benchmark instances and compare it with existing techniques for both TTP and UTTP. Our experimental results demonstrate that the proposed approach achieves competitive solution quality. It outperforms prior methods on UTTP for the US National Baseball League NL16 instances and some prominent methods when applied to TTP.

Keywords

Sports scheduling / Traveling tournament problem (TTP) / Biogeography Based Optimization / Integer programming

Funding

None.

Declaration of competing interest

The authors declare that they have no conflict of interest regarding the publication of this article.

References

[1] Lamas-Fernandez C, Martinez-Sykora A, Potts CN. Scheduling double round-robin sports tournaments. In: Proceedings of the 13th International Conference on the Practice and Theory of Automated Timetabling, 2021;2:2021.

[2] Van Bulck D, Goossens D, Schönberger J, Guajardo M. RobinX: A three-field classification and unified data format for round-robin sports timetabling. Eur J Oper Res. 2020; 280(2):568-580. https://doi.org/10.1016/j.ejor.2019.07.023

[3] Ribeiro CC. Sports scheduling: Problems and applications. Int Trans Oper Res, 2012; 19(1-2):201-226. https://doi.org/10.1111/j.1475-3995.2011.00819.x

[4] Kendall G, Knust S, Ribeiro CC, Urrutia S. Scheduling in sports: An annotated bibliography. Comput Oper Res., 2010; 37(1):1-19. https://doi.org/10.1016/j.cor.2009.05.013

[5] Durán G, Durán S, Marenco J, Mascialino F, Rey PA. Scheduling Argentina’s professional basketball leagues: A variation on the travelling tournament problem. Eur J Oper Res. 2018.

[6] Khelifa M, Boughaci D. A cooperative local search method for solving the traveling tournament problem. Comput Inform., 2019; 37(6). https://doi.org/10.4149/cai_2018_6_1386

[7] Thielen C, Westphal S. Complexity of the traveling tournament problem. Theor Comput Sci., 2011; 412(4-5):345-351. https://doi.org/10.1016/j.tcs.2010.10.001

[8] Bhattacharyya R. Complexity of the unconstrained traveling tournament problem. Oper Res Lett., 2016; 44(5):649-654. https://doi.org/10.1016/j.orl.2016.07.011

[9] Irnich S. A new branch-and-price algorithm for the traveling tournament problem. Eur J Oper Res., 2010; 204(2):218-228. https://doi.org/10.1016/j.ejor.2009.10.024

[10] Uthus DC, Riddle PJ, Guesgen HW. DFS* and the traveling tournament problem. In: International Conference on AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 2009; 279-293. Springer. https://doi.org/10.1007/978-3-642-01929-6_21

[11] Challenge Traveling Tournament Instances. Available from: http://mat.tepper.cmu.edu/TOURN [Accessed 29 January 2016].

[12] RobinX Validator. Available from: https://robinxval.ugent.be/RobinX/contact.php [Accessed 16 January 2020].

[13] Wolsey LA. Integer Programming. John Wiley & Sons; 2020. https://doi.org/10.1002/9781119606475

[14] Ustuncelik M, Koc C, Tunc H. Bin packing problem with restricted item fragmentation: Assignment of jobs in multiproduct assembly environment with overtime. Int J Optim Control Theor Appl. (IJOCTA), 2024; 14(1):32-40. https://doi.org/10.11121/ijocta.1435

[15] Kostyukova O, Tchemisova T. Exploring constraint qualification-free optimality conditions for linear second-order cone programming. Int J Optim Control Theor Appl. (IJOCTA), 2024; 14(3):168-182. https://doi.org/10.11121/ijocta.1421

[16] Mariem K, Saliha M, Abdelaziz HM, Amine FM, Khaled BM. Novel solutions to the multidimensional knapsack problem using CPLEX: New results on ORX benchmarks. J Ubiquitous Comput Commun Technol, 2024; 6(3):294-310. https://doi.org/10.36548/jucct.2024.3.007

[17] Rasmussen RV, Trick MA. Round robin scheduling-A survey. Eur J Oper Res., 2008; 188(3):617-636. https://doi.org/10.1016/j.ejor.2007.05.046

[18] Uthus DC, Riddle PJ, Guesgen HW. An ant colony optimization approach to the traveling tournament problem. In: Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation, 2009; 81-88. ACM. https://doi.org/10.1145/1569901.1569913

[19] 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. https://doi.org/10.1287/inte.1110.0587

[20] Khelifa M, Boughaci D, Aïmeur E. A new approach based on graph matching and evolutionary approach for sport scheduling problem. Intell Decis Technol., 2020; 14(4):565-580. https://doi.org/10.3233/IDT-190114

[21] Khelifa M, Boughaci D, Aïmeur E. A novel graph-based heuristic approach for solving sport scheduling problem. In: International Conference on Principles and Practice of Constraint Programming, 2018; 229-241. Springer. https://doi.org/10.1007/978-3-319-98334-9_16

[22] Khelifa M, Boughaci D. Hybrid harmony search combined with variable neighborhood search for the traveling tournament problem. In: International Conference on Computational Collective Intelligence, 2016; 520-530. Springer. https://doi.org/10.1007/978-3-319-45243-2_48

[23] Carvalho MAM, Lorena LAN. New models for the mirrored traveling tournament problem. Comput Ind Eng., 2012; 63(4):1089-1095. https://doi.org/10.1016/j.cie.2012.08.002

[24] Choubey NS. A novel encoding scheme for traveling tournament problem using genetic algorithm. IJCA Spec Issue Evol Comput., 2010; 2(7):79-82. https://doi.org/10.5120/1536-139

[25] Khelifa M, Boughaci D. A variable neighborhood search method for solving the traveling tournaments problem. Electron Notes Discret Math., 2015; 47:157-164. https://doi.org/10.1016/j.endm.2014.11.021

[26] Biajoli FL, Lorena LAN. Clustering search approach for the traveling tournament problem. In: Mexican International Conference on Artificial Intelligence. Springer; 2007: 83-93

[27] Ribeiro CC, Urrutia S. Heuristics for the mirrored traveling tournament problem. Eur J Oper Res., 2007; 179(3):775-787. https://doi.org/10.1016/j.ejor.2005.03.061

[28] Costa FN, Urrutia S, Ribeiro CC. An ILS heuristic for the traveling tournament problem with predefined venues. Ann Oper Res., 2012; 194(1):137-150. https://doi.org/10.1007/s10479-010-0719-9

[29] Xiang C, Wu Z, van Den Berg D, Weise T. NSGA-II vs. Randomized local search vs. frequency fitness assignment on the traveling tournament problem. In: 16th International Joint Conference on Computational Intelligence (IJCCI 2024), 2024; 38-49. SciTePress. https://doi.org/10.5220/0012891500003837

[30] Westphal S, Noparlik K. A 5.875-approximation for the traveling tournament problem. Ann Oper Res., 2014; 218(1):347-360. https://doi.org/10.1007/s10479-012-1061-1

[31] Imahori S, Matsui T, Miyashiro R. A 2.75-approximation algorithm for the unconstrained traveling tournament problem. Ann Oper Res., 2014; 218(1):237-247. https://doi.org/10.1007/s10479-012-1161-y

[32] Chatterjee D, Roy BK. An improved scheduling algorithm for traveling tournament problem with maximum trip length two. 2021. arXiv preprint arXiv:2109.09065.

[33] Xiao M, Kou S. An improved approximation algorithm for the traveling tournament problem with maximum trip length two. In: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. 2016

[34] Anagnostopoulos A, Michel L, Van Hentenryck P, Vergados Y. A simulated annealing approach to the traveling tournament problem. J Sched., 2006; 9(2):177-193. https://doi.org/10.1007/s10951-006-7187-8

[35] Khelifa M, Boughaci D, Aïmeur E. An enhanced genetic algorithm with a new crossover operator for the traveling tournament problem. In: Control, Decision and Information Technologies (CoDIT), 2017 4th International Conference on, 2017; 1072-1077. IEEE. https://doi.org/10.1109/CoDIT.2017.8102741

[36] Wallace AR. Wallace’s geographical distribution of animals. 1877.

[37] Wallace AR. The geographical distribution of animals: with a study of the relations of living and extinct faunas as elucidating the past changes of the earth’s surface, Volume 1. Cambridge University Press; 2011. https://doi.org/10.1017/CBO9781139097116

[38] Darwin C, Beer G. The origin of species. Dent; 1951.

[39] Simon D. Biogeography-based optimization. IEEE Trans Evol Comput., 2008; 12(6):702-713. https://doi.org/10.1109/TEVC.2008.919004

[40] de Werra D. Some models of graphs for scheduling sports competitions. Discret Appl Math., 1988; 21(1):47-65. https://doi.org/10.1016/0166-218X(88)90033-9

[41] Hansen P, Mladenović N. Variable neighborhood search: Principles and applications. Eur J Oper Res., 2001; 130(3):449-467. https://doi.org/10.1016/S0377-2217(00)00100-4

[42] Pérez Cáceres L, Riff MC. AISTTP: An artificial immune algorithm to solve traveling tournament problems. Int J Comput Intell Appl., 2012; 11(01):1250008. https://doi.org/10.1142/S1469026812500083

[43] Rasmussen RV, Trick MA. The timetable constrained distance minimization problem. Ann Oper Res., 2009; 171(1):45. https://doi.org/10.1007/s10479-008-0384-4

[44] Chen P-C, Kendall G, Vanden Berghe G. An ant-based hyperheuristic for the travelling tournament problem. In: Computational Intelligence in Scheduling, 2007. SCIS’07. IEEE Symposium on, 2007; 19-26. IEEE. https://doi.org/10.1109/SCIS.2007.367665

[45] Tajbakhsh A, Eshghi K, Shamsi A. A hybrid PSO-SA algorithm for the travelling tournament problem. Eur J Ind Eng., 2012; 6(1):2-25. https://doi.org/10.1504/EJIE.2012.0448080