O problema dos árbitros viajantes: complexidade, modelagem e algoritmos
Estudamos neste doutorado o problema dos árbitros viajantes (TUP, do inglês traveling umpire problem), que consiste em um problema de otimizacão baseado no problema real de alocacão de árbitros às partidas da Liga Profissional de Beisebol dos Estados Unidos. O TUP recebe como entrada um torneio roun...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Objeto de conferencia |
| Lenguaje: | Portugués |
| Publicado: |
2017
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/64920 http://www.clei2017-46jaiio.sadio.org.ar/sites/default/files/Mem/CLTD/CLTD-02.pdf |
| Aporte de: |
| id |
I19-R120-10915-64920 |
|---|---|
| record_format |
dspace |
| institution |
Universidad Nacional de La Plata |
| institution_str |
I-19 |
| repository_str |
R-120 |
| collection |
SEDICI (UNLP) |
| language |
Portugués |
| topic |
Ciencias Informáticas árbitros viajantes heurística relax-and-fix traveling umpire problem |
| spellingShingle |
Ciencias Informáticas árbitros viajantes heurística relax-and-fix traveling umpire problem Oliveira, Lucas de Souza, Cid Carvalho de Yunes, Tallys O problema dos árbitros viajantes: complexidade, modelagem e algoritmos |
| topic_facet |
Ciencias Informáticas árbitros viajantes heurística relax-and-fix traveling umpire problem |
| description |
Estudamos neste doutorado o problema dos árbitros viajantes (TUP, do inglês traveling umpire problem), que consiste em um problema de otimizacão baseado no problema real de alocacão de árbitros às partidas da Liga Profissional de Beisebol dos Estados Unidos. O TUP recebe como entrada um torneio round robin duplo e tem como objetivo atribuir árbitros ás partidas deste torneio minimizando a distância total viajada por eles durante toda a competicão e respeitando restricões que impõem que cada árbitro não apite jogos de um mesmo time frequentemente e apite ao menos um jogo na sede de cada time. Demonstramos que o TUP é um problema NP-completo, fechando esta questão em relacão à sua complexidade que ficou em aberto durante sete anos.
Também introduzimos duas novas formulacões matemáticas e uma heurística relax-and-fix para este problema. As análises de resultados computacionais comprovam que as formulacões matemáticas e a heurística relax-and-fix produzem limitantes inferiores e superiores de excelente qualidade para o TUP, melhorando diversos resultados da literatura. |
| format |
Objeto de conferencia Objeto de conferencia |
| author |
Oliveira, Lucas de Souza, Cid Carvalho de Yunes, Tallys |
| author_facet |
Oliveira, Lucas de Souza, Cid Carvalho de Yunes, Tallys |
| author_sort |
Oliveira, Lucas de |
| title |
O problema dos árbitros viajantes: complexidade, modelagem e algoritmos |
| title_short |
O problema dos árbitros viajantes: complexidade, modelagem e algoritmos |
| title_full |
O problema dos árbitros viajantes: complexidade, modelagem e algoritmos |
| title_fullStr |
O problema dos árbitros viajantes: complexidade, modelagem e algoritmos |
| title_full_unstemmed |
O problema dos árbitros viajantes: complexidade, modelagem e algoritmos |
| title_sort |
o problema dos árbitros viajantes: complexidade, modelagem e algoritmos |
| publishDate |
2017 |
| url |
http://sedici.unlp.edu.ar/handle/10915/64920 http://www.clei2017-46jaiio.sadio.org.ar/sites/default/files/Mem/CLTD/CLTD-02.pdf |
| work_keys_str_mv |
AT oliveiralucasde oproblemadosarbitrosviajantescomplexidademodelagemealgoritmos AT souzacidcarvalhode oproblemadosarbitrosviajantescomplexidademodelagemealgoritmos AT yunestallys oproblemadosarbitrosviajantescomplexidademodelagemealgoritmos |
| bdutipo_str |
Repositorios |
| _version_ |
1764820479796838401 |