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.

Abstract

Several sport federations are confronted with the problem of tournament scheduling. The Fédération Québcoise du Sport Étudiant (FQSE) has the mandate to organize championship tournaments at the school, college and university levels in the province of Quebec and we have been asked to help them in scheduling their tournaments. We first compare their problem to a class of similar instances commonly known as the traveling tournament problem (TTP). In the TTP, the objective is to minimize the total traveled distance for all teams. Then we formulate a mathematical model for the problem in Quebec where the objective is to produce schedules with an optimal number of satisfied constraints. The constraints we consider are all given by the FQSE and the literature review shows that many of them are new. After having described in the literature review the different methods that have been used for solving the TTP, we propose an integer programming model and use CPLEX to solve it. The mathematical model uses boolean variables with two indices which indicate where and when each game is to take place, and which teams play at home, away or do not play in each round. The mathematical model has been tested on two instances given by the FQSE for college and university football. For both of them we can easily generate optimal schedules. In the last section, an extended model is presented to take into account the traveled distance for each team. This model uses boolean variables with two or three indices, which makes it more interesting when compared with what can be found in the literature. Our model is able to take into account the different types of constraints we have seen in the literature, but it can also handle a good number of original constraints. Its flexibility makes it easy to apply to several sport scheduling problems: we can add any constraint that can be written as a linear combination of the variables of the model. The main restriction is due to the fact that the more constraints a problem has, the more difficult it gets. In that case, a good solution would be to develop a heuristic algorithm.