Title: Randomized Construction Approaches for the Traveling Tournament Problem using Lower Bound Based Heuristics
Language: English
Authors: Pace, Giulio 
Qualification level: Diploma
Advisor: Raidl, Günther 
Assisting Advisor: Frohner, Nikolaus 
Issue Date: 2021
Number of Pages: 81
Qualification level: Diploma
The traveling tournament problem (TTP) is an N P-hard combinatorial optimization problem famous for its practical hardness. The goal is to construct a double round robin sports league schedule for a certain number of teams, minimizing the sum of the total traveled distance over all teams. Each team starts and ends the season at their home venue and, when playing two away opponents in a row, will travel directly from the first venue to the second. There is a limit on the number of consecutive home and away games that a team is allowed to play and two opponents cannot face each other in two consecutive rounds. As of today, from the standard benchmark sets only instances up toten teams have been solved to optimality, those with 12 have not. The goal of this work is to study the behavior and augment constructive approaches withguidance by independent lower bound based heuristics formulated as capacitated vehicle routing problems (CVRPs). Building upon a state-space formulation for the TTP, we propose a MAX -MIN ant system algorithm, based on a successful application in the literature. Furthermore, we extend a randomized beam search approach to be able to tackle instances up to 26 teams by calculating the guidance heuristics approximately using Google OR-Tools.T he effects of numerous algorithmic parameters (e.g., using a restricted candidate list during construction, varying the beam width for beam search) when solving the CVRPs and the TTP itself are presented in a detailed computational study. Sensible choices of parameters are performed by manual tuning and further strengthened by automated parameter tuning. A final comparison is performed on the NL, NFL, galaxy, CIRC and Super benchmark instances up to 26 teams. Our ant colony optimization approach generally presents differences to the relative gaps of the best known solutions of around 11%, which leads us to conclude that a hybridization with a local search based method is necessary to reach competitive results. The beam search approach profits much more from the heuristic guidance and shows relative gap differences to state-of-the-art approaches not higher than 6% and in the mean of only 2.7%.
Keywords: Traveling Tournament Problem; Independent Lower Bound; Capacitated Vehicle Route Problem; Heuristic Optimization; Ant Colony Optimization; Beam Search
URI: https://doi.org/10.34726/hss.2021.87881
DOI: 10.34726/hss.2021.87881
Library ID: AC16217827
Organisation: E192 - Institut für Logic and Computation 
Publication Type: Thesis
Appears in Collections:Thesis

Files in this item:

Show full item record

Page view(s)

checked on Jun 20, 2021


checked on Jun 20, 2021

Google ScholarTM


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.