Page 75 - IJOCTA-15-2

M. Khelifa et. al. / IJOCTA, Vol.15, No.2, pp.264-280 (2025)
Constraint (12) ensures that a team does not play By introducing the binary variable t i , we
more than three consecutive away matches, anal- can control which team trips are fixed based on
ogous to the home game restriction in Constraint the input schedule in our Relaxed ILP for the
(11). TTP (RILP-TTP). This approach will allow us
Constraint (13) prevents a team from playing to maintain the fixed scheduling for the select-
against the same opponent in two successive ing Ft teams; while keeping the scheduling for
rounds. Constraints (14) enforce z iik to be equal the remaining teams flexible and subject to op-
to 1 (resp. 0) if team i plays at home (resp. away) timization. In Figure 2, we present an exam-
in round k. For any two teams, i and j, constraints ple with n=6; we fix the schedule of the first
(15) enforce z ijk = x ijk , i.e. team i should be at team (Ft = t 1 ), then employ integer program-
the home city of team j if the former plays away ming methods to optimize the schedule for the
against the latter. remaining five teams(n − Ft): t 2 , t 3 ,t 4 , t 5 and t 6 .
Constraints (16) ensure that team t travels from
the home city of team i to that of team j when 3.2. A combined BBO and integer
it plays in those cities in two consecutive rounds. programming for TTP
Constraint (17) enforce the integrality conditions. The following subsections provide the different
As mentioned previously, the Integer Linear components of BBO applied to TTP, along with
TTP Program (ILP-TTP) fails to solve large TTP the global flowchart of our proposed approach,
instances with 10 or more teams. To overcome TTP BBO Figure 4.
this challenge, we relax the program by fixing the
schedule for a subset of teams, denoted as Ft, 3.2.1. Individual representation
where 1 ≤ Ft < n in a given solution. Then,
apply ILP TTP solver to optimize the remaining In our model, each schedule is treated as a habi-
part of the solution (the schedule of n−Ft teams). tat. The Habitat Suitability Index (HSI) is de-
This involves applying the ILP solver to optimize fined as the total travel distance of the schedule
a partial solution (solution with Ft teams), and (travel cost, see 1). Every habitat is character-
then optimizing the remaining part of the solu- ized by a Suitability Index Variable (SIV), which
tion. To implement this approach, we need to fix in this context corresponds to a set of Ft teams
the schedule for Ft teams in the given solution; we within the schedule.
achieve this by introducing additional constraints
3.2.2. Neighborhood structures utilized
to the ILP of TTP:
Let t i be a binary decision variable that equal We utilized three types of neighborhood struc-
1 if team i is included in the set of Ft whose trips tures:
will be fixed; and 0 otherwise; where i ranges from • Swap Round (S, R i , R j ):This operation
1 to n. exchanges all matches between the spec-
Additional constraints: To relax and fix ified rounds (R i , R j ) within the schedule
the scheduling for Ft teams based on the input S.
schedule: • Swap Home (S, t i , t j ): This move reverses
the home/away roles of teams. Specifi-
cally, if team t i is scheduled to play at
(1) Select Ft teams to be fixed: home against team t j in round R k and

n play away in round R l , applying Swap
X
t i = Ft (18) Home (S, t i , t j ) results in team t i play-
ing away in R k and at home in R l , while
i=1
(2) For each team i and j where t i and t j are leaving the remainder of schedule S un-
changed.
both set to 1, set the corresponding x ijk
variable to 1 to indicate that these teams • Swap Team (S, t i , t j ): This operation
will play against each other in all rounds: swaps all opponents of a specified pair of
teams (t i , t j ) across every round.
x ijk = 1 for all k (19)
(3) Ensure that all other x ijk variables for 3.2.3. The initial population, calculating HSI,
pairs of teams where either t i or t j is 0 λ and µ:
are set to 0 for all rounds:
The expression distance hamming(Neigh(S), S)
For all pairs i and j where t i and t j is 0;
refers to the Hamming distance that measures the
ensure;
difference between the schedule S and its neigh-
x ijk = 0 for all k (20) boring schedule Neigh(S). This metric measures
270