Page 72 - IJOCTA-15-2

Hybridizing biogeography-based optimization and integer programming for solving the travelling tournament ...
1.3. Contribution and overview and evolve in different habitats. Mark 36–38 cre-
ated biogeographic mathematical models to study
Even in its simplified form, the TTP remains the movement of species among habitats, the for-
a highly challenging combinatorial optimization
problem due to its unique formulation, which in- mation of new species, and extinction processes.
A habitat is defined as a distinct living space,
volves both an optimization objective and integer
with its quality is quantified using the Habitat
constraints. Consequently, solving the TTP de-
Suitability Index (HSI). Factors affecting habit-
mands methods that deliver high computational
ability, called Suitability Index Variables (SIV),
efficiency without compromising solution quality.
include rainfall, vegetation diversity, topography,
For larger TTP instances, exact methods en-
land size, and temperature.
counter scalability limitations, often failing when
The essential features of habitats are listed
the problem size reaches 10 teams, as demon-
strated in. 9,11 Metaheuristic approaches, 6,21,34,35 below:
on the other hand, offer greater scalability and • Habitats offering optimal conditions for
can manage larger TTP instances. In this study, biological species are characterized by a
we introduce an innovative approach that inte- high HSI, which typically correlates with
grates evolutionary BBO metaheuristics with an a greater number of resident species. In
integer programming solver to effectively tackle contrast, habitats with less favorable con-
the TTP, generating high-performance outcomes ditions exhibit a low HSI.
within a practical timeframe. • By enabling species migration, high-HSI
habitats typically adopt characteristics
The key contributions of our work: from low-HSI habitats. Consequently,
these features persist in the high-HSI
• First, we devise a new strategy for reduc-
habitats and emerge as new traits in the
ing the travel cost of any input DRRT
schedules. This strategy is based on Re- low-HSI habitats.
laxing ILP of TTP (RILP-TTP). Figure 1 presents a linear migration model de-
• Next, we apply the BBO combined with picting species abundance within a habitat and
RILP-TTP to generate new DRRT sched- demonstrates the link among species count, im-
ules that reduce travel costs. migration rate, and emigration rate. It can be
• Our computational results demonstrate observed that as the species count increases (in
that our approach ranks among the top- favorable habitats), the immigration rate (λ) de-
performing methods for the UTTP. It creases, while the emigration rate (µ) rises. Con-
achieves notable enhancements over the versely, when the species count is low (in habitats
previously best-known solutions for the with low HSI), the immigration rate (λ) increases,
US National Baseball League (NL16). and the emigration rate (µ) decreases.
This enhanced solution for NL16 has
been verified and published on the Chal-
lenge Traveling Tournament Instances
website. 12
• Our approach matches the optimal solu-
tion in seventeen cases and surpasses sev-
eral other notable methods applied to the
TTP.
The organization of the paper is as follows:
In section 2 we provide an overview of BBO and
explains its operational procedure. Section 3 out-
lines the proposed methodology, while Section 4
discusses the computational results. The paper
concludes with Section 5. Figure 1. Evolution of (λ) and (µ) rates with the
number of species
2. BBO

BBO is a biogeography-inspired evolutionary The BBO method, 39 based on biogeographic
algorithm. 36,37 . Biogeography examines the spa- mathematical models, is summarized in its gen-
tial and temporal distribution of species (includ- eral framework in Table 3.
ing plant and animal life) across various environ- The BBO method initiates with a popula-
ments, seeking to understand how species sustain tion of solutions, represented as habitats, each
267