Page 83 - IJOCTA-15-2

M. Khelifa et. al. / IJOCTA, Vol.15, No.2, pp.264-280 (2025)
of -4.35%, -7.92%, and -3.99%, respectively. No- Methodology: Meriem Khelifa
tably, our approach identifies optimal solutions Writing – original draft: Meriem Khelifa
for smaller instances and maintains a general de- Writing – review & editing: Meriem Khelifa,
viation of -1.25% from the best-known solutions. Harous Saad
Our approach achieves better results by integrat-
ing ILP within BBO, combining efficient explo- Availability of data
ration with optimal refinement. By migrating the All the data is included in the paper.
schedules of certain teams from the best solution
and optimizing the remainder with ILP, we effec- References
tively guide the search toward high-quality solu-
1. Lamas-Fernandez C, Martinez-Sykora A, Potts
tions.
CN. Scheduling double round-robin sports tour-
naments. In: Proceedings of the 13th Interna-
5. Conclusion
tional Conference on the Practice and Theory of
This study addresses the TTP, a challenging NP- Automated Timetabling, 2021;2:2021.
hard problem in the domain of sports scheduling. 2. Van Bulck D, Goossens D, Sch¨onberger J, Gua-
The goal of the TTP aims to construct DRRT jardo M. RobinX: A three-field classification
and unified data format for round-robin sports
schedule that reduces the total travel distance for
timetabling. Eur J Oper Res. 2020;280(2):568–
all participating teams.
580.
This study proposes a new hybrid approach
https://doi.org/10.1016/j.ejor.2019.07.023
that combines exact methods with the BBO meta-
3. Ribeiro CC. Sports scheduling: Problems and ap-
heuristic to tackle both the TTP and its variant, plications. Int Trans Oper Res, 2012;19(1-2):201–
the UTTP. First,We propose a novel strategy that 226.
relaxes the ILP formulation of TTP (RILP-TTP) https://doi.org/10.1111/j.1475-3995.2011.
to reduce travel costs in DRRT schedules. We 00819.x
then integrate BBO with RILP-TTP to efficiently 4. Kendall G, Knust S, Ribeiro CC, Urrutia S.
solve instances of both TTP and UTTP. Scheduling in sports: An annotated bibliography.
The results of our experiments demonstrate Comput Oper Res., 2010;37(1):1–19.
that the proposed method offers strong perfor- https://doi.org/10.1016/j.cor.2009.05.013
mance achieving the best-known solutions for sev- 5. Dur´an G, Dur´an S, Marenco J, Mascialino F, Rey
enteen instances and setting new best-known so- PA. Scheduling Argentina’s professional basket-
lutions for the sixteen instances of the National ball leagues: A variation on the travelling tour-
Leagues US. This performance exceeds that of nament problem. Eur J Oper Res. 2018.
several prominent methods when applied to the 6. Khelifa M, Boughaci D. A cooperative local
TTP. search method for solving the traveling tourna-
In our future work, we plan to investigate ment problem. Comput Inform., 2019;37(6).
https://doi.org/10.4149/cai 2 018 61 386
the incorporation of deep learning techniques into
metaheuristic methods to tackle further chal- 7. Thielen C, Westphal S. Complexity of the trav-
eling tournament problem. Theor Comput Sci.,
lenges in sports scheduling problems.
2011;412(4-5):345–351.
Acknowledgments https://doi.org/10.1016/j.tcs.2010.10.001
8. Bhattacharyya R. Complexity of the uncon-
None. strained traveling tournament problem. Oper Res
Lett., 2016;44(5):649–654.
Funding https://doi.org/10.1016/j.orl.2016.07.011
None. 9. Irnich S. A new branch-and-price algorithm for
the traveling tournament problem. Eur J Oper
Conflict of interest Res., 2010;204(2):218–228.
https://doi.org/10.1016/j.ejor.2009.10.024
The authors declare that they have no conflict of
10. Uthus DC, Riddle PJ, Guesgen HW. DFS* and
interest regarding the publication of this article.
the traveling tournament problem. In: Interna-
tional Conference on AI and OR Techniques in
Author contributions
Constraint Programming for Combinatorial Opti-
Conceptualization: Meriem Khelifa mization Problems, 2009; 279–293. Springer.
Formal analysis: Meriem Khelifa, Harous Saad, https://doi.org/10.1007/978-3-642-01929-6 2 1
Mezzoud Saliha 11. Challenge Traveling Tournament Instances.
Investigation: Meriem Khelifa, Mohammed Available from: http://mat.tepper.cmu.edu/T
OURN [Accessed 29 January 2016].
Abdelaziz Hacini
278