AccScience Publishing / IJOCTA / Online First / DOI: 10.36922/ijocta.1726
Submit to IJOCTA
Cite this article
5
Download
74
Views
Journal Browser
Volume | Year
Issue
Search
Forthcoming Issue
Current Issue
View All
News and Announcements
View All
RESEARCH ARTICLE

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

Meriem Khelifa1* ,  Saad Harous2 ,  Saliha Mezzoudj3 ,  Mohammed Abdelaziz Hacini1
Show Less
1 Department of Computer Science and Information Technologies, University of Kasdi Merbah Ouargla, Algeria
2 Department of Computer Science,College of Computing and Informatics, University of Sharjah, Sharjah, UAE
3 Department of Computer Science, University of Algiers, Algeria
IJOCTA, 1726 https://doi.org/10.36922/ijocta.1726
Submitted: 9 November 2024 | Accepted: 5 February 2025 | Published: 4 April 2025
© 2025 by the Author(s). This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution -Noncommercial 4.0 International License (CC-by the license) ( https://creativecommons.org/licenses/by-nc/4.0/ )
Download PDF
Cite
XML
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.
Conflict of 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 tour- In: Proceedings of the 13th Interna- tional Conference on the Practice and Theory of Automated Timetabling, 2021;2:2021.

 

  1. Van Bulck D, Goossens D, Sch¨onberger J, Gua- jardo 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

 

  1. Ribeiro CC. Sports scheduling: Problems and ap- plications. Int Trans Oper Res, 2012;19(1-2):201– 226.https://doi.org/10.1111/j.1475-3995.2011.x

 

  1. 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

 

  1. Dur´an G, Dur´an S, Marenco J, Mascialino F, Rey PA. Scheduling Argentina’s professional basket- ball leagues: A variation on the travelling tour- nament problem. Eur J Oper Res.

 

  1. Khelifa M, Boughaci D. A cooperative local search method for solving the traveling tourna- ment problem. Comput Inform., 2019;37(6). https://doi.org/10.4149/cai201861386

 

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

 

  1. Bhattacharyya R. Complexity of the uncon- strained traveling tournament problem. Oper Res , 2016;44(5):649–654. https://doi.org/10.1016/j.orl.2016.07.011

 

  1. 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

 

  1. Uthus DC, Riddle PJ, Guesgen HW. DFS* and the traveling tournament problem. In: Interna- tional Conference on AI and OR Techniques in Constraint Programming for Combinatorial Opti- mization Problems, 2009; 279–293. Springer. https://doi.org/10.1007/978-3-642-01929-621

 

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

 

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

 

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

 

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

 

  1. Kostyukova O, Tchemisova T. Exploring con- straint 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

 

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

 

  1. 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

 

  1. 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

 

  1. Bonomo F, Cardemil A, Dur´an G, Marenco J, Sab´an D. An application of the traveling tourna- ment problem: The Argentine volleyball league. 2012;42(3):245–259. https://doi.org/10.1287/inte.1110.0587

 

  1. Khelifa M, Boughaci D, A¨ımeur E. A new approach based on graph matching and evolution- ary approach for sport scheduling problem. Intell Decis Technol., 2020;14(4):565–580. https://doi.org/10.3233/IDT-190114

 

  1. Khelifa M, Boughaci D, A¨ımeur E. A novel graph- based heuristic approach for solving sport sched-uling problem. In: International Conference on Principles and Practice of Constraint Program ming, 2018; 229–241. Springer. https://doi.org/10.1007/978-3-319-98334-916

 

  1. Khelifa M, Boughaci D. Hybrid harmony search combined with variable neighborhood search for the traveling tournament problem. In: Interna- tional Conference on Computational Collective Intelligence, 2016; 520–530. Springer. https://doi.org/10.1007/978-3-319-45243-248

 

  1. 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

 

  1. 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

 

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

 

  1. Biajoli FL, Lorena LAN. Clustering search ap- proach for the traveling tournament problem. In: Mexican International Conference on Artificial Intelligence. Springer; 2007: 83–93

 

  1. 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

 

  1. Costa FN, Urrutia S, Ribeiro CC. An ILS heuris- tic for the traveling tournament problem with pre- defined venues. Ann Oper Res., 2012;194(1):137– 150. https://doi.org/10.1007/s10479-010-0719-9

 

  1. Xiang C, Wu Z, van Den Berg D, Weise T. Randomized local search vs. NSGA-II vs. fre- quency fitness assignment on the traveling tourna- ment problem. In: 16th International Joint Con- ference on Computational Intelligence (IJCCI 2024), 2024; 38–49. SciTePress. https://doi.org/10.5220/0012891500003837

 

  1. 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

 

  1. 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

 

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

 

  1. Xiao M, Kou S. An improved approximation al- gorithm for the traveling tournament problem with maximum trip length two. In: 41st Inter- national Symposium on Mathematical Founda- tions of Computer Science (MFCS 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. 2016

 

  1. 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

 

  1. Khelifa M, Boughaci D, A¨ımeur E. An enhanced genetic algorithm with a new crossover opera- tor 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

 

  1. Wallace AR. Wallace’s geographical distribution of animals. 1877.

 

  1. Wallace AR. The geographical distribution of an- imals: with a study of the relations of living and extinct faunas as elucidating the past changes of the earth’s surface, Volume 1. Cambridge Univer- sity Press; 2011. https://doi.org/10.1017/CBO9781139097116

 

  1. Darwin C, Beer G. The origin of species. Dent; 1951.

 

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

 

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

 

  1. Hansen P, Mladenovi´c, 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

 

  1. P´erez C´aceres L, Riff MC. AISTTP: An artifi- cial immune algorithm to solve traveling tour- nament problems. Int J Comput Intell Appl., 2012;11(01):1250008. https://doi.org/10.1142/S1469026812500083

 

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

 

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

 

  1. 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
Share
Back to top
An International Journal of Optimization and Control: Theories & Applications, Electronic ISSN: 2146-5703 Print ISSN: 2146-0957, Published by AccScience Publishing
We use cookies on our website to ensure you get the best experience.
Read more about our cookies here
Accept