Graph-based heuristics for rest difference minimisation

Abstract

Complaints often arise from teams with less rest time between games in a tournament, highlighting the importance of minimising rest differences for fairness. Achieving fairness through rest difference minimisation is an empirically hard problem when determining the opponents and matchdays of teams in a tournament. To address this issue, we propose novel heuristic approaches based on graph theory. Remarkably, one of our heuristic methods significantly outperforms previously reported outcomes. We also show that the widely used canonical schedule has the maximum optimal rest difference value among all possible opponent schedules, and if the number of rounds is a prime number, shuffling the rounds within the canonical schedule offers no advantages in reducing rest differences. Furthermore, we present an efficient integer programming formulation to determine the total rest difference for a given opponent schedule. © 2025 Elsevier B.V., All rights reserved.