Abstract
In previous work the distance travelled by UK football clubs, and their supporters, over the Christmas/New Year period was minimised. This is important as it is not only a holiday season but, often, there is bad weather at this time of the year. Whilst searching for good quality solutions for this problem, various constraints have to be respected. One of these relates to clashes, which measures how many paired teams play at home on the same day. Whilst the supporters have an interest in minimising the distance they travel, the police also have an interest in having as few pair clashes as possible. This is due to the fact that these fixtures are more expensive, and difficult, to police. However, these two objectives (minimise distance and minimise pair clashes) conflict with one another in that a decrease in one intuitively leads to an increase in the other. This chapter explores this question and shows that there are compromise solutions which allow fewer pair clashes but does not statistically increase the distance travelled. We present a detailed set of computational experiments, on datasets covering seven seasons. We conclude that it is sometimes possible to reduce the number of pair clashes whilst not significantly increasing the overall distance that is travelled.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Aarts, E., Korst, J., Michels, W.: Simulated annealing. In: Burke, E.K., Kendall, G. (eds.) Search Methodologies: Introductory Tutorials in Optimization and Decision Support Methodologies, 1st edn., ch. 7, pp. 97–125. Springer (2005)
Anagnostopoulos, A., Michel, L., Van Hentenryck, P., Vergados, Y.: A simulated annealing approach to the traveling tournament problem. Journal of Scheduling 9, 177–193 (2006)
Ball, B.C., Webster, D.B.: Optimal scheduling for even-numbered team athletic conferences. AIIE Transactions 9, 161–169 (1977)
Bean, J.C., Birge, J.R.: Reducing travelling costs and player fatigue in the national basketball association. Interfaces 10, 98–102 (1980)
Cain, W.O.: The computer-aided heuristic approach used to schedule the major league baseball clubs. In: Ladany, S.P., Machol, R.E. (eds.) Optimal Strategies in Sports, pp. 33–41. North Holland, Amsterdam (1977)
Campbell, R.T., Chen, D.S.: A minimum distance basketball scheduling problem. In: Machol, R.E., Ladany, S.P., Morrison, D.G. (eds.) Management Science in Sports. Studies in the Management Sciences, vol. 4, pp. 15–25. North-Holland, Amsterdam (1976)
Costa, D.: An evolutionary tabu search algorithm and the NHL scheduling problem. INFOR 33, 161–178 (1995)
Di Gaspero, L., Schaerf, A.: A composite-neighborhood tabu search approach to the traveling tournament problem. Journal of Heuristics 13, 189–207 (2007)
Dinitz, J.H., Fronček, D., Lamken, E.R., Wallis, W.D.: Scheduling a tournament. In: Colbourn, C.J., Dinitz, J.H. (eds.) Handbook of Combinatorial Designs, 2nd edn., pp. 591–606. CRC Press (2006)
Drexl, A., Knust, S.: Sports league scheduling: Graph- and resource-based models. Omega 35, 465–471 (2007)
Easton, K., Nemhauser, G.L., Trick, M.A.: The Traveling Tournament Problem Description and Benchmarks. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 580–585. Springer, Heidelberg (2001)
Easton, K., Nemhauser, G.L., Trick, M.A.: Solving the Travelling Tournament Problem: A Combined Integer Programming and Constraint Programming Approach. In: Burke, E., De Causmaecker, P. (eds.) PATAT 2002. LNCS, vol. 2740, pp. 100–109. Springer, Heidelberg (2003)
Easton, K., Nemhauser, G.L., Trick, M.A.: Sports scheduling. In: Leung, J.T. (ed.) Handbook of Scheduling, pp. 52.1–52.19. CRC Press (2004)
Elf, M., Jünger, M., Rinaldi, G.: Minimizing breaks by maximizing cuts. Operations Research Letters 31(3), 343–349 (2003)
Evans, J.R.: A microcomputer-based decision support system for scheduling umpires in the American Baseball League. Interfaces 18, 42–51 (1988)
Ferland, J.A., Fleurent, C.: Computer aided scheduling for a sport league. INFOR 29, 14–25 (1991)
Kendall, G.: Scheduling English football fixtures over holiday periods. Journal of the Operational Research Society 59, 743–755 (2008)
Kendall, G., Knust, S., Ribeiro, C.C., Urrutia, S.: Scheduling in sports: An annotated bibliography. Computers & Operations Research 37, 1–19 (2010)
Kendall, G., While, L., McCollum, B., Cruz, F.: A multiobjective approach for UK football scheduling. In: Burke, E.K., Gendreau, M. (eds.) Proceedings of the 7th International Conference on the Practice and Theory of Automated Timetabling (2008)
Knust, S.: Classification of literature on sports scheduling (2010), http://www.inf.uos.de/knust/sportssched/sportlit_class/ (last visited July 15, 2010)
Rasmussen, R.V., Trick, M.A.: Round robin scheduling – A survey. European Journal of Operational Research 188, 617–636 (2008)
Ribeiro, C.C., Urrutia, S.: Heuristics for the mirrored traveling tournament problem. European Journal of Operational Research 179, 775–787 (2007)
Trick, M.: Traveling tournament problem instances (2010), http://mat.gsia.cmu.edu/TOURN/ (last accessed July 15, 2010)
Urrutia, S., Ribeiro, C.: Minimizing travels by maximizing breaks in round robin tournament schedules. Electronic Notes in Discrete Mathematics 18-C, 227–233 (2004)
Urrutia, S., Ribeiro, C.C., Melo, R.A.: A new lower bound to the traveling tournament problem. In: Proceedings of the IEEE Symposium on Computational Intelligence in Scheduling, pp. 15–18. IEEE, Honolulu (2007)
de Werra, D.: Scheduling in sports. In: Hansen, P. (ed.) Studies on Graphs and Discrete Programming, pp. 381–395. North Holland, Amsterdam (1981)
de Werra, D.: Some models of graphs for scheduling sports competitions. Discrete Applied Mathematics 21, 47–65 (1988)
Wright, M.: Timetabling county cricket fixtures using a form of tabu search. Journal of the Operational Research Society 45, 758–770 (1994)
Wright, M.: 50 years of OR in sport. Journal of the Operational Research Society 60, S161–S168 (2009)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Kendall, G., McCollum, B., Cruz, F.R.B., McMullan, P., While, L. (2013). Scheduling English Football Fixtures: Consideration of Two Conflicting Objectives. In: Talbi, EG. (eds) Hybrid Metaheuristics. Studies in Computational Intelligence, vol 434. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-30671-6_14
Download citation
DOI: https://doi.org/10.1007/978-3-642-30671-6_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-30670-9
Online ISBN: 978-3-642-30671-6
eBook Packages: EngineeringEngineering (R0)