A new approach based on graph matching and evolutionary approach for sport scheduling problem

Article type: Research Article

Authors: Khelifa, Meriem^{a; *} | Boughaci, Dalila^a | Aïmeur, Esma^b

Affiliations: [a] Department of Computer Science, The Laboratory for Research in Artificial Intelligence (LRIA), USTHB, Algeria | [b] Department of Computer Science and Operations Research HERON Laboratory, Université de Montréal, Canada

Correspondence: [*] Corresponding author: Meriem Khelifa, Department of Computer Science, The Laboratory for Research in Artificial Intelligence (LRIA), USTHB, Algeria. E-mail: [email protected].

Abstract: The Traveling Tournament Problem (TTP) is concerned with finding a double round-robin tournament schedule that minimizes the total distances traveled by the teams. It has attracted significant interest recently since a favorable TTP schedule can result in significant savings for the league. This paper proposes an original evolutionary algorithm for TTP. We first propose a quick and effective constructive algorithm to construct a Double Round Robin Tournament (DRRT) schedule with low travel cost. We then describe an enhanced genetic algorithm with a new crossover operator to improve the travel cost of the generated schedules. A new heuristic for ordering efficiently the scheduled rounds is also proposed. The latter leads to significant enhancement in the quality of the schedules. The overall method is evaluated on publicly available standard benchmarks and compared with other techniques for TTP and UTTP (Unconstrained Traveling Tournament Problem). The computational experiment shows that the proposed approach could build very good solutions comparable to other state-of-the-art approaches or better than the current best solutions on UTTP. Further, our method provides new valuable solutions to some unsolved UTTP instances and outperforms prior methods for all US National League (NL) instances.

Keywords: Sport scheduling, Traveling Tournament Problem, genetic algorithm

DOI: 10.3233/IDT-190114

Journal: Intelligent Decision Technologies, vol. 14, no. 4, pp. 565-580, 2020