Return to search

[en] REFEREE ASSIGNMENT IN SPORT TOURNAMENTS: MONO AND MULTI-CRITERIUM ALGORITHMS AND APPLICATIONS / [pt] ATRIBUIÇÃO DE ÁRBITROS EM COMPETIÇÕES ESPORTIVAS: ALGORITMOS E APLICAÇÕES MONO MULTI-CRITÉRIO

[pt] A otimização em esportes é uma área que reúne diversas aplicações relacionadas
ao planejamento e gestão de atividades esportivas. Diversas técnicas
de otimização combinatória têm sido aplicadas, por exemplo, à  construção
de tabelas de torneios e à  análise do desempenho de equipes em competições.
Um problema que surge no contexto da organização de competições
esportivas consiste na determinação de quais árbitros atuarão em cada partida
de um determinado torneio. Diversas regras devem ser observadas no
processo de atribuição de árbitros, que em geral envolve também a consideração
de vários objetivos. Esta tese tem como objetivo principal apresentar
um estudo sobre um problema de atribuição de árbitros, comum a
várias ligas esportivas amadoras. Demonstra-se que a versão de decisão do
problema estudado é um problema NP-completo. Considera-se inicialmente
duas variantes mono-objetivo do PAA, que diferem uma da outra pela função
objetivo adotada. Propõe-se modelos de programação linear inteira que
permitem uma abordagem exata para a resolução de instâncias de pequeno e
médio portes. Com o intuito de tratar instâncias de tamanho real, propõe-se
também abordagens aproximadas de resolução baseadas na metaheurí­stica
Iterated Local Search (ILS). Uma vez que o PAA tem origem em aplicações
reais, ligadas a processos de tomada de decisões, é natural que envolva a consideração de diversos objetivos, muitas vezes em conflito. Tal fato motivou a investigação do uso de técnicas de otimização multi-critério que possam ser utilizadas na construção de um sistema de suporte a decisão e aplicadas a uma variante bi-objetivo do PAA, que considera simultaneamente as duas
funções objetivo utilizadas nas variantes mono-objetivo estudadas. Abordagens de resolução exata e aproximada para esta variante bi-objetivo são propostas e seus resultados discutidos. / [en] Optimization in sports is a field of increasing interest. Combinatorial optimization
techniques have been applied e.g. to game scheduling and playoff
elimination. A problem that arises in competition management is the assignment
of referees to games already scheduled. There are a number of
rules and objectives that should be taken into account when referees are
assigned to games. We address two mono-objective versions of a Referee
Assignment Problem (RAP) common to many amateur leagues of sports
such as soccer, baseball, and basketball. The problem is formulated by integer
programming and its decision version is proved to be NP-complete. To
tackle real-life large instances of the RAP, we propose a three-phase heuristic
approach based on a constructive procedure, a repair heuristic to make
solutions feasible, and a local search heuristic to improve feasible solutions,
based on the metaheuristic iterated local search. Numerical results on realistic
instances are presented and discussed. This work also investigates the
solution of a bi-objective version of the RAP, which combines both objective
functions used in the mono-objective versions. Exact and heuristic approaches
are proposed to solve this bi-objective version and its computational
results are discussed.

Identiferoai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:13381
Date16 April 2009
CreatorsALEXANDRE ROCHA DUARTE
ContributorsCELSO DA CRUZ CARNEIRO RIBEIRO, CELSO DA CRUZ CARNEIRO RIBEIRO
PublisherMAXWELL
Source SetsPUC Rio
LanguagePortuguese
Detected LanguagePortuguese
TypeTEXTO

Page generated in 0.0022 seconds