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

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.