Análise dos métodos de resolução de problemas de programação inteira : um estudo de caso no problema de alocação de servidores na ANAC

Abstract

A evolução das tecnologias e sistemas computacionais tem permitido maior utilização de modelos de apoio à decisão formulados através da programação matemática. Dentre eles, destacam-se os que utilizam da Programação Inteira (PI), que por terem seu processo de solução mais complexo, demandam maior esforço computacional e de tempo para problemas de grande porte. Tendo em vista a importância desses tipos de modelos e a diversidade de métodos e ferramentas utilizadas na resolução destes, essa pesquisa buscou identificar os métodos e técnicas adotados na solução de modelos de Programação Inteira, por meio de uma revisão sistemática da literatura, e realizar uma comparação entre a utilização de alguns métodos e ferramentas para solução de um modelo de grande porte. A pesquisa utilizou o estudo desenvolvido no projeto Safety Oversight na Agência Nacional de Aviação Civil (ANAC), que consiste em um problema de alocação dos servidores lotados em diferentes estados do Brasil e que realizam fiscalizações nos diversos aeroportos, levando em consideração o tempo, custo e atividade. Para isso, foram utilizados dois modelos implementados na linguagem Python com auxílio da biblioteca “Pyomo” e dos solvers CPLEX e Gurobi, e testadas 6 instâncias. Os resultados dos testes foram consolidados em uma tabela apresentando o tempo de execução e a Função Objetivo (FO) encontrados para cada instância, comparando o algoritmo implementado em Python com os modelos desenvolvidos na literatura nos softwares LINGO, AIMMS, Julia e heurísticas (Tabu Search, Simulated Annealing e Hibrid). A partir disso, verificou-se que ambos os softwares testados são viáveis e capazes de solucionar a maioria dos cenários no problema de programação inteira da alocação de servidores da ANAC, minimizando o custo com passagem aérea nas fiscalizações. Por fim, destaca-se o desempenho da linguagem de código aberto Python com o solver Gurobi por ter sido capaz de solucionar todas as instâncias testadas, obtendo o melhor desempenho em duas delas comparado aos outros softwares.