Page 70 - IJOCTA-15-2

Hybridizing biogeography-based optimization and integer programming for solving the travelling tournament ...
while adhering to constraints such as limiting con- (1) Double Round Robin Constraint
secutive home or away games to a maximum of (DRRT): Each team must play against
three. This problem is classified as NP-hard, every other team twice—once at their own
with its complexity established through a reduc- venue and once at the opponent’s venue.
tion from the 3-satisfiability (3-SAT) problem. 7 Teams participate in one match per day,
This reduction underscores that the problem re- without any breaks, ensuring a game is
mains strongly NP-hard even when the restriction held daily.
on consecutive away games is capped at three. (2) No team is permitted to have more than
Additionally, the Unconstrained Traveling Tour- three consecutive matches at home or
nament Problem (UTTP), which removes con- away.
straints on consecutive home or away games, con- (3) Teams are not permitted to face the same
tinues to pose an NP-hard challenge. 8 opponent in consecutive matches.
TTP presents both theoretical and practical
challenges. It combines elements of the travel- The Unconstrained Traveling Tournament
ing salesman problem with those of tournament Problem (UTTP) is a variation of the TTP
scheduling, creating significant feasibility diffi- that removes constraints two and three. It
culties due to its structured format, along with is often relevant for practical scheduling, espe-
complex optimization issues related to travel dis- cially in low-budget league sports. Let R =
tances. Given this blend of characteristics, TTP (R 1 , R 2 , . . . , R 2(2n−1) ) represent the sequence of
has proven challenging to solve exactly, even for 2(2n − 1) days, from round R 1 to round R 2(2n−1) .
smaller-scale instances; currently, no research has Table 1 illustrates an example of a TTP schedule
achieved optimal solutions for cases exceeding ten when 2n equals 6.
teams. 9–11 A set of complex instances, where re-
searchers have proposed solutions—though the Table 1. Double Round Robin Tournament (DRRT)
(2n=6)
optimal answer often remains unknown—can be
accessed on the TTP webpage. 2,11,12 Conse-
R 1 (t 1 , t 6 ) (t 5 , t 2 ) (t 4 , t 3 ) R 6 (t 6 , t 1 ) (t 2 , t 5 ) (t 3 , t 4 )
quently, TTP is an appealing area for exploration
R 2 (t 2 , t 1 ) (t 3 , t 5 ) (t 4 , t 6 ) R 7 (t 4 , t 5 ) (t 3 , t 1 ) (t 2 , t 6 )
using heuristic and meta-heuristic search tech- R 3 (t 5 , t 1 ) (t 2 , t 4 ) (t 6 , t 3 ) R 8 (t 1 , t 5 ) (t 4 , t 2 ) (t 3 , t 6 )
niques. R 4 (t 1 , t 2 ) (t 5 , t 3 ) (t 6 , t 4 ) R 9 (t 5 , t 4 ) (t 1 , t 3 ) (t 6 , t 2 )
This study addresses the TTP by intro- R 5 (t 5 , t 6 ) (t 1 , t 4 ) (t 2 , t 3 ) R 10 (t 6 , t 5 ) (t 4 , t 1 ) (t 3 , t 2 )
ducing a novel approach that integrates the
The schedule (S) indicates that team t 1 fol-
Biogeography-Based Optimization (BBO) meta-
lows this sequence of games: it competes against
heuristic with algorithms grounded in integer
programming. 13–16 team t 6 at home, t 2 away, t 5 away, t 2 at home, t 4
at home, t 6 away, t 3 away, t 5 at home, t 3 at home,
1.1. The traveling tournament problem and t 4 away. The corresponding circuit for t 1 is
given as: (h 1 , h 2 , h 5 , h 1 , h 6 , h 3 , h 1 , h 4 , h 1 ).
The TTP requires creating a schedule for a double
The travel cost or distance value for team t 1
round-robin tournament that meets certain con-
(dvt(S, t 1 )) is:
straints, while aiming to reduce the total travel
distance for all teams.
The problem is structured as follows: TTP dvt(S, t 1 ) =
consists of 2n teams, T = (t 1 , . . . , t 2n ), with each W(h 1 , h 2 )+W(h 2 , h 5 )+W(h 5 , h 1 )+W(h 1 , h 6 )+
team t i based at a home location h i . Let G(H, E) W(h 6 , h 3 ) + W(h 3 , h 1 ) + W(h 1 , h 4 ) + W(h 4 , h 1 )
represent a complete undirected graph, where the
2n The computed travel cost for the given sched-
vertices H = h ii=1 correspond to team loca-
tions, and E represents the edges between them ule is:
+
2n
A weight function W : E 7→ R assigns a value to X
each edge, with W(h i , h j ) indicating the distance travel cost(S) = dvt(S, t i ) (1)
between the home locations of teams t i and t j . i=1
• Inputs for the TTP: A set of 2n teams, The schedule 2, shown in Table 2 is another
T = (t 1 , t 2 , . . . , t 2n ), and a symmetric presentation of the same DRRT schedule 1 (Ta-
2n × 2n distance matrix, Dis. ble 1). In this representation, the symbol ’-’ in-
• Output: A tournament schedule span- dicates that the team is playing away. For ex-
ning 2(2n−1) days, designed to minimize ample, the table 2 specifies that Team t 1 plays
the total travel distance for all teams, against Team t 6 at home in Round R 1 , while it
while meeting the following requirements: plays away against Team t 2 in Round R 2 .
265