Every year the English football authorities produce a set of fixtures for the four main divisions in England. Over the Christmas and New Year period every team has to play two fixtures; one being played at their home venue and the other at an opponent's venue. There are various other constraints that also have to be respected with the overall objective being to minimize the total distance travelled by all teams. In this paper, I formally define the problem, discuss the data collection that I have undertaken and present the algorithm (which is based on depth first search, followed by a local search) I have developed. Using data from four seasons, I show that I am able to produce better schedules than those currently used. Football (called soccer in the USA) is the national game of England. There are four main divisions (see Appendix A for the main terms I use in this paper) which most people would consider as making up the 'English football league'. These divisions are administered by three bodies, the Football Association (FA), the Premier League and the Football League. The Football Association (http://www.thefa.com, last accessed 13 March 2006) is the governing body of the game with a key aim of developing the sport at all levels. The Premier League (http://www.premierleague.com, last accessed 13 March 2006), formed in May 1992 in order to promote the top division of the game, has commercial independence from the Football Association and the Football League and is able to negotiate its own broadcast and sponsorship agreements. The Football League (http://www.football-league.co.uk, last accessed 13 March 2006) provides the referees for fixtures, produces the fixture programme, administers the transfer system and looks for ways to generate extra revenue for its member clubs. For the [2005][2006] season, the top four divisions were known as the 'Barclays Premiership', 'Coca-Cola Championship', * Correspondence: G Kendall, School of Computer Science and IT, The University of Nottingham, Jubilee Campus, Wollaton Road, Nottingham, Notts NG8 1BB, 'Coca-Cola League One' and 'Coca-Cola League Two'. The names of the divisions change in line with sponsorship arrangements. The Barclays Premiership comprises 20 teams, with the other three divisions each having 24 teams. Each division is self-contained, in that they hold their own double round robin tournament. The total number of fixtures played in the Barclays Premiership is 380, with 552 fixtures being played in the other three divisions, giving a total of 2036 fixtures that have to be scheduled in a given season. To produce the required double round robin tournament for each division, I could use algorithms drawn from the literature, with one of the most common being the polygon construction method (Dinitz et al, 2007) . However, this method is unlikely to produce a fixture list that is acceptable to all interested parties (which include the football authorities, the football clubs, the supporters, the police, etc) as the algorithm does not cater for all the real-world requirements that make up an acceptable set of fixtures. For example, the pairing system (see Problem Definition section) operates across divisions, so that fixtures in one division cannot be scheduled without reference to the other divisions. Another real-world requirement, not captured by methods such as polygon construction, arises when scheduling fixtures over holiday periods. The period around Christmas is a particularly busy time, with teams playing at least twice. The dates on which the fixtures take place over this period differs from year to year, and there could be more than two fixtures for each team. However, it is always the case that each team will play two related fixtures, with these fixtures having to adhere to the set of constraints discussed below (Problem Definition section and in Appendix B). Given the specific requirements of these two fixtures, it is usual to schedule them first and then generate the rest of the schedule around them. The aim of this paper is to investigate if we are able to generate fixtures, for these two days, that adhere to the various constraints, but have travel distances that are less than the distances of the fixtures produced by the football authorities (I refer to the fixture lists produced by the football authorities as the published fixtures). Note that I will refer to the first fixture list as the Boxing Day (26th December) fixtures and the second fixture list as the New Year's Day (1st January) fixtures. As can be seen from Table 1 , the fixtures are not always played on these two dates but it is convenient to refer to them in this way. This paper is organized as follows. In the next section, I present related work with respect to sports scheduling. Next, I informally describe the problem (a formal definition is given in Appendix B). Following this, I present the data that I have used. Next, I describe the algorithmic approach that I adopt. Finally, I show the results and then present my conclusions and suggest future directions for research in this area. There is a body of work which has considered the minimization of travel distances for sports schedules. Costa (1995) , for example, investigated the scheduling requirements of the National Hockey League, where one of the factors was to minimize the distances travelled. The introduction of the Travelling Tournament Problem (Easton et al, 2001) , using distances based on the road trips that have to be undertaken by Major League Baseball teams in the United States, has helped promote research interest in finding shortest travelling distances. Easton et al initially introduced seven instances, containing 4, 6, 8, 10, 12, 14 and 16 teams, which have been tackled, using various approaches. See, for example Crauwels and van Oudheusden (2002) , Ribeiro and Urrutia (2004) , Easton et al (2003) and Araújo et al (2006) . The best results have been reported, using simulated annealing (Anagnostopoulos et al, 2006) . A new set of larger instances has recently been introduced (December 2005). This comprises an additional nine instances (16, 18, 20, 22, 24, 26, 28, 30 and 32 teams). An up-to-date list of the best known solutions, as well as details of all the instances, can be found on Michael Trick's web site (http://mat.gsia.cmu.edu/TOURN/, last accessed 13 March 2006). Urrutia and Ribeiro (2004) have shown that minimizing distance and maximizing breaks (two consecutive home games (home break) or two consecutive away games (away break)) is equivalent. This followed previous work (de Werra, 1981 Werra, , 1988 Elf et al, 2003) which showed how to construct schedules with the minimum number of breaks. Much of the previous work (especially with respect to the Travelling Tournament Problem) is based on the assumption that teams go on road trips. A road trip involves a team leaving their home city, travelling to their first opponent, playing a fixture and then travelling to their second opponent (and possibly third, fourth, . . .), before returning home. Road trips are common in countries such as the US, due to the distances involved, but not common in the UK where teams will leave their home location, play the fixture and then return home. Therefore, there is a distinct difference between the previous work on the Travelling Tournament Problem, and the work reported here. For a set of fixtures, making up an entire English football season we cannot minimize the total distance travelled. The amount of travel is dictated by the fixtures that are to be played because each team returns home after every fixture. However, we can consider other factors of the fixture list in order to assist both the teams and the supporters. For example, we could try and minimize the distance between teams for mid-week fixtures. We might also attempt to minimize the number of breaks and, in an ideal set of fixtures, every team will play alternate home and away fixtures. We could also try and schedule some fixtures when they are likely to receive the most media interest or we could schedule fixtures which are likely to have low supporter interest in order to maximize gate receipts. The scheduling aspect that I am considering in this paper is minimizing the distance travelled for two complete fixtures (a complete fixture is defined as a set of fixtures when every team plays). These two complete fixtures can be used over the Christmas holiday period when, for a variety of reasons, teams wish to limit the amount of travelling they do. As I shall discuss later, these fixtures are normally scheduled first and they do have the lowest travelling distances of all the complete fixtures in the season. In order to judge the effectiveness of my approach, I shall compare my fixtures against the fixtures that were actually used (which I shall refer to as the published fixtures). Readers with an interest in sports scheduling are referred to the following papers which contain problems and approaches applicable to a variety of sports (Campbell and Chen, 1976; G Kendall-Scheduling English football fixtures over holiday periods 745 Cain, 1977; Bean and Birge, 1980; Ferland and Fleurent, 1991 ,Wright, 1991 , 1994 Schreuder, 1992; Armstrong and Willis, 1993; Russell and Leung, 1994; Willis and Terrill, 1994; Ball and Webster, 1997; Nemhauser and Trick, 1998; Schaerf, 1999; Thompson, 1999; Henz, 2001; Yang et al, 2002; Burke et al, 2004; Henz et al, 2004; Cassady et al, 2005; Coleman, 2005; Bartsch et al, 2006; Drexl and Knust, 2007) . An excellent overview of sports scheduling can be found in (Easton et al, 2004) . The problem is formally defined in Appendix B. Here, I give an informal description. The pairing system specifies that certain teams should not be allowed to play at home on the same day. Examples of these include Manchester United and Manchester City, Liverpool and Everton and Chelsea and Fulham. These restrictions are typically due to policing requirements. The pairings used in this paper are shown in Appendix C. I am required to produce two complete fixtures, one for Boxing Day and the other for New Year's Day. Each complete fixture consists of 92 teams, resulting in 46 fixtures. The overall aim is to minimize the total distance travelled by all the teams, over the two days. In addition, there are a number of constraints that have to be respected. These are hard constraints, in that they cannot be violated. Tables 3  and A1 ). (5) There is a limit on the number of London-based clubs that can play at home on any one day. Similarly, there are limits on the number of London Premiership clubs that can play at home on the same day and also the number of Greater Manchester clubs that can play at home on the same day. The limits of these values are shown in Appendix D. As mentioned in the introduction, all teams play (at least) two fixtures over the Christmas period. Typically, these fixtures are played on Boxing Day (26th December) and New Year's Day (1st January), but the actual dates do differ from year to year. December) adheres to the constraint that if a team played at home on Boxing Day, it plays away on 28th/29th December (and vice versa). Therefore, every team has a three fixture sequence of home/away/home or away/home/away. However, the 28th/29th December fixtures has a higher travel distance (6747 + 839 = 7586) and so is not used for comparison purposes here. Therefore, in this paper, I have access to four sets of data (seasons 2002-2003, 2003-2004, 2004-2005 and 2005-2006) and Table 2 presents just one of the published fixtures (Boxing Day, 2004. The Fixture and Division columns are self-explanatory. The Distance column is the distance between each team and is calculated using the postcode (ZIP code) of the teams and utilizing one of the UK car breakdown service web sites which incorporates a route planner (http://www.greenflag.co.uk, accessed 28 December 2005). The distances for this study were all collected at the same time (during December 2005). The distances will actually alter over time due to changes in road layouts, the construction of new roads, etc. With this in mind, I have supplied all the distances used in this paper on the author's web site (due to space limitations it is too large to list here) (http://www.cs.nott.ac.uk/∼gxk/research-data/). The Clash column indicates where there is a pair clash in the published fixtures. That is, two teams are playing at home, when they have been defined as a pair. For example, in Table 2 , both Birmingham and Coventry are at home and these teams have been defined as a pair. Table 2 represents just a sample of the published fixtures. The other fixtures can be found in Rollin and Rollin (2002 but the important factors, with regards to the work presented here, have been summarized in Table 3 . There are 92 teams across the four divisions, so a complete fixture comprises 46 fixtures. In order to create fixtures for Boxing Day and New Year's Day, I need to create two complete fixtures while minimizing travel distances, limiting the number of pair clashes and adhering to the other constraints described above and formally presented in Appendix B. One possible way to generate the schedules is to create a complete search tree, where each node represents a fixture and the path from the root node to the bottom of the tree G Kendall-Scheduling English football fixtures over holiday periods 747 represents a complete fixture. In this case, the depth of the search tree will be 45 (assuming the root node is level 0) and the branching factor is as follows. If I start with the Barclays Premiership (20 teams), I would firstly choose two teams (I use the notation C(m, n) to represent 'm choose n'). Therefore, I have C(20, 2) × 2 = 190 × 2 = 380 nodes at level 0. Note that I multiply by 2, as each fixture can be reversed to switch the home and away teams. The next level would have a branching factor of C(18, 2) × 2 = 153 × 2 = 306 and so on until I reach C(2, 2) × 2 = 1 × 2 = 2. This would represent a search tree with 10 levels and 380 × 306 × · · · × 2 nodes (2.43 × 10 18 ). Once I have produced the search tree for the Barclays Premiership, I would now have to continue building the tree by incorporating the Coca-Cola Championship. Therefore, going from level 9 to level 10 would have a branching factor of C(24, 2) × 2 = 276 × 2 = 552, with the next level having a branching factor of C(22, 2) × 2 = 231 × 2 = 462 nodes. Once the tree had been expanded for the Coca-Cola Championship, I would repeat the process for the two remaining divisions. The size of the search tree for just one of the Coca-Cola divisions is of the order 6.20 × 10 23 . A full enumeration of a search tree for just a single division is not possible, let alone a combined search tree for all the divisions. Therefore, I have developed a two-stage approach. The first stage builds a separate search tree for each division, incorporating pruning to reduce the size of the search space. Each division returns the best solution it finds which is a set of 10 fixtures (resp. 12) for the Barclays Premiership (respectively the Coca-Cola divisions). This search process is carried out twice for each division, once for Boxing Day and once for New year's Day. There are slight differences between the two searches for the different days, which I describe below. The second stage carries out a local search across all divisions, for both days, in order to find a good quality, feasible solution. The details of both these stages are described below. Stage 1: Depth First Search: I initially produce a solution for each division, for both days. I generate a search tree, pruning at branches that either cannot lead to a better solution than one already generated or which will lead to an infeasible solution. I begin by taking one team (at random) and generating all its possible fixtures (both home and away). Next I carry out a depth first search. A node is expanded by generating all possible fixtures. In expanding a node, I check the following. (1) I do not expand a node that would lead to the same team playing twice in that branch of the tree, as this would be an infeasible schedule. (2) If the travel distance for two teams is greater than 200 miles, I do not generate that search node. The figure of 200 is based on the fact that (in the UK) this represents travel time of about 3 h which is about the maximum that teams/supporters would wish to travel over the holiday period. I do make an exception for Plymouth. Owing to its location there are not many teams within 200 miles so I raise their limit to 250. (3) If the expanded node would lead to a total travel distance which is greater than the best solution seen so far, I do not generate that node. The best solution found so far is defined as a node which contains a full set of fixtures (ie at level 9 for the Barclays Premiership and level 11 for the other divisions) and the total distance travelled is the minimum found so far. (4) I do not allow paired teams to play each other. (5) I do not allow paired teams to both be playing at home. I follow exactly the same procedure as above to generate fixtures for New Year's Day. In addition, the complete fixture found above is input to this search procedure so that additional checks can be performed. In this procedure, I carry out these additional checks when generating new nodes in this search tree. (1) I relax the condition (5, above) that paired teams cannot both be at home. The aim of the local search is to reduce the number of pair clashes to acceptable values (ie less than or equal to those of the published lists) as well as to ensure that the other constraints are not violated. Before describing the local search procedure I define a swap operation which I use within the search. This operation swaps the home and away teams in a given schedule. If I were only considering one complete fixture, this would be a simple operation as simply swapping the teams in a single fixture would still lead to a feasible schedule and, in addition, it would not affect the distance travelled as the distances are assumed to be symmetric. However, where I Fixture f have two complete fixtures, as I do here, swapping the home and away team in one schedule leads to an infeasible schedule as I now have the same teams which are playing at home (or away) in both complete fixtures. Therefore, I have to carry out the swap in one fixture and repair the other fixture. An example is shown in Figure 1 . Figure 1a shows the state of two schedules ( f (B) and f (N )) before the swap operation. The fixture Chelsea versus Portsmouth, in f (B), has been identified as the fixture where the teams will be swapped. After the swap (Figure 1b ) the two teams have been swapped. However, in order to maintain feasibility of the two fixtures, I have to locate Chelsea and Portsmouth in f (N ) and swap them as well. Note that this second swap has the potential to alter the travel distances as Chelsea were travelling to Arsenal, but Portsmouth are now travelling to Arsenal. Fulham were travelling to Portsmouth but now Fulham are travelling to Chelsea. Having defined this swap operation, I can now describe the local search algorithm. I call the following operators 5000 times (ie a total of 40 000 calls). I use the value of 5000 after experimentation but it can easily be increased as the local search moves are computationally inexpensive (the local search takes little more than a few minutes). (1) If there is a pair clash in f (B), I locate the fixture that has a maximum number of clashes, choosing randomly if there is more than one candidate. I swap the home and away teams, making the corresponding swap in f (N ) in order to maintain feasability. The total distance figures are calculated by adding together the Boxing Day and New Year's Day Travel Distances. The distance saving percentage improvement is calculated as '100-generated distance * 100/published distance'. (5) If the number of Barclays Premiership London clubs playing at home in f (B) exceeds the threshold, I choose (at random) one of those fixtures and swap the home and away teams. I make the corresponding swap in f (N ) to maintain feasability. (6) Same as 3 but now considering f (N ). After each of the above, I check if I have a new best solution (ie minimum travel distance and no constraint violations). At the end of the local search phase, I carry out a postprocessing phase, to ensure that a feasible solution is returned. This post-search process checks that I do not have any reverse fixtures (team i playing team j, followed by team j playing team i) and that I do not have any local derbies (two paired teams playing each other). While these two conditions exist, I carry out the swap operator, ensuring I include one of the teams that is contributing to the infeasible solution. The output of this post-process phase is a solution that does not violate any constraints. Using the above two-stage approach, I am able to produce significant improvements over the published fixtures (see Tables 3 and 4) . Table 3 shows the improvements I achieved for each day. In addition, I was able to reach these solutions with the same, or fewer, pair clashes when compared with the published fixtures. On Boxing Day, for season [2005][2006], for example, I managed a distance saving of 1246 (4295 − 3049), with two less pair clashes. The previous season (2004The previous season ( -2005, the distance saving for Boxing Day is 838 (4563−3725) but now achieved with the same number of pair clashes. Table 4 shows total distance travelled over the two complete fixtures for each season. It is noticeable that the highest savings were achieved in the 2005-2006 season. I discuss the possible reasons for this in my concluding remarks. However, even removing this year from consideration, I achieve an average overall saving of 24.86% ([29.95+22.15+22.47]/3), with the same number of pair clashes. Table 5 shows one of the complete fixtures that were generated. In this paper, I have described a sports scheduling problem that has not been reported before in the literature. The problem is to minimize the total distance travelled by 92 football league clubs over two complete fixtures. At first sight, it may seem to be a similar problem to the Travelling Tournament Problem but, in fact, the problems are very different. The aim of the Travelling Tournament Problem is to minimize distances by finding a set of suitable road trips, so that when the teams play a number of away games, they limit the amount of travel that is undertaken. In this problem, the travel distances, for a given team over a given season, is fixed. Instead, I try and minimize the distance for two dates so that these fixtures can be used over the Christmas period. As can be seen from the results, I have made significant savings over the published fixtures. In doing so, I have not increased the number of pair clashes and, in one of the seasons, I have actually reduced the number of pair clashes. In addition, I have not allowed any paired teams to play each other. This is occasionally allowed in the published fixtures, which can help the reduction of the overall distance as paired teams are often close to one another. Finally, I have also ensured that I do not have more than a certain number of teams playing in London or Greater Manchester on any one day. I am currently discussing my results with the Football League. I would like to extend this work in order to try and produce fixture lists for the entire season. This will include catering for many more constraints, which is why I would like to discuss the problem with the problem owners as I would like to ensure I am solving the problem that they actually face and not some simplified abstraction. With regards to the work reported in this paper, I see a number of future directions that I could follow. The first is to provide a fair comparison for seasons where four complete fixtures are needed over the holiday season. season is an example when this was a requirement. Table  1 shows that over the holiday period for this season, there were actually four complete fixtures played. The two additional complete fixtures (played on 31st December, 2nd January and 3rd January) also adhere to the constraint that if you play at home on one of these days, then you have to play away on the other day. Also, by looking at the distances (4503+6564+296=11 363) I note that these are also among the lowest in the season when considering all the complete fixtures. This indicates that, for this season, the schedulers have had to produce two sets of complementary fixtures for the holiday period. In fact, this has been reported in the press and is because 2006 is a world cup year and the English football authorities try to schedule games in such a way that allows the English national team to spend more time together in preparation for the world cup. In the previous season (2004)(2005) there were also four fixtures scheduled, which also adhered to the home/away constraints. However, the distances for the alternative fixtures are high so I assume that there was not a requirement to minimize distances. I would also like to further investigate the bounds that I place on my depth first search. In the algorithm section, I described how I control whether I expand a node or not. I have some more ideas as to how I can improve this. One idea is to increase the 200 mile limit (250 for Plymouth) so that I consider more solutions. Then, in the local search I could introduce an operator that looks at the team which has the highest travel distance and carry out a move which tries to re-schedule that team. Another idea is to order the fixtures when considering the expansions. That is, to expand lower cost (those with lower distance) nodes first. This might have the effect of reducing the search space as I am likely to exceed the total travel distance (ie best solution found so far) higher in the search tree as we should find a relatively low cost solution early in the search which will reduce the number of expansions I have to carry out later. It would also be interesting to investigate if I can reduce the number of clashes, while still maintaining the travel distances to acceptable levels. In this current study, I set the upper bound on the number of pair clashes to those that are present in the published fixtures. What effect would it have on the solutions if I decreased these limits? Would the solutions be considered better by, say, the police as, although, the teams would have to travel further, would there be a reduction in the required policing resources due to having fewer teams playing in a given geographical area? In order to investigate this particular line of research, I would need to talk to police authorities, as well as the football authorities. This has been a very interesting problem to work on and it has the potential for significant further investigation. This study has used an exact method (depth first search) combined with a local search. If I am to tackle the problem of generating fixture lists for the complete season I am likely to have to resort to meta-heuristic approaches (eg genetic algorithms (Goldberg, 1989; Sastry et al, 2005) , simulated annealing (Kirkpatrick et al, 1983; Aarts et al, 2005) , hyper-heuristics (Burke et al, 2003a,b; Ross, 2005; Burke et al, 2007) etc). However, as I have shown here, it is possible to decompose the problem and, perhaps, the hybridization of exact and metaheuristic approaches might also be applicable for the larger problem. This paper, for the first time in the academic literature, studies the problems associated with scheduling football fixtures in the four major English divisions. In particular, I study how fixtures can be scheduled over holidays periods when travel distances have to be minimized. One contribution of this paper is to generate fixtures which are better than published fixtures (ie those that are published and used). By 'better', I mean when comparing the overall distance travelled, while still adhering to the required constraints. I use a combination of depth first search, followed by a local search in order to find feasible solutions. A further contribution of this work describes the problem both in a descriptive way and also presents a formal model. It is hoped that this will promote more research on this problem. In addition, I describe the data collection that was undertaken in order to allow other researchers access to the data in order to reproduce my results or to develop this work even further. Indeed, the data I present could be used for a variety of other applications such as vehicle routing or travelling salesman. Acknowledgements-I would like to thank the anonymous reviewers for their comments. This has led to a much improved paper.
This process produced eight separate fixtures (two sets of fixtures for each division) which adhered to some of the constraints (e.g. a team plays at home on one day and away on the other) but had not yet addressed the constraints with regards to pair clashes (see REF for a detailed description).
Scheduling English football fixtures over holiday periods
Journal of the Operational Research Society
Computer Science