Round Robin Tournament Scheduling

Partial Schedule Played, complete it

Rourke · 2 · 99

Rourke

  • Newbie
  • *
    • Posts: 1
on: July 02, 2020, 08:49:29 PM
Just stumbled on this board, thanks for putting it together! I've always had an interest in tournament scheduling, and have been able to put it into practice several times.

We've had a situation in our national league where due to coronavirus a big slab of the season went missing after a few rounds had been played. The original schedule was not a perfect double round-robin. The organisers want to complete it with a single round-robin, given the shortened time. They also have a few key matches that must be played on a certain date (Locked).

I managed to develop an algorithm that seems to work, something like simulated annealing. Sharing it here for feedback, and to see if anyone can point me to similar published work:


  • For each remaining round, generate a random permutation of the teams that are not involved in a Locked match, and put them in pairs of teams
  • Count how many times each team plays each other in the full fixture
  • While there are team pair counts that are zero:
    • Randomly choose a pair A:B with count more than one (overplayed)
    • Randomly choose one of their non-Locked matches
    • Find another overplayed match in the same round; if there are none, choose any match X:Y in the round
    • Decide whether A:X & B:Y or A:Y & B:X would be the better replacement by testing the overplayed count; if equal, flip a coin
    • Make the swap
    • Update the team pair counts
This seems to steadily move the overplayed count down, with random walks where it gets larger for a while. I'm yet to see it fail, but that would assuredly happen if enough of the fixture was already Locked.

It also works if you want to allow byes, just by adding an extra round, running the algorithm, then removing some of the overplayed matches at the end.

You can then balance the home & away counts with a similar stochastic process.


« Last Edit: July 02, 2020, 08:54:05 PM by Rourke »


Ian Wakeling

  • Forum Moderator
  • God Member
  • *****
    • Posts: 1131
Reply #1 on: July 06, 2020, 08:29:54 AM
Thanks for posting your algorithm.  I don't have any specific literature to point to, but I know that the operations research people (I am not one of them) have studied these sorts of sports scheduling problems.  Common methods for finding solutions are constraint programming, integer programming and perhaps genetic algorithms.

It seems that your approach is working well, and I think this is because the random element prevents it becoming trapped at local optima.  There is probably an alternative approach where the matches are first fixed, and then the non-locked ones are moved around the schedule with the aim of having no repeated teams in a round.