Estudo comparativo de meta-heurísticas : otimização do modelo de alocação na Agência Nacional de Aviação Civil

Abstract

Órgãos públicos de caráter fiscalizatório, como agências reguladoras, tem a necessidade de atender uma grande demanda de missões com um número limitado de recursos humanos. Esse tipo de problema pode ser categorizado como um problema de High School Timetibling Problem (HSTP) um sub-problema da classe de problemas de alocação e agendamento. É possível observar na literatura um grande número de trabalhos que visam solucionar os problemas de otimização, destacando-se as soluções que envolem as meta-heurísticas. Além do uso desses algoritmos para a resolução de problemas de agendamento, modelos de hibridização de meta-heurísticas têm se mostrado promissores na maximização e minimização de funções objetivo em problemas de agendamento, obtendo resultados sub-ótimos muito próximos aos resultados ótimos. Nesse contexto, o trabalho presente tem como objetivo apresentar e comparar três meta-heurísticas, Busca Tabu, Algoritmo Genético e Simulated Annelaning e dois modelos de hibridização, multi-estágio e sequencial, utilizando como caso de uso, o modelo de alocação das missões da Agência Nacional de Aviação Civil (ANAC). Além disso, foi desenvolvido uma plataforma para uso de não especialistas como aplicação de rede, utilizando a arquitetura REST, onde conectam-se os dados das missões com o algoritmo de otimização que obteve o melhor desempenho, com uma interface amigável e simplificada ao usuário final. Resultados comparativos entre os algoritmos apresentados mostraram que o algoritmo híbrido multi-estágio combinando a abordagem de Busca Tabu e o Algoritmo Genético (HMS) obteve melhor desempenho na maioria dos testes. Já, para os métodos sem hibridização, o algoritmo genético destacou-se com os melhores resultados dentre as demais técnicas comparadas.