Meta-Heurísticas em Pesquisa Operacional – Capítulo 20

  • Título: Simulated Annealing Aplicado ao Problema de Alocação de Salas com Deslocamentos Mínimos
  • Autores: Rosana Maria Luvezute Kripka e Moacir Kripka
  • DOI:10.7436/2013.mhpo.20
  • Resumo: A otimização combinatorial é comumente utilizada na resolução de aplicações reais complexas, onde geralmente a solução pertence a um conjunto discreto, resultante de todas as combinações entre as possibilidades existentes. Um problema desta natureza é o de alocação de salas de aula em instituições de ensino onde, na distribuição das salas de aula disponíveis, devem ser respeitados tanto o número de alunos de cada disciplina/turma, bem como as capacidades das salas de aula. Neste capítulo apresenta-se uma formulação matemática desenvolvida para a otimização do problema de alocação de salas na Universidade de Passo Fundo, na qual a função objetivo consiste em minimizar a distância total percorrida pelos alunos, com intuito de realizar a distribuição das salas de aula, dos diversos prédios, de modo a manter os alunos o mais próximo possível das suas respectivas unidades. O processo de otimização foi realizado através do método Simulated Annealing, uma vez que apresenta um bom desempenho na resolução de problemas de otimização combinatórial e utiliza poucos parâmetros de controle, comparado a outras meta-heurísticas. Foram realizados testes diversos que comprovaram a validação do modelo. Acredita-se que a formulação matemática apresentada, com pequenas adaptações, poderá resolver problemas específicos de outras Instituições de ensino.
  • Palavras-chave: Modelagem matemática, Alocação de salas de aula, Otimização combinatorial, Simulated annealing.
  • Abstract: In general, combinatorial optimization is used in the resolution of real complex applications, where a solution is obtained from a discrete set, resulting from all the combinations among the possibilities. One such problem is the Classroom Assignment Problem because in the distribution of available classrooms, the number of registered students in each course and the capacities of the classrooms must be respected. This chapter presents a mathematical formulation developed for the optimization of the Classroom Assignment Problem at the University of Passo Fundo, in which the objective function is to minimize the total distance traveled by students, aiming assign classrooms at various buildings in order to keep students as close as possible of their respective units. The optimization process was solved by the Simulated Annealing method because it presents a good performance in solving combinatorial optimization problems and uses fewer control parameters, when compared to other metaheuristics. Various tests were performed for model validation with good results. It is believed that the mathematical modeling presented, with a few adjustments, can solve specific problems of other education institutions..
  • Keywords: Mathematical modeling, Classroom assignment problem, Combinatorial optimization, Simulated annealing.
PDF do capítulo (0,335 MB):
BIBTEX do capítulo:

 

Os comentários estão encerrados.