This is an implement of one TTP algorithm in the paper:
Jingyang Zhao, Mingyu Xiao, Chao Xu: Improved Approximation Algorithms for the Traveling Tournament Problem. MFCS 2022: 83:1-83:15
https://drops.dagstuhl.de/opus/volltexte/2022/16881/pdf/LIPIcs-MFCS-2022-83.pdf
We only implement the case: TTP-3 with
The code is written in c/c++ and the source file is a .cpp file.
Since
Phase 1:
The first step of algorithm is to generate a triangle packing with a small weight by using a heuristic method. In fact, our method usually can find the optimal packing on many instances.
① Generate an arbitrary triangle packing;
② We try to switch two vertices in the triangle packing to reduce the weight:
List
According to this order, check each pair
③ After checking all pairs: if there is an improvement, we restart this local search in ②; if there is no improvement after 99 iterations of ②, return the final triangle packing.
Phase 2:
The second step of the algorithm is to construct a schedule according to the triangle packing.
The main idea of the construction is as follows. we take each triangle as a super-team and design super-games between super-teams. Then we extend super-games to normal games between normal teams.
We have three kinds of super-games (SG): normal/left/last. In the paper, we describe one design for each of these super-games. Here we design more.
One design for each normal SG; three different designs for each left SG; and 62 designs for each last SG. //These designs are obtained by using an ILP on 6 teams with some restrictions.
The designs can be found in normal_super_game.txt, left_super_game.txt, and last_super_game.txt.
In extending each SG between super-teams
For each super-team, there are
Phase 3:
Last we do the following local search to switch two super-teams to reduce the weight:
① List
② According to this order, check each pair
③ After checking all pairs: if there is an improvement, we restart this local search in ②; if there is no improvement after 9 iterations of ②, return the final schedule.
Some parameters in the code:
int n: number of teams;
int f_opt: a 0/1 variable indicating the last two heuristic parts;
char *s: filname, e.g. Galaxy.
The information of the output scheudle:
① It is a
② The