Round robin match location algorithm

Question

I'm trying to figure out an algorithm for setting a matches location for a round robin tournament.

Each team plays each other team twice, once at home and once away.
Each team has a home location.
There are many teams in the tournament that share the same home location.

I already have an array of all the matches. A match looks something like:

{
  date: "Thu Jan 08 2015 12:00:00",
  home: "Bob",
  away: "Frank",
  location: null
}

I want to loop through all matches and assign the location. I've tried various solutions but nothing has worked perfectly yet.

Of course, if Bob's home location is available on date we can just use that.
We have to take into consideration the other match in which Bob and Frank play. It's fine to switch home/away teams but we must ensure it is balanced. (i.e. Bob and Frank play at home once each)
If it is impossible to assign a location even after trying to switch home/away, we must then attempt location splits.

Location split

Match locations can be split so that multiple matches are played at the same time at a single location. How we determine if a location can be split is outside the scope of this question but let's just say we have a function called canLocationBeSplit(location) which returns a bool true or false.

Both home or away locations on either match between 2 teams can be split. However, we only want to start splitting locations unless absolutely necessary. Again, each team must play at home once and away once.

If there is still no available location for the match, we just leave it as null.

Question

So my question is, does anybody have any suggestions for a suitable recursive algorithm that would solve this problem? Thanks for your time.

H W H W · Accepted Answer · 2015-04-10T11:48:41

This is not a trivial problem. Since it is not certain that there is any solution at all, it is hard to prove that any solution you might find is optimal in regard to your requirements without using a bruteforce approach and compare it to every single outcome.

An example for a constellation without a solution would be 4 teams which all share a home location that can not be split. The desired solution would be assigning NULL values to some matches and an "optimal" solution would have as few NULL values as possible (so finding an optimal solution is an optimization problem which might even be NP-hard?!).

So I would have two suggestions depending on the amount of teams that you have:

Use bruteforce and calculate all possible combinations of locations. This being said, let's estimate what this means. Let's say you have 20 teams. In the worst case 10 matches are played all on the same date (for example every saturday). Thus for each week (38 different dates) you need to pick 10 locations out of the 20 you have and calculate every permutation of these. This gives you 38*binom(20,10)*10! = 25.476.817.766.400 different combinations which need to be validated (check if your above requirements are met) and then compared to find the most optimal distribution. If you have only 10 teams, this number goes down to only 241.920 possible combinations, which would actually be reasonably small!
Create a reasonable distribution of locations for the first date and iterate over the dates, assigning the locations as optimal as possible without changing the previously set locations. This will most likely not give you an optimal result, and might leave some matches without location, but you get at least a proposed distribution of locations in a small amount of time.

To get the "reasonable" distribution that i spoke of in the second approach, i would suggest determine for each location and each date how many different matches could possibly be played at this location. Then start by assigning the locations with the least possible matches first and repeat until no matches are left.

Example:

Team A - Home Location: 1
Team B - Home Location: 1
Team C - Home Location: 1
Team D - Home Location: 2
Team E - Home Location: 3
Team F - Home Location: 4

Matches at some given date:

Match 1: Team A vs Team D
Match 2: Team B vs Team E
Match 3: Team C vs Team F

If Team A played Team D before at Location 2, we get:

Location 1 could host 3 matches (all matches)
Location 2 could host no matches
Location 3 could host 1 match (Match 2)
Location 4 could host 1 match (Match 3)

Thus we would assign Location 3 to Match 2 and Location 4 to Match 3 which only leaves Location 1 to assign to Match 1.

Like i said, this won't be an optimal solution and might produce some matches without an assigned location, but i hope this produces a good enough result.

Round robin match location algorithm

1 Answers