Help on constrained round robin

[speedwago]

Hi, I've the following problem:
I've implementented a round robin algorithm using the Cyclic algorithm. Unfortunaly I also have a pair oh containt. The first one is that every team cannot play more than 2 matches in a row in home or away. I've resolved this simply by "switching" the two column for home and away team at each iteration.
The second constraint is more complex and I cannot resolve it.
My scheduling is on 20 teams but 4 of the sharing the same stadium, so 2 teams that share the same stadium cannot play at home. Since the schedule is mirrored , the two teams cannot also play away the same time (since in the mirrored second half they will be play at home at the same time).
So I try to do the following: When there is a conflict flip the home/away order of one od the two matches (at random choose), keep doing this until there are no conflict.
It seems to work but my home/away contraint are not respected! now I've teams that pla 4 time home in a row!
I tried to choose to flip the team witch less home in a row matches intead of made a random choice, but it seems to give  an unfeasable solution (a new conflict is always found) and the algotithm loop forever.

Any suggestion?

[Ian Wakeling]

If 4 teams share the same stadium then it must surely be the case that you play two matches per round at that stadium?  The  Excel generator program here will solve most of this problem for you, if you turn off the randomization feature and use the home/away option then you should find that A and B form complementary pairs of teams (when A is home, B is away), teams C and D are also complementary - so these could be the 4 teams at the same stadium, all you need to do is schedule two different starting times for the two home matches among A,B,C & D.  Notice that most teams have one sequence of two home or two aways games in a row, I don't believe it is possible to do any better than this, so perhaps this is why your current algorithm is not working.

PS: A, B, E & F may be a better choice than A, B, C & D since they never all play each other in the same round.

[speedwago]

I'm sorry my explanation was a little confusing.

The exact problemi is that 4 COUPLE of teams share the same stadium (so team A share the statiom with TramB , C with D and so on).

Thank you for your reply, I'll see if that excel sheet solves the problem!

[Richard A. DeVenezias]

Posted on behalf of Warren Porter

Rnd                 Pairings
 1:  1-20 11-10 19-2  12-9  18-3  13-8  17-4  14-7 16-5 15-6
 2: 20-11  2-1  10-12  3-19  9-13  4-18  8-14  5-17 7-15 6-16
     .......
 

The above is from my RR Table when Porter and Board Order are chosen with 20 players.  

The team on the left is home, like 12 plays at 10 in the 2nd round.  It was created like
this in that sequential numbers were "seated" in every other position counterclockwise going around the long "table" twice.  Between rounds the ribbon moves one position clockwise except player 20 always stays put.  At any rate players (teams) next to each other on the moving ribbon will not be both home or away until they play team 20.  For example (10 19) (9 18) (8 17) (7 16) is one way to assign pairing numbers to teams who share a stadium and would cause your scheduling problems to occur late in the season.  A grouping of (2 12) (4 14) (6 15) (7 17) would spread your possible conflicts over the season.

You would have only one "doubleheader" per round and then just four times in a season (or 1st half of a season since you do a double round robin).  Teams 11-19 would be home against 20 (in the 1st half).

Good luck!

[wbport]

I'm having trouble posting a more detailed reply, but found you won't have any problem with four pairs of teams sharing facilities if you can select pairs of teams on the "ribbon" where the team with the higher pairing number is leading the way around the ribbon.  For example (16 7) or (13 4) or (17 8) or (11 2) should all work.

If you look at my table (in the link), look at the order of 20's opponents to get suggested pairings (1st column) .  You can observe how paired pairing numbers interact with no 20 by looking at the first two columns in consecutive rounds.
--------------------------------------------- The following is what I tried to post earlier-------------

After some more thinking on this, I think I have a better solution.  To see how a round robin works, visit here.  To make it applicable to team events, substitute team for player, White and Black become Home and Away. Substitute Week for Round.  The "Board Number" shows where players, er, teams, meet other teams a given number of positions ahead or behind them on a "ribbon", except on "Board 1" where the team with the highest even number does not move and and other teams come "there" on the model.

I have shown the first two rounds (weeks) and just the first two boards on all other rounds.  Outside of the first and last week, the teams in the 2nd column (Board 2) have just met team 20 or will meet that team next week.  The order of players on the ribbon is the same as the order as 20's opponents.  When not playing 20, no adjacent teams on the ribbon can both be home or away the same week;  it is only when they meet 20 is there a potential problem. The full table is here, choose Porter, Board Order, and 20, perhaps checking Double Round Robin as well.

In this table, the first named team is Home and Teams 1-10 will be home against 20 while 11-19 will be away against 20.  To make this work, the team with the higher pairing number must be in the lead, e.g., 13 and 4.  In week 6, 13 plays at 20 while 4 hosts team 3.  In week 7, 4 hosts team 20 while 13 plays at 14.  Other pairs which would work are 15:6 or 17:8 or 19:10.  Hope this helps!

19 or 20 players
Rd                                         Pairings
 1:   1-20  11-10  19-2   12-9   18-3   13-8   17-4   14-7   16-5   15-6  
 2:  20-11   2-1   10-12   3-19   9-13   4-18   8-14   5-17   7-15   6-16 
 3:   2-20  12-11     
 4:  20-12   3-2  
 5:   3-20  13-12   
 6:  20-13   4-3  
 7:   4-20  14-13  
 8:  20-14   5-4  
 9:   5-20  15-14   
10:  20-15   6-5     
11:   6-20  16-15   
12:  20-16   7-6     
13:   7-20  17-16   
14:  20-17   8-7     
15:   8-20  18-17 
16:  20-18   9-8   
17:   9-20  19-18 
18:  20-19  10-9    
19:  10-20   1-19   

[wbport]

After looking at this a little further, it seems each team can be part of a pair of teams which play at the same facilities--never at the same place (home/away) until they play each other.

First of all, team 1 and the "ghost" team (has highest pairing number) is one pair.  Next take the number of teams (assume it's even, assume next higher even number if necessary) divide by 2 and then subtract 1.  That difference when added to or subtracted from any other pairing number will give each team's partner (except for 1 and the ghost).  If there are an odd number of teams, team 1 cannot have a partner.

In the original problem (20 teams), the difference is (20 / 2) - 1 = 9.  The possible pairs are
(1 20) (2 11) (3 12) (4 13) (5 14) (6 15) (7 14) (8 17) (9 16) and (10 19).

This assumes the Porter option in my tables (see earlier post for link).

[wbport]

In the original problem (20 teams), the difference is (20 / 2) - 1 = 9.  The possible pairs are
(1 20) (2 11) (3 12) (4 13) (5 14) (6 15) (7 14) (8 17) (9 16) and (10 19).

That should be (7 16) and (9 18).