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.
