¹The University of Nottingham, Nottingham, UK

Correspondence: G Kendall, School of Computer Science and IT, The University of Nottingham, Jubilee Campus, Wollaton Road, Nottingham, Notts NG8 1BB, UK. E-mail: gxk@cs.nott.ac.uk

Received March 2006; Accepted November 2006; Published online 7 March 2007.

Abstract

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.