Planning the traveling tournament problem

One of the older examples in Drools Planner is the Traveling Tournament Problem as defined by Trick et al. I haven't improved/optimized on it much in the last couple of years, but recently I made a diagram to explain the problem more clearly:

We need to schedule matches between N teams while respecting the following hard constraints:

• Each team plays twice against every other team: once home and once away.


• Each team has exactly 1 match on each playing day.


• No team must have more than 3 consecutive home or 3 consecutive away matches.


• No repeaters: no 2 consecutive matches of the same 2 opposing teams.

There's only one soft constraint:

• Minimize the total distance traveled by all teams.

This might look like a really easy problem, but even for low N's (12 <= N <= 24) they haven't found (or at least proven) the optimal solution yet. Regularly better solutions are found for the larger N's.

Still, those N's are embarrassingly small compared to real-world planning problems such as examination timetabling (N >= 1000), shift rostering or bin packaging.

Planning the traveling tournament problem