Grouping and scheduling multiple sports leagues: an integrated approach

This paper introduces the multi-league grouping and scheduling problem, which integrates the grouping of teams into leagues and the scheduling of each league. This involves two possibly conflicting objectives: minimizing travel distance and minimizing capacity violations of venues shared by teams. We formulate this problem as a bi-objective mixed-integer programming model. Given the NP-hardness of the grouping problem, the integrated problem is particularly challenging. Hence, we design a two-layer constructive heuristic to efficiently approximate the Pareto set, using simulated annealing on the outer layer and an integer programming model on the inner layer. We further develop a speed-up version where the inner layer is solved heuristically. We develop a series of large-scale problem instances, including one based on data from the Royal Belgian Football Association. In a computational study, we compare our algorithms with an epsilon-constraint method and evaluate their results using various multi-objective solution quality metrics.