Football Fixture Scheduling: Are all clashes equal?

In a paper published in JORS:

• Kendall G. (2008) Scheduling English Football Fixtures Over Holiday Periods. Journal of the Operational Research Society, 59(6), pages 743-755 (doi:10.1057/palgrave.jors.2602382)

I investigated if it was possible to produce superior fixtures for the Christmas/New Year Period with respect to minimising the distance that is traveled by supporters on two particular days.

One of the issues that the underlying model had to capture was that certain teams could not play at home on the same day. For example:

• Manchester United and Manchester City
• Liverpool, Everton and Tranmere
• Chelsea and Fulham
• Colchester, Ipswich and Norwich
  
• etc.

Teams that are paired in this way are called pairs (even though there might be more than two teams involved). A problem arises as it is not possible to eliminate all the pair clashes. That is, some paired teams have to play at home on the same day.

In the JORS paper, all the pair clashes were treated equally (e.g. Manchester United and Manchester City playing at home on the same day is not considered any more, or any less, important than Liverpool and Tranmere playing at home on the same day).

I am not sure if any given pair clash should be considered more (or less) important than any other, but I suspect so.

One of the things I plan to do is analyse the past few seasons fixtures and gauge if certain pair clashes are allowed more than others. Then I will use this evidence to weight the clashes during the process of searching for a good set of fixtures.

General Algebraic Modeling System (GAMS)

Yesterday (5th July 2009) I attended a workshop run by GAMS (run as part of the EURO 2009 conference - see previous post). They provide a piece of software called GAMS (General Algebraic Modeling System: http://www.gams.com) which enables an easy way to develop mathematical models and then solve them by calling various solvers (such as CPLEX, COIN-OR etc.).

I had heard of GAMS before, but had never really looked into it, played with it or talked to anybody who had used it.

I realise that the workshop was really a sales pitch but from what I saw it was very good.

You can download the software and try it (on small models) and this is something that I will be doing in the next couple of weeks. I'll report how I get on.

EURO 2009 Conference

I am at the EURO conference at the moment (see http://www.euro-2009.de) (the picture was taken during the opening ceremony).

This is an annual conference for the European Operational Research Societies. This year it has attracted around 2000 delegates, which was a lot more than we had expected (I know as I am on the main Program Committee and have been actively involved in planning and organising the conference, although I have not worked anything like as hard as some people I could mention - but won't mention them by name for fear of embarassing them).

As the conference progresses I'lll report on anything that grabs my interest/attention.

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.

Operational or Operations Research?

Some of my research is carried out in the area of Operations Research. This term is actually the American version. The English version is Operational Research and (although being biased), I believe that this is the correct version, bearing in mind that Operational Research was founded in England (around the time of the Second World War).

You will find the distinction between these two terms no more apparent than in the naming of academic journals. The oldest OR journal in the world is called Journal of the Operational Research Society (JORS). Another journal is called European Journal of Operational Research (EJOR) .
The journals published in America have titles such as Operations Research.

Welcome

Welcome to my blog.

Through this blog I'd like to discuss areas that are related to my research interests.

I will post on an irregular basis as, I am guessing, that there will be more important things to do on many days but I hope to post regularly enough to make it worth visiting every so often.