When the English football fixtures were announced in June, many fans would have studied them from their own perspective. Are the fixtures fair to their team? Why do they have to travel the full length of the country on a Wednesday evening in the middle of February when, no doubt, it will be cold and raining?
Some people might consider fixtures to be biased. But the truth is that scheduling any sporting event is an incredibly complex job. Let’s stick with the example of English football to understand why.
The basics
English football is divided into four main divisions, with the English Premier League (EPL) being the jewel in the crown, receiving world-wide attention. Each division has to play a double round-robin tournament – that is, each team has to play every other team in the division twice, once at home and once away.
For the EPL, this means 380 games have to be played. The other divisions play 552 games each, making it a total of 2,036 games to be played and scheduled over the football season.
Pairings
Teams from one division do not play teams in other divisions, so you might think that we can simply schedule each division independently. This is not the case. The football league operates a pairing system. Paired teams cannot play at home on the same day, or even the same weekend. This is done for reasons such as:
Crowd control: The police do not want paired teams such as Manchester United and Manchester City playing at home on the same day. This is because it will mean four sets of supporters will be in the centre of Manchester, making policing difficult.
Revenue maximisation: Some clubs would prefer other clubs not to be playing at home over the same weekend as they believe that it has an effect on their revenue.
Shared resources: Some clubs may share resources such as stewards and if they are playing at the same time, there may not be enough stewards for both fixtures.
Transport: The transport police would like to minimise the places where travelling fans are likely to meet and restrict the number of opposing fans that are passing through main transport hubs at any given time.
It is not always possible to respect every pairing, but the high priority pairings, such as Manchester City and Manchester United, will be given special attention.
Taking the fans into account
Over the busy Christmas and New Year period, the overall travel distances are kept to a minimum to save the fans having to travel long distances.
The fixtures are arranged so that a team does not have too many home (or away) fixtures in a row. This is to spread the costs for the home fans and to give pitches time to recover. In an ideal world teams would have alternate home/away fixtures, but it is impossible to do this for every team, for the entire season.
Even if we only had to consider the factors above it would still be a complex task to produce a schedule that is considered fair by everybody. But these factors just scratch the surface, and many others need to be taken into account.
Clubs will have special requests for a variety of reasons. These could include that their stadium is being used for a music concert on a certain date, it is a public holiday weekend and the town would prefer not to have football supporters visiting the town at that time, or there is another major event taking place in the town which should not be held at the same time as a large sporting event.
The police will have additional conditions, such as not wanting too many teams playing in the area under their control. For example, the number of fixtures that can take place in the London and Manchester areas are restricted. The police will also look at what other events they have to police, such as demonstrations, that are taking place at the same time.
Other football competitions – for example, the FA cup, international fixtures, other European fixtures – also need to be borne in mind.
Some sensitive fixtures may have to be given special consideration due to the previous history of particular clubs, which might not just mean them playing one another but also where particular groups of supporters might meet before and after a match. You don’t, for example, want lots of supporters all travelling through London at the same time, even though the fixtures might be taking place outside of London.
It may be preferential to play some derby fixtures at certain times. Some clubs might prefer to play a high-profile local derby on a midweek evening. They are likely to get a capacity crowd, whereas if the fixture was against a team where the fans had to travel a long way, they might not be inclined to travel on a midweek evening, so the clubs might prefer these fixtures to take place at the weekend.
How are fixtures scheduled?
Before the start of the season the Football League – the overarching management body – sends out a questionnaire to all the clubs asking for any special requests, although they are not guaranteed to be respected.
Once all the data has been collected, the initial schedules are produced. There follows a period of discussion with the key stakeholders – the clubs, the Football League, the Premier League and the police.
The schedule is gradually refined until everybody agrees that they have workable solution. But even with that, some games may have to be rescheduled during the season, because of cancellation, for whatever reason.
How could it be done?
Scheduling sporting events is a popular topic among researchers.
The scheduling of games is not so different from the problem supermarkets face when they need to deliver groceries (or even Santa delivering presents). For any scheduling problem the usual procedure is to develop a mathematical model and then attempt to optimise that model using one of the many tools that are available.
If the problem you are trying to solve is small enough, you may be able to use an exact method. But, as the problems get larger, exact methods tend to take too long, perhaps even millions of years of computation.
If we cannot use exact methods, then we have to resort to other methodologies such as meta-heuristics and hyper-heuristics. These algorithms tend to be reasonably fast and, although they cannot guarantee to return the optimal solution, they tend to give good solutions to the problem at hand.
Amongst the most popular methods for sports scheduling is simulated annealing, which draws its inspiration from the way metals are cooled to ensure that they have a uniform crystal structure. Like many approaches the method is based on a natural phenomena – with perhaps the most well known being genetic algorithms, which are based on Darwin’s theory of the survival of the fittest.
When simulated annealing is used for sports scheduling it starts with an initial schedule – which is probably terrible, but it gives us something to work with. It tries to improve the schedule by making small changes. This might be swapping a home and away team, changing the date of a fixture, switching two home (or away) teams etc. The important thing is that small changes are made in the hope we gradually improve the overall schedule. There are some algorithmic details that we need to control but simulated annealing is easy to understand, easy to implement and tends to run quite fast. This makes it the algorithm of choice for many researchers, and not just for sports scheduling problems, but for a wide variety of optimisation problems – such as delivering groceries.
It works – so why the fuss?
Without doubt, the Football League does a fantastic job in creating the schedules. But there is room for improvement.
We might be able to take more stakeholders into account. At the moment, supporters have little direct input. Perhaps it may be possible to take the weather into account. Or the fixtures could be arranged so that the chances of every team having something to play for are maximised. Or it may allow players to finally take that winter break they have been talking about for a while.
These are all questions not just for English football. Better algorithms are bound to improve scheduling.