Monday, December 28, 2009

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.

1 comment:

  1. I have been searching around and can't seem to find information about when Solver/Planner is expected to be released (non-beta)... do you have any dates set for an official release?

    ReplyDelete