Page 77 - IJOCTA-15-2

M. Khelifa et. al. / IJOCTA, Vol.15, No.2, pp.264-280 (2025)
less favorable habitats based on a probability of Deviating below this value leads to a runtime ex-
change, which is determined by the immigration ceeding 5 hours (Figures 7 and 8). Similar consid-
rate λ (as shown in equation 23) and the emigra- erations apply to NL 14 and NL 16 , where the best
tion rate µ (as shown in equation 24). Figure 3 Ft values are approximately 7 and 8, respectively,
illustrates the migration process, with Habitat2 which corresponds to about half of the total teams
serving as the immigrating habitat and Habitat1 (n/2).
as the emigrating habitat:
(1) Migrate Siv Habitat1 of Habitat 1 to the
Habitat 2; here the Siv Habitat1 represents 4.2. Numerical results
the schedule of team t 1 .
(2) We create an incomplete schedule with The effectiveness of the proposed method is as-
only the schedule of the first team. sessed using multiple benchmark datasets for the
We then solve our Relaxed ILP (RILP- TTP . The implementation was carried out using
TTP)(explained in Section 3.1) where Java, with experiments performed on a system
Ft= t 1 to create and optimize the sched- equipped with an Intel(R) Core(TM) i5-10210U
processor (1.60 GHz) and 8 GB of RAM.
ule for the remaining five teams t 2 , t 3 ,t 4
and t 5 . GameNonFt=represents all the The performance of the proposed TTP BBO
games of Habitat2 excluding those of Ft; approach was assessed using NL x and CON x
here, all the games of the first team are instances 2,12 (refer to Section 1.1). This section
highlighted in red, as shown in Figure 3. provides experimental results to analyze the effi-
(3) In the obtained schedule, we retain the ciency of our approach. Our approach was tested
home/away patterns and the location of on various NL and CON instances (outlined in
GameNonFt in Habitat2, where feasible. Section 1.1) to assess its performance on TTP
and UTTP. Tables 4 and 5 present a summary
of the results. The Best k column lists the best-
3.2.5. The mutation process 2,12
known results for each benchmark, while the
In each iteration of the mutation process, the TTP BBO column reports the maximum, av-
Variable Neighborhood Search (VNS) 41 is em- erage and the minimum values obtained by the
ployed as a local search heuristic to reduce the proposed method within a 5-hour computation
travel cost of the schedule. VNS systematically time. The Gap (TTP BBO/Best k ) column indicates
changes neighborhoods within a local search, in- the difference between the best-known results and
volving operations such as swapping teams, swap- the best solution obtained by our approach.
ping home assignments, and swapping rounds.

4. Experimental results Gap (TTP BBO/Best k ) % = travel cost TTP BBO − Best k
travel cost TTP BBO
4.1. Parameters tuning
× 100 (25)
In our Relaxed Integer Linear Programming
(RILP-TTP) approach (Section 3.1), the variable NBins
Ft (where 1 ≤ Ft < n) denotes the number of AG = X Gap /NBins
teams selected from the input solution. Through i=1 (TTP BBO/Best−k) i
numerical experiments depicted in Figures 5 and (26)
6, we evaluated the impact of Ft on NL 10 , NL 12 ,
NL 14 , and NL 16 instances across various input Table 4 illustrates the performance of our pro-
schedules. The outcomes of these experiments posed approach, TTP BBO, in tackling NL and
illustrate that reducing the number of selected CON instances on TTP. Remarkably, TTP BBO
teams from the input schedule (Ft) results in an achieves optimal solutions for NL 4 and NL 6 ,
enhancement in the resultant travel cost (average as evidenced by Table 4. Furthermore, our
outcomes). This observation aligns with intuition method demonstrates exceptional performance by
since opting for fewer teams allows the ILP solver securing optimal solutions for CON 14 , CON 10 ,
to concentrate on optimizing the remaining por- CON 12 , CON 6 , CON 8 , CON 4 and CON 16 as
tion of the schedule (i.e., the schedule for the re- shown in Table 4. For the other instances, the
maining n − Ft teams). However, it is important gap varies from zero to 4.94. We compute the
to acknowledge that this optimization is accom- Average Gap (AG) using the formula 26, where
panied by increased CPU time. For instance, in Gap (TTP BBO/Best k ) represents the disparity be-
NL 10 , the best Ft value is 3 , which equals n/2−2. tween our approach results, for instance, i and
272