Randomized Construction Approaches for the Traveling Tournament Problem using Lower Bound Based Heuristics

Abstract

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%.