<  Back to the Polytechnique Montréal portal

Mathematical Modeling and Optimization Approaches for Scheduling the Regular-Season Games of the National Hockey League

Elivelton Ferreira Bueno

PhD thesis (2014)

[img]
Preview
Download (925kB)
Cite this document: Bueno, E. F. (2014). Mathematical Modeling and Optimization Approaches for Scheduling the Regular-Season Games of the National Hockey League (PhD thesis, École Polytechnique de Montréal). Retrieved from https://publications.polymtl.ca/1534/
Show abstract Hide abstract

Abstract

RÉSUMÉ : La Ligue nationale de hockey (LNH) est une association sportive professionnelle de hockey sur glace regroupant des équipes du Canada et des États-Unis. Chaque année, la LNH dois compter sur un calendrier de haute qualité concernant des questions économiques et d'équité pour les 1230 matchs de sa saison régulière. Dans cette thèse, nous proposons le premier modèle de programmation linéaire en nombres entiers (PLNE) pour le problème de la planification de ces matchs. Basé sur la littérature scientifique en planification des horaires sportifs, et aussi sur un raisonnement pratique, nous identifions et soulignons des exigences essentielles et des préférences qui doivent être satisfaites par des calendriers de haute qualité pour la LNH. La construction de tels calendriers, tout comme la planification des horaires sportifs en général, s'avère une tâche très difficile qui doit prendre en compte des intérêts concurrents et, dans plusieurs cas, subjectifs. En particulier, les expérimentations numériques que nous décrivons dans cette étude fournissent des évidences solides suggérant qu'une approche basée sur la PLNE est actuellement incapable de résoudre des instances de taille réaliste pour le problème. Pour surmonter cet inconvénient, nous proposons ensuite un algorithme de recherche adaptative à voisinage large (ALNS) qui intègre à la fois des nouvelles stratégies et des heuristiques spécialisées provenant de la littérature scientifique. Afin de tester cette approche, nous générons plusieurs instances du problème. Toutes les instances sont basées sur les calendriers officiels de la LNH et, en particulier, utilisent les dates de matchs à domicile de chaque équipe comme des dates de disponibilité de son aréna. Dans les situations les plus difficiles, la disponibilité des arénas est rare ou est à son minimum. Dans tous les cas, en ce qui concerne les indicateurs de qualité soulevés, l'algorithme ALNS a été capable de générer des calendriers clairement meilleur que leur correspondants adoptés par la LNH. Les résultats obtenus suggèrent que notre approche pourrait certainement permettre aux gestionnaires de la LNH de trouver des calendriers de meilleur qualité par rapport à une variété de nouvelles préférences.----------ABSTRACT : The National Hockey League (NHL) is a major professional ice hockey league composed of 30 teams located throughout the United States and Canada. Every year, the NHL must rely on a high-quality schedule regarding both economic and fairness issues for the 1230 games of its regular season. In this thesis, we propose the first integer linear programming (IP) model for the problem of scheduling those games. Based both on the pertinent sports scheduling literature and on practical reasoning, we identify and point out essential requirements and preferences that should be satisfied by good NHL schedules. Finding such schedules, as many other sports scheduling problems, is a very difficult task that involves several stakeholders with many conflicting, and often subjective, interests. In fact, computational experiments that we describe in this study, provide compelling evidence that an IP approach is currently unable to solve instances of realistic size for the problem. To overcome such drawback, we propose then an Adaptive Large Neighborhood Search (ALNS) algorithm that integrates both novel strategies and specialized heuristics from the scientific literature. To test the approach, we generate instances based on past NHL schedules and on a given number of arena-available dates that are suitable for the home games of each team. In the most challenging instances, availability of arenas is scarce or at its minimum. In all cases, regarding the identified concerns, the ALNS algorithm was able to generate much better schedules than those implemented by the NHL. Results obtained suggest that our approach could certainly identify unnecessary weakness in NHL schedules, makes the NHL managers aware of better schedules with respect to different requirements, and even lead them to consider other desired features they might not have previously taken into account.

Open Access document in PolyPublie
Department: Département de mathématiques et de génie industriel
Dissertation/thesis director: Michel Gendreau and Jacques Ferland
Date Deposited: 23 Dec 2014 10:35
Last Modified: 27 Jun 2019 16:48
PolyPublie URL: https://publications.polymtl.ca/1534/

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Repository Staff Only