My research has focused on scheduling the fixtures over the Christmas/New Year period. On Boxing Day and New Years Day every team has to play. If a team plays at home on Boxing Day, they must play away on New Years Day (and vice versa), but they are not allowed to play a reverse fixture (for example, if Chelsea play Liverpool on Boxing Day, Liverpool cannot play Chelsea on New Years Day). There are also other factors which have to be considered (such as the number of fixtures that can take place in London etc.)
One of the most important aspects for the fixtures on Boxing Day and New Years Day fixture is to reduce the amount of traveling for the supporters. If you look at these fixtures for (at least) the past seven seasons you will see that these two days have the lowest travel distances when compared to other dates when all the teams play.
This was the focus of a paper I published in Journal of the Operational Research Society (you can access the paper here, or from the journal itself). The paper shows that it is possible to produce a set of fixtures which involves less travel than the fixtures that were actually used.
There are a couple of caveats.
- I have tried to make sure that I have captured all the aspects of the real world problem, but I cannot be totally sure. For example, I consider all pair clashes (see the paper if you are interested in what a pair clash is) as being equal. Perhaps, some should be avoided more than others?
- There are some seasons (typically World Cup years) where, over the Christmas and New Year period, every team has to play four matches and they must be sequenced Home, Away, Home, Away (or Away, Home, Away, Home). This makes the scheduling problem a lot more difficult, especially when you still attempting to minimise the travel distances. I still need to address this aspect of the problem.
The paper referred to above only considers four seasons. I have other work in progress which not only uses seven seasons of data but also uses more sophisticated search techniques. Not only am I able to significantly speed up the search (from about 30 hours to a matter of minutes) but I also managed to improve on the results reported in the JORS paper. I'll report more if/when the paper is published.
In the meantime, my attention is turning towards the 2009-2010 season. One of the biggest tasks each year is to collect the data representing distances between each football club. For the past seven years I have used http://www.greenflag.com. It is a time consuming task as I have to manually collect the data for each pair of teams. This year I am looking at exploiting google maps. They have an API (Application Programming Interface) which I hope will enable me to automate this data collection task. I will report on the success (or failure) of this approach soon.
5 comments:
This looks a lot the traveling tournament problem (TTP). My drools-solver (open source) includes the TTP as an example.
The "every team has to play four matches and they must be sequenced Home, Away, Home, Away (or Away, Home, Away, Home)" could be implemented in several rules like this in drools-solver:
rule "homeBoxingDayMustBeAwayNewYearsDay"
when
$boxingDay : Day(boxingDay == true);
$newYearsDay : Day(newYearsDay == true);
$m : Match($homeTeam : homeTeam, day == $boxingDay);
Match(homeTeam == $homeTeam, day == $newYearsDay);
then
insertLogical(new UnweightedConstraintOccurrence("homeBoxingDayMustBeAwayNewYearsDay", $m));
end
I forgot a shameless plug to the drools-solver blog. :)
Thans for the comment. I'll take alook at your solver.
The UK football fixture scheduling does similarities to TSP and TTP but it is not the same.
Unlike the TTP, UK football teams do not go on road trips and it is not like the TSP as, over the course of the year, each team will have to cover the same distance, no matter what order the fixtures are played in. Also, the fixtures are not carried out as a cycle.
I have added a link from your blog (drools-solver blog) to this blog (see my side panel).
Thanks :)
The drools-solver blog is a filter on the drools blog. I'll ask the drools project lead about linking back and the policy on it. Drools-solver is a small, community-driven subproject of the big, jboss-driven drools project.
Post a Comment