1 |
[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ÉRIOALEXANDRE ROCHA DUARTE 16 April 2009 (has links)
[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.
|
2 |
[en] OPTIMIZATION IN SPORTS: SPORT SCHEDULING AND QUALIFICATION PROBLEMS / [pt] OTIMIZAÇÃO EM ESPORTES: PROGRAMAÇÃO DE TABELAS E PROBLEMAS DE CLASSIFICAÇÃOSEBASTIAN ALBERTO URRUTIA 26 April 2006 (has links)
[pt] O planejamento e a gestão de atividades esportivas é uma
área promissora e pouco explorada para aplicações de
Pesquisa Operacional. Os problemas nesta área são em geral
de formulação simples e alcançam grande difusão nos meios
de comunicação. Embora sua formulação seja simples, em
geral estes problemas são difíceis de serem resolvidos em
termos computacionais. Os resultados de muitos trabalhos
acadêmicos nesta área têm sido aceitos como soluções para
problemas reais e várias soluções vem sendo implementadas
na prática. Esta tese tem como objetivo principal estudar
dois tipos de problemas que surgem na área de esportes: a
programação de tabelas e os problemas da classificação. A
programação de tabelas para competições esportivas é uma
tarefa difícil, na qual diversas técnicas de otimização
combinatória têm sido aplicadas. Nesta tese, formula-se o
Problema do Torneio com Viagens Espelhado como um problema
de otimização em grafos. O problema é resolvido utilizando-
se algoritmos aproximados. Apresentam-se duas heurísticas
para este problema. A primeira é muito rápida e serve para
fornecer soluções iniciais para a segunda, que é capaz de
obter soluções de boa qualidade em tempos razoáveis. São
deduzidos limites duais para um tipo particular de
instâncias. Estes limites permitem provar a otimalidade
das soluções obtidas heuristicamente para instâncias muito
maiores do que as maiores instâncias resolvidas na
literatura. Por ultimo, é apresentado um modelo de
programação linear inteira para o problema, ao qual são
acrescentadas desigualdades válidas. Os problemas da
classificação visam obter condições, necessárias e
suficientes, para a classificação de uma determinada
equipe para as finais de um campeonato em relação ao
número de pontos a ser obtido. São apresentados modelos de
programação linear inteira que permitem resolver estes
problemas no contexto do Campeonato Brasileiro de Futebol. / [en] Sports management is a very attractive and not very
explored area for applications of Operations Research.
Problems in this area use to have simple formulations and
reach a big coveragge by the media. Although their
formulations are simple, in general these problems are
difficult to be solved in computational terms. The results
of many academic works in this area have been accepted as
solutions for real problems and some solutions are being
implemented.
This thesis has the main objective of studying two types
of problems that appear in the sports area: the fixture
creation and the qualification problems.
Fixture creation (also known as sport scheduling) for
sport competitions is a difficult task, in which several
combinatorial optimization techniques has been applied. In
this thesis, the Mirrored Traveling Tournament Problem is
formulated as a graph optmization problem. The problem is
solved using approximation algorithms. Two heuristics are
introduced for this problem. The first one is very fast
and is used to supply initial solutions for the second one
which is able to obtain high quality solutions in
reasonable computation times. Dual limits are deduced for
a particular type of instances. These limits allow to
prove the optimality of the heuristically abtained
solutions for instances that are much bigger than those
soved in the literature. Finally, an integer programming
model is introduced in wich valid inequalities are added.
The qualification problems aim to obtain necessary and
sufficient conditions for the playoffs qualification of a
given team in terms of the number of points to be
obtained. Integer programming models are introduced which
allow solving these problems in the context of the
Brazilian Football Championship.
|
Page generated in 0.0459 seconds