Page 69 - IJOCTA-15-2

An International Journal of Optimization and Control: Theories & Applications
ISSN: 2146-0957 eISSN: 2146-5703
Vol.15, No.2, pp.264-280 (2025)
https://doi.org/10.36922/ijocta.1726

RESEARCH ARTICLE

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

2
1*
3
Meriem Khelifa , Saad Harous , Saliha Mezzoudj , and Mohammed Abdelaziz Hacini 1
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
khelifa.meriem@univ-ouargla.dz, harous@sharjah.ac.ae, s.mezzoudj@univ-alger.dz,
Hacini.Mohammedabdelaziz@univ-ouargla.dz
ARTICLE INFO ABSTRACT

Article History: Combining metaheuristics with exact methods improves solution quality by ef-
Received: November 9, 2024 ficiently exploring promising regions and refining the obtained solutions. This
Accepted: February 5, 2025 paper introduces a novel hybrid approach that combines exact methods and
Published Online: April 4, 2025 metaheuristics to address the Traveling Tournament Problem (TTP) in sports
Keywords: scheduling. The TTP, a critical aspect of sports management, aims to create a
Sports scheduling tournament schedule that minimizes the total travel distance of participating
Traveling tournament problem (TTP) teams, which is essential for controlling league management costs and maximiz-
Biogeography Based Optimization ing revenue. However, its complex optimization requirements and tournament
Integer programming structure make it highly challenging to solve efficiently. Our hybrid approach
combines exact methods with the Biogeography-Based Optimization (BBO)
AMS Classification:
metaheuristic to tackle both the TTP and its variant, the Unconstrained Trav-
90C27; 68T20
eling 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 in-
stances and compare it with existing techniques for both TTP and UTTP. Our
experimental results demonstrate that the proposed approach achieves com-
petitive solution quality. It outperforms prior methods on UTTP for the US
National Baseball League NL16 instances and some prominent methods when
applied to TTP.

1. Introduction inefficient schedules may impact profitability neg-
atively. Additionally, minimizing travel dis-
tances allows athletes more time to rest and train
throughout the season.
Sports scheduling has drawn significant interest
from researchers and practitioners across fields
like operational research, scheduling, graph the- The TTP is a complex sports scheduling chal-
ory, and constraint programming. 1–6 A primary lenge that involves creating a Double Round-
factor driving this interest is the travelling tour- Robin Tournament (DRRT) schedule for teams
nament problem (TTP), which has become piv- located in different cities with predefined travel
otal in sports scheduling. Well-structured TTP distances. The primary goal of the TTP is to
schedules can boost revenue significantly, whereas reduce the total travel distance across all teams,
*Corresponding Author
264