Page 74 - IJOCTA-15-2

Hybridizing biogeography-based optimization and integer programming for solving the travelling tournament ...
Algorithm 1 Migration process: from team i to team j anywhere in the schedule.
n
n
1: for i=1:number habitats do X X
2: Select a habitat Habitat iwith probability αλ i Minimize d ij x ij1 + d ij y tij
3: if H i is selected then i,j=1 t,i,j=1
4: if rand ∈ (0, 1) < λ i then n (7)
5: Select Habitat j with probability αµ j + X
6: if H j is selected then d ji x ij,2n−2
7: Habitat i(SIV ) ← Habitat j(SIV ) i,j=1
8: end if Subject to constraints:
9: end if
10: end if
11: end for x ii = 0(i = 1, ..., 2n − 2) (8)
n
X
(x ijk + x jik ) = 1(i = 1, ..., n, k = 1, ...2n − 2)
j=1
1 − P sp
Pmut(sp) = α (4) (5) (9)
P max
2n−2
Where: X
x ijk = 1(i, j = 1, ..., n, i ̸= j) (10)
• P mut (sp): Mutation rate for a habitat k=1
with sp species. 3 n
X X
• α: User-defined parameter. x ij,k+l ⩽ 3(i = 1, ..., n, k = 1, ..., 2n − 2 − 3)
• P sp : Probability of having sp species in l=0 j=1
the habitat. (11)
• P max : Probability of having the maximum 3 n
number of species (i.e., max P S ). X X x ij,k+l ⩽ 3(j = 1, ..., n, k = 1, ..., 2n − 2 − 3)
• P sp : Probability of the presence of sp l=0 i=1
species in the habitat. (12)
x ijk + x jik + x ijk+1 + x jik+1 ≤ 1,

λ 0 λ 1 ...λ sp−1 , (i, j = 1, . . . , n, k = 1, . . . , 2n − 3) (13)


n P λ λ ...λ
 0 1 l−1
 µ 1 µ 2 ...µ sp 1+ n

1 2
 µ µ ...µ l X
l=1
 z iik = x ijk (i = 1, ..., n, k = 1, ..., 2n − 2)
P sp = 1 ≤ sp ≤ number habitats j=1
1

 , sp = 0 (14)

 n P λ λ ...λ
 0 1 l−1
 1+ z ijk = x ijk (i, j = 1, ..., n, i ̸= j, k = 1, .., 2n − 2)
µ µ ...µ l
1 2
l=1
(6) (15)
y tij ⩾ z tik + z tj,k+1 − 1,
Algorithm 2 Mutation Algorithm : (t, i, j = 1, . . . , n, k = 1, . . . , 2n − 3) (16)
1: for j = 1 to number habitats do x ijk , z ijk , y tij ∈ {0, 1},
2: Use λ i and µ i to compute Pmut i
(t, i, j = 1, . . . , n, k = 1, . . . , 2n − 2) (17)
3: Select Habitat i(j) with probability αPmut i
4: if Habitat i(j) is selected then Where:
5: Replace Habitat i(j) with a random SIV • d ij represents some distance or weight be-
6: end if
7: end for tween teams i and j.
The goal of the objective function (7) is to reduce
the overall travel distance throughout the tourna-
3. The proposed approach ment represented by the sum of distances d ij , d ji
and d ij over the variables x ij1 , y tij and x ij,2n−2 .
3.1. Integer programing for TTP
Constraints (8) ensures that a team does not play
In our proposed approach, we utilize a simple and against itself during the tournament.
directed Integer Programming formulation varia- Constraints (9) guarantees that each team i plays
3
3
tion of the TTP, employing O(n ) variables. The exactly one match in each round k either at home
binary decision variables of this model are: or away.
x i,j,k (i, j = 1, ..., n, k = 1, ..., 2n − 2): represents Constraints (10) every team i plays away against
the decision if team i plays away against team j every other team j exactly once.
on round k, Constraints (11) ensures that a team does not
y t,i,j (t, i, j = 1, ..., n): denotes that team t travels play more than three successive home matches.
269