VI ALIO/EURO Workshop on Applied Combinatorial Optimization

December 15 - 17, 2008, Buenos Aires, Argentina

Metaheuristics for Optimization Problems in Sports

Celso Carneiro Ribeiro

Universidade Federal Fluminense, Brazil

Professional sport leagues involve millions of fans and significant investments in players, broadcast rights, merchandising, and advertising. Multiple agents, such as the organizers, media, players, fans, security forces, and airlines, play important roles in the leagues and tournaments. Professional sports leagues are therefore part of a major economic activity and face challenging optimization problems. On the other side, amateur leagues usually do not involve impressive amounts of money, but instead the number of tournaments and competitors can be very large, also requiring coordination and logistic efforts. The field of sports scheduling and management has been attracting the attention of an increasing number of researchers in multidisciplinary areas such as operations research, scheduling theory, constraint programming, graph theory, combinatorial optimization, and applied mathematics. Different optimization techniques have been applied to solve problems arising from sports scheduling and management. The hardness of the problems in the field lead to the use of a number of exact and approximate approaches, including integer programming, constraint programming, metaheuristics, and hybrid methods. Problems associated with the scheduling of round robin tournaments are of particular importance, due to their relevance in practice and to their interesting mathematical structure. We review some applications of metaheuristics to different scheduling problems in sports, such as the traveling tournament problem and referee assignment in sports competitions. Recent advances in metaheuristics are also illustrated in the context of these applications.