The Traveling Tournament Problem

Consider the following problem, known as the Traveling Tournament Problem (TTP). There are n teams playing a so-called Double Round Robin tournament. This means that each pair of teams meet each other twice, once in the home venue of one team, and once in the home venue of the other team; there are 2n-2 rounds, and in each round each team plays once. Each team begins the tournament at its home venue and must return to its home venue at the end of the tournament. When a team plays an away game, it must travel directly from the site of its previous game to the site of its next game. The problem is to find a playing schedule such that total travel is minimized.

This problem is motivated by the Major League Baseball in the United States; the problem has been introduced by Easton et al. (2001). Additional constraints that are relevant in practice are:

*) two teams that play each other in round t should not play each other in round t + 1,

*) no team will play more than three consecutive home or three consecutive away games.

A key reference is:

Easton, K., Nemhauser, G., & Trick, M. A. (2001). The travelling tournament problem: Description and benchmarks. In T. Walsh (Ed.), Principles and practice of constraint programming (Lecture notes in computer science) (Vol. 2239, pp. 580–585). Berlin: Springer.

Goals of the bachelor project:

*) Find scientific literature on this subject, and related problems

*) Design mathematical programming models for this problem

*) Solve instances of this problem