On the application of graph colouring techniques in round-robin sports scheduling

Lewis, Rhyd ORCID: https://orcid.org/0000-0003-1046-811X and Thompson, Jonathan Mark 2011. On the application of graph colouring techniques in round-robin sports scheduling. Computers & Operations Research 38 (1) , pp. 190-204. 10.1016/j.cor.2010.04.012

Preview

PDF - Submitted Pre-Print Version Download (526kB) | Preview

Abstract

The purpose of this paper is twofold. First, it explores the issue of producing valid, compact round-robin sports schedules by considering the problem as one of graph colouring. Using this model, which can also be extended to incorporate additional constraints, the difficulty of such problems is then gauged by considering the performance of a number of different graph colouring algorithms. Second, neighbourhood operators are then proposed that can be derived from the underlying graph colouring model and, in an example application, we show how these operators can be used in conjunction with multi-objective optimisation techniques to produce high-quality solutions to a real-world sports league scheduling problem encountered at the Welsh Rugby Union in Cardiff, Wales.

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Mathematics
Subjects:	Q Science > QA Mathematics Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Uncontrolled Keywords:	Metaheuristics; Sports scheduling; Graph colouring; Timetabling
Publisher:	Elsevier
ISSN:	0305-0548
Last Modified:	03 Nov 2023 07:27
URI:	https://orca.cardiff.ac.uk/id/eprint/11081

Citation Data

Cited 34 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item