Metaheurísticas para o problema da mochila multidimensional

Detalhes bibliográficos
Ano de defesa: 2016
Autor(a) principal: Dantas, Bianca de Almeida
Orientador(a): Cáceres, Edson Norberto
Banca de defesa: Não Informado pela instituição
Tipo de documento: Tese
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Não Informado pela instituição
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: https://repositorio.ufms.br/handle/123456789/2970
Resumo: O problema da mochila multidimensional ´e amplamente conhecido na área de otimização combinatória e possui diversas aplicações práticas, tais como, dimensionamento de cargas, orçamento de capital, alocação de recursos em sistemas distribuídos, entre outros. Apesar de sua popularidade, sua solução não é trivial, de fato, ele pertence a uma classe de problemas conhecidos como NP-difíceis, para os quais não são conhecidos algoritmos polinomiais capazes de obter uma solução exata para todas as instancias. Essa situação motiva a busca por técnicas alternativas para obter soluções em menor tempo, ainda que aproximadas e, nesse cenário, as metaheurısticas têm se mostrado de especial interesse, pois são capazes de alcançar soluções de boa qualidade para uma ampla variedade de problemas. Entretanto, mesmo as metaheurısticas podem ser relativamente demoradas, em especial para instâncias de tamanho grande, o que encoraja a aplicação de t´técnicas, como as estratégias de paralelização, para reduzir os seus tempos de execução ou, ainda, melhorar a qualidade das soluções. Neste trabalho, apresenta-se o estudo, implementação e análise de um conjunto de metaheurısticas para a solução do problema da mochila multidimensional. São apresentadas e avaliadas diferentes alternativas para a paralelização e os resultados obtidos são comparados com os de outros trabalhos da literatura pesquisada. Para comprovar que os bons resultados possibilitados pelo uso das metaheurısticas estudadas não foram obtidos ao acaso, as soluções foram validadas com a utilização de testes estatísticos.