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
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
Is there anyone out there who’s addressed this problem and can point me
in the right direction?
PS. If you need more details, just post here and I’ll provide them.
Please log in or register to post a reply.
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.
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
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).
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.
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: