A traditional Benders’ approach to sports timetabling

David Van Bulck and Dries Goossens

European Journal of Operational Research, 2023, vol. 307, issue 2, 813-826

Abstract: Even for sports leagues with a small number of teams, the construction of a round-robin timetable taking into account various constraints, e.g., venue availability or travel distance, can be challenging. It is therefore common to decompose the problem with the first-break-then-schedule approach, which first decides when teams play home or away after which it determines a compatible assignment of opponents. When there are more time slots than games per team, so-called relaxed timetables, an alternative is the first-day-off-then-schedule approach which starts by deciding when teams receive a day of rest. Despite the popularity of these approaches, a major unsolved question is how to efficiently backtrack between the different phases of the algorithm. Moreover, existing backtracking schemes can only cope with a very limited set of timetable requirements. The main contribution of this paper is to show how traditional Benders’ decomposition relates to the aforementioned approaches, and how Benders’ cuts can be used to organize backtracking. To show the effectiveness and versatility of the proposed framework, we construct compact timetables that minimize the total number of travel trips, and relaxed timetables that either balance the games over the season or minimize the total differences in rest time of opposing teams. Furthermore, we discuss the quality of the obtained Benders’ cuts and strengthen integer programming formulations from the literature to construct relaxed round-robin timetables.

Keywords: OR in sports; Benders’ decomposition; First-break-then-schedule; First-day-off-then-schedule; Travelling tournament problem (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221722008542
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:307:y:2023:i:2:p:813-826

DOI: 10.1016/j.ejor.2022.10.044

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().