An extension to the Travelling Tournament Problem

[RobS]

Hi People,

Firstly, I'm new to AI and may get some terminology wrong here so please bear with me.

I've written (well, followed an algorithm description really) a solution to the Travelling Tournament problem using a simulated annealing algorithm.
This works well for producing a balanced Round-robin schema with an acceptable number of breaks.

However, as a pool player it occured to me that there was a situation not covered by the standard algorithm. That is, coping with two teams playing out of the same venue (or on the same pool table, in the case of the pool league).

In this situation I have to ensure that when one team is playing at home, its sister team is playing away. The problem is further exacerbated by the fact that one team may play in division 1 while the other team plays in division 2. Imagine further, if you will, that there's a third division, 2 more teams playing out of the same venue and that one plays in division 3 and the other in division 2.

So we now have division 2 containing 2 teams that must play away while their sister team plays at home.

My algorithm starts with a feasible schedule, generated programatically, and moves from one feasible schedule to the next until an optimum solution is found. However, with this new rule, I'm having trouble generating a feasible schedule to start with (I've been testing with 2 divisions of 4 teams and half of each division twinned with half the other division).

Is there anyone out there who's addressed this problem and can point me in the right direction?

Cheers
Rob

PS. If you need more details, just post here and I'll provide them.

[Jare]

I have no idea about pool leagues, but in football (soccer for americans) leagues usually have each team play each other twice, one at home one away.

Generate the matchups randomly for the first weekend. For each team playing at home, check if its sister team plays away, and switch the sister team's matchup so they do. Generate the next weekend. Rinse and repeat. There's probably a number of adjustments you need to make to even out the spread of home / away games for each team, but gut feeling tells me this is separate from the sister team issue.

I don't think you can do this for 3 teams sharing the same venue, since all teams must play 50% of games at home.

All in all I think I have completely misunderstood your problem, or that I just lack data. Or maybe my approach just doesn't work... Never hurts to try thou.

[RobS]

Cheers for the response Jare,

You've not misunderstood the problem. However, you've gone along a route I've already looked at and there are certain situations when this doesn't work. Namely, that by ensuring that one pair of teams always have opposite games, it's possible to break the rule for another pair of teams. In order to resolve this you need to swap the home away flag for that other team which may break another pairing, triggering another swap, etc.

This in itself isn't a huge problem since you can just go round swapping the Home/Away flag until a valid schema is achieved for all.

Sadly though it's not as simple as that since it's possible to get stuck in a circular loop if the original pair is changed again. The reason why this may happen is that depending on the arrangement of the teams in the schema, it's not always possible to produce a valid schema. Therefore, not only to the home/away flags need to be checked, but the team arrangement as well.

It's possible to do, but so inefficient as to render the algorithm useless for anything more than about 12 teams (4 in each division).

Cheers
Rob

[Jare]

Ah, you are right, the damned non-repairable partial solutions... :)

I don't know, apparently Genetic Algorithms are a popular approach to scheduling problems with arbitrary constraints. I don't have much experience in either field.

[RobS]

Cheers Jare, I'll google GA's to see if I can come up with anything. I suspect though that I'll have to learn the basics and then apply my new-found knowledge. Looks like no spoon-fed answers for me :wallbash:

Rob