Heuristics for the mirrored traveling tournament problem

Celso Ribeiro (celsoinf.puc-rio.br)
Sebastián Urrutia (usebainf.puc-rio.br)

Abstract: Professional sports leagues are a major economic activity around the world. Teams and leagues do not want to waste their investments in players and structure in consequence of poor schedules of games.Game scheduling is a difficult task, involving several decision makers, different types of constraints, and multiple objectives to optimize. The Traveling Tournament Problem abstracts certain types of sport timetabling issues, where the objective is to minimize the total distance traveled by the teams. In this work, we tackle the mirrored version of this problem. We first propose a fast and effective constructive algorithm. We also describe a new heuristic based on the combination of the GRASP and Iterated Local Search metaheuristics. A strong neighborhood based on ejection chains is also proposed and leads to significant improvements in solution quality. Very good solutions are obtained for the mirrored problem, sometimes even better than those found by other approximate algorithms for the less constrained non-mirrored version. Computational results are shown for benchmark problems and for a large instance associated with the main division of the 2003 edition of the Brazilian soccer championship, involving 24 teams.

Keywords: Traveling tournament problem, timetabling, heuristics, sports, iterated local search

Category 1: Applications -- OR and Management Sciences (Scheduling )

Category 2: Combinatorial Optimization (Meta Heuristics )

Citation: Research report, Catholic University of Rio de Janeiro, Department of Computer Science, March 2004.

Download: [Postscript]

Entry Submitted: 04/05/2004
Entry Accepted: 04/05/2004
Entry Last Modified: 04/05/2004

Modify/Update this entry