Matheurísticas para o problema da mochila com restrição de conflitos

Vol 54, 2022 - 152866
Trabalho completo (oral)
Favoritar este trabalho
Como citar esse trabalho?
Resumo

Neste trabalho, três classes de matheurísticas são avaliadas para a construção de heurísticas para o problema da mochila com restrição de conflitos. As classes de matheurísticas avaliadas são: métodos de decomposição, métodos baseados na relaxação linear e métodos de melhoria. Para a heurística de decomposição, foram propostas heurísticas gulosas e aleatórias para resolver os conflitos seguidas por métodos exatos para resolver a mochila. A heurística baseada na relaxação linear proposta foi a Relax&Fix e a de melhoria foi o Large Neighbourhood Search (LNS). Testes computacionais foram conduzidos em instâncias da literatura para avaliar a qualidade das soluções. A combinação entre Relax&Fix e LNS obteve melhores resultados em 57% das instâncias, quando comparado com as demais, e o tempo gasto, na média, foi de 116 segundos. Em relação à literatura, o algoritmo proposto obteve resultados próximos do ótimo na maior das instâncias com baixa densidade, mas não foi competitivo nas instâncias densas.

Compartilhe suas ideias ou dúvidas com os autores!

Sabia que o maior estímulo no desenvolvimento científico e cultural é a curiosidade? Deixe seus questionamentos ou sugestões para o autor!

Faça login para interagir

Tem uma dúvida ou sugestão? Compartilhe seu feedback com os autores!

Instituições
  • 1 Universidade Federal de Mato Grosso do Sul
Eixo Temático
  • 13 - MH – Metaheurísticas
Palavras-chave
Heurísticas
Programação linear inteira
Relax&Fix