Análise de algoritmos baseados em VNS para a resolução do problema de alocação de salas de aula no ensino superior

Abstract

RESUMO: O Problema de Alocação de Salas em uma instituição acadêmica consiste em distribuir turmas para as devidas salas, respeitando uma série de restrições operacionais e preferências. Neste trabalho, o objeto de pesquisa é investigar alguns métodos de resolução de um problema real encontrado em uma instituição de ensino superior pública. O trabalho apresentado propõe duas versões de algoritmos heurísticos baseados na resolução sucessiva de problemas de designação linear e quatro versões baseadas na meta-heurística VNS: GVNS clássico e três algoritmos encontrados na literatura e que implementam diferentes técnicas para definir a ordem de execução das buscas locais na estrutura de vizinhança. Experimentos computacionais foram realizados aplicando-se os algoritmos propostos para resolver instâncias extraídas do banco de dados da instituição. Os resultados obtidos mostraram que os algoritmos heurísticos baseados na resolução sucessiva de problemas de designação linear forneceram boas soluções em um tempo relativamente curto e que as soluções de melhor qualidade foram obtidas com os algoritmos PAS_GVNS, baseado em VNS, e PAS_GVNS_SA, no qual a ordem das vizinhanças é escolhida de forma autoadaptativa. Além disso, foram observados indícios de que a ordem em que são aplicadas as buscas locais no processo de exploração das estruturas de vizinhança não é determinante para a melhoria do resultado final da solução

ABSTRACT: The Classroom Assignment Problem in an academic institution consists of distributing courses for the due rooms, respecting a series of operational restrictions and preferences. At this work, the object of research is to investigate some methods of solving a real problem found in a public higher education institution. The presented work proposes two versions of heuristic algorithms based on the successive resolution of linear designation problems and four versions based on the VNS metaheuristic: classic GVNS and three algorithms found in the literature that implement different techniques to define the order of execution local searches in the neighborhood structure. Computational experiments were performed applying the proposed algorithms to solve instances extracted from the database of the institution. The results obtained showed that the heuristic algorithms based on the successive resolution of linear designation problems provided good solutions in a relatively short time and that the best quality solutions were obtained with the algorithms PAS_GVNS, based on in VNS, and PAS_GVNS_SA, in which the order of neighborhoods is chosen in a self-adaptive way. In addition, evidence was observed that the order in which local searches are applied in the process of exploring neighborhood structures is not decisive for improving the final result of the solution