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. 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?

  2. This is Very very nice article. Everyone should read. Thanks for sharing. car insurance online - online travel insurance

  3. This comment has been removed by the author.

  4. Thanks for the information you provided here. The article is superb. I was looking for it for a long time. Thank you... Limo Service Dubai | cheap car rental with driver in Dubai

  5. Pretty nice post. I just stumbled upon your weblog and wanted to say that I have really enjoyed browsing your blog posts. Limo Service Dubai ~ cheap car rental with driver in Dubai

  6. I got too much interesting stuff on your blog. I guess I am not the only one having all the enjoyment here! Keep up the good work. Car Rental with Driver in Dubai & Limousine Service Dubai

  7. I got such a nice information from your blog.