Heuristics for the mirrored traveling tournament problem

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.