O problema dos árbitros viajantes: complexidade, modelagem e algoritmos

Abstract

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.