Meta-heurísticas para o problema da mochila com penalidades
Otimização Combinatória, Problema da Mochila, Meta-heurísticas, Iterated Local Search, Variable Neighborhood Descent.
O problema da mochila está entre um dos problemas de otimização mais conhecidos e estudados. Seu potencial de aplicação e de suas inúmeras variações fazem dele um bom modelo de problema da vida real. Neste trabalho, será abordado o problema da mochila com penalidades. Uma variante, em que a presença de pares de itens conflitantes na solução implicam em uma penalidade. Dado um conjunto de itens e um grafo de conflito, o objetivo do problema é encontrar um coleção de itens que respeitem a capacidade da mochila e maximize o valor total dos itens subtraído das penalidades. Este problema pode ser aplicado desde a organização da força de trabalho em chão de fábrica até problemas de decisão em investimentos. Este trabalho propõe a construção de um novo método para o problema utilizando-se de ferramentas já bem estabelecidas, a meta-heurística ILS e a heurística de busca local VND, existindo também a possibilidade de verificar outras heurísticas e meta-heurísticas. Resultados preliminares já foram obtidos, mostrando que o novo método surpassa outros já aplicados para o problema, em específico, o Carrossel Guloso. Pode-se esperar que este trabalho ofereça uma indicação do caminho que pode ser tomado para o refinamento da resolução do problema, apresentando análises e comparativos entre métodos aplicados ao problema.