Limites para o problema do torneio com viagens

Abstract

The traveling tournament problem (TTP) is a important problem in sports scheduling. Given n teams and the distances between the team’s venues, the TTP consists in finding a tournament with 2(n − 1) rounds where each team must play n − 1 rounds at his home venue and must travel to each of its rivals venues in the other n − 1 rounds. The distance traveled by all teams must be minimum. This work consists on a column generation algorithm to the TTP and as original contributions two pricing algorithms are proposed. These algorithms are adapted from the capacitated vehicle routing problem (CVRP). Two stabilization techniques for column generation were also implemented: one based on the idea of stability box and the other uses convex combinations of the obtained dual solutions. Finally, a pricing heuristic and an ILS metaheuristic were proposed. The new pricing algorithms proposed allowed running the column generation for instances with size up to n = 24 teams. The lower bounds found were weaker compared to those previously known, but were obtained more quickly.