Page 71 - IJOCTA-15-2

M. Khelifa et. al. / IJOCTA, Vol.15, No.2, pp.264-280 (2025)
Table 2. Another DRRT presentation (2n=6) was developed in. 9 This method successfully
achieved optimal solutions for instances like NL8
R 1 R 2 R 3 R 4 R 5 R 6 R 7 R 8 R 9 R 10 and CIRC6.
6 -2 -5 2 4 -6 -3 5 3 -4
t 1
-5 1 4 -1 3 5 6 -4 -6 -3
t 2 For larger instances of the TTP, metaheuris-
-4 5 -6 -5 -2 4 1 6 -1 2
t 3
tic approaches have shown significant success.
3 6 -2 -6 -1 -3 5 2 -5 1
t 4
2 -3 1 3 6 -2 -4 -1 4 6 Among these, methods such as the genetic al-
t 5 24
-1 -4 3 4 -5 1 -2 -3 2 5 gorithm (GA), variable neighborhood search
t 6
(VNS), 25 and the clustering search (CSA) tech-
All problem instances can be found in. 2,11,12 nique applied to the mirrored TTP (mTTP) 26
There are two types of instances: ones with arti- have proven effective. 27 proposed a hybrid tech-
ficially generated distances and others with real- nique that blends the Greedy Randomized Adap-
world distances: The real instances are: tive Search Procedure (GRASP) with Iterated Lo-
cal Search (ILS) to tackle the mTTP. The method
• NL n : Represents the US National League demonstrated superior performance on NL and
of Professional Baseball Clubs, with n CIRC instances compared to previous studies.
being an even number of participating Additionally, 22 introduced an innovative strat-
teams. egy for the mTTP, combining enhanced harmony
• Super n : Refers to a Rugby League that search with variable neighborhood search (V-HS),
includes teams from New Zealand, Aus- showing optimal solutions on NL6, CON4, and
tralia, and South Africa. CON8 instances when tested on NL benchmarks
• NFL n : Denotes the National Football (up to 16 teams) and CON benchmarks (up to
League and the Brazilian Soccer Cham- 20 teams). Furthermore, 28 employed ILS to ad-
pionship. dress the TTP with Predefined Venues (TTPPV),
achieving improved results for the CIRC 20 and
The artificial instances are:
CIRC 18 instances.
• CON n : Refers to instances where all
team-to-team distances are constant and
This work 29 addresses the TTP by propos-
equal to one (1).
ing a novel game-permutation encoding and tack-
• CIRC n : Represents instances with teams
ling it as a bi-objective problem to minimize both
arranged in a circular layout, where adja-
constraint violations and travel length. Using
cent nodes have a distance of one (1). The
NSGA-II (Non-dominated Sorting Genetic Algo-
distance between any two teams i and j
rithm II) and a lexicographic Randomized Local
(for i > j) is determined as the minimum
Search (RLS), the study demonstrates that RLS
of i − j and j − i + n, representing the
reliably finds feasible schedules for up to 36 teams
shortest path.
and outperforms NSGA-II and FRLS on larger
The NL n instance family is the most com- problems.
monly studied, with the majority of TTP research
papers reporting computational results on these Several approximation algorithms have also
instances. 4,17,18 30
been developed for the TTP. In, an algorithm
was proposed that achieves an approximation
1.2. Previous work
within a factor of 5.875 of the optimal solu-
TTP has been widely examined in the optimiza- tion. For the UTTP, 31 applied methods such
tion field. Several studies 4,5,19–22 have investi- as the circle technique and the shortest Hamil-
gated the TTP across different contexts, focusing tonian cycle to produce effective results. In
32
on methods like constraint programming , integer this work , the authors proposed an approxi-
programming, and hybrid techniques. mate algorithm for solving TTP-2 with up to
In, 23 the authors, present an integer pro- 32 teams, achieving a better approximation fac-
gramming model targeting the mTTP and Max- tor than the existing best result by. 33 Lately, 21
MinTTP variants, with an emphasis on reduc- proposed a unique graph-based heuristic for the
ing the longest distance traveled. While their UTTP, which showed promising outcomes for in-
methodology was applied to smaller instances in- stances with fewer than 10 teams. In, 20 an in-
volving up to 10 teams, it demonstrated encour- novative evolutionary algorithm was introduced,
aging outcomes. integrating a new constructive heuristic to design
Furthermore, an exact approach for solving double round-robin tournament (DRRT) sched-
the TTP, utilizing a Branch-and-Price method, ules that minimize travel costs.
266