Scheduling English football fixtures over holiday periods

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.