A Matching-Based Algorithm for the Traveling Tournament Problem
Authors: Jingyang Zhao, Mingyu Xiao
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In practice, our experimental results indicate an average improvement of 6.65% over the best-known solutions on 9 benchmark instances. |
| Researcher Affiliation | Academia | Jingyang Zhao, Mingyu Xiao* University of Electronic Science and Technology of China EMAIL, EMAIL |
| Pseudocode | Yes | Algorithm 1: Randomized Labeling of Teams |
| Open Source Code | Yes | Our code is available at https://github.com/Jingyang Zhao/TTP-4. |
| Open Datasets | Yes | For TTP-4, the current best-known experimental results are from Westphal and Noparlik (2014), where they tested 30 benchmark instances from the online website (Trick 2024). Among these, nine instances satisfy n 0 (mod 8). ... Trick, M. 2024. Challenge traveling tournament instances. https://mat.tepper.cmu.edu/TOURN/. Accessed: 2024-0815. |
| Dataset Splits | No | The paper uses existing benchmark instances but does not describe any specific training/test/validation splits for these instances, as the problem is more about combinatorial optimization and algorithm performance rather than machine learning model training. |
| Hardware Specification | Yes | Our algorithm is implemented in C++ and executed on a standard Windows desktop computer with an Intel Core i5-11400 CPU (2.6 GHz) and 16 GB of RAM. |
| Software Dependencies | No | The paper states, "Our algorithm is implemented in C++", but does not specify any particular version of C++ or any other software libraries or their versions used in the implementation. |
| Experiment Setup | Yes | First, we use two minor modifications of the construction. We replace the left super-game Sm Sm 1 in the first time slot with a normal super-game Sm Sm 1. After Sm plays an away last super-game in the last time slot, instead of calling a TTP-2 algorithm, we assign an away self-game for it, as we do for other super-teams. So, any last super-game, along with the two subsequent selfgames, can be regarded together as a new last super-game. Second, we optimize our super-games as follows: during the extension of each super-game between any pair of superteams Si and Sj, we relabel the teams in Si and Sj to minimize the total traveling distance for all teams in Si Sj on the extended days. There are 4! 4! = 576 possible ways to relabel the teams, and we will choose the best way. Last, instead of using the randomized labeling algorithm, we form m super-teams as follows: (1) We obtain a new graph G by contracting each edge in M into a vertex, where the weight between vertices corresponding to edges xy M and zt M is defined as min{w(x, z) + w(y, t), w(x, t) + w(y, z)}. (2) We then find a minimum weight matching M in G , which pairs the 2m edges in M into m pairs of edges. (3) Finally, we take the four teams from each pair of edges in M to form a super-team. ... After forming m super-teams, we attempt to swap the indices of two super-teams to find better solutions. Specifically, there are m 2 possible pairs of super-teams. We consider these pairs in a random order. For each pair, from the first to the last, we test whether swapping the indices of the super-teams results in a better schedule. If not, we do not swap them and move on to the next pair. If it does result in a better schedule, we swap them and proceed to the next pair. After evaluating all m 2 pairs, if an improvement is found, we repeat the procedure. Otherwise, the process concludes. |