Scheduling Football Fixtures

The fixtures for the English football season have just been published (Wednesday 17th June 2009), ready for the kick off in August. Paul Fletcher’s (another blogger) excellent article describes some of the complexities that have to be considered when generating the fixtures.

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.

1. 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?
2. 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.