Confection de calendriers d'événements sportifs au Québec

L'automatisation de la confection de calendriers pour les ligues sportives a reçu une attention particulière au cours des dernières années puisque les ligues sportives génèrent des revenus considérables ainsi que des problèmes d'optimisation combinatoire intéressants. La Fédération Québécoise pour le Sport Étudiant (FQSE) a reçu le mandat d'organiser les championnats sportifs provinciaux scolaires, collégiaux et universitaires. Nous comparons le problème québécois qu'elle nous expose à une classe de problèmes similaires communément appelés dans la littérature traveling tournament problem, ce type de problèmes ayant pour but de minimiser la distance totale parcourue par les équipes. Nous formulons par la suite un modèle mathématique dont l'objectif est de produire des calendriers satisfaisant un nombre optimal de contraintes inédites fournies par la FQSE. La revue de littérature met en avant les différentes méthodes qui ont été utilisées pour résoudre le traveling tournament problem, mais elle nous permet aussi de constater qu'un bon nombre des contraintes du problème québécois sont originales. Pour résoudre ce problème, nous avons formulé un modèle mathématique en nombres entiers que nous résolvons à l'aide du logiciel CPLEX. Notre modèle prend en compte des variables booléennes à deux indices qui vont nous permettre de d´eterminer l'endroit où a lieu chaque rencontre, la date à laquelle chaque rencontre va se jouer et les équipes qui vont jouer à domicile, à l'extérieur ou celles qui ne vont pas jouer à chaque date. Il a été testé sur deux instances fournies par la FQSE pour le football collégial et universitaire pour lesquelles nous avons pu facilement générer des calendriers optimaux. Une extension du modèle est ensuite proposée pour prendre en compte la distance parcourue pour chaque équipe. Ce nouveau modèle utilise des variables booléennes à deux et trois indices, le rendant ainsi plus intéressant que les modèles que nous avons pu trouver dans la littérature. Le modèle développé est capable de prendre en compte toutes les contraintes que nous avons pu rencontrer dans la littérature, mais il est aussi capable de traiter ensemble un bon nombre de contraintes originales. La flexibilité du modèle rend ses applications éventuelles nombreuses étant donné que des contraintes supplémentaires peuvent facilement être rajoutées en autant qu'elles s'écrivent comme une combinai- son linéaire des variables du modèle.