Do Lógico ao Abstrato: A Ciência no Cotidiano
23 a 28 de outubro de 2017
Trabalho 8389
| ISSN | 2237-9045 |
|---|---|
| Instituição | Universidade Federal de Viçosa |
| Nível | Graduação |
| Modalidade | Pesquisa |
| Área de conhecimento | Ciências Exatas e Tecnológicas |
| Área temática | Ciência da Computação |
| Setor | Departamento de Informática |
| Bolsa | CNPq |
| Conclusão de bolsa | Sim |
| Apoio financeiro | CNPq |
| Primeiro autor | Igor Rodrigues Cardoso |
| Orientador | ANDRE GUSTAVO DOS SANTOS |
| Título | Métodos exatos e heurísticos para problemas multicomponentes |
| Resumo | Um problema multicomponente envolve mais de um problema de otimização de forma interdependente, isto é, em que a otimização de um interfere direta ou indiretamente na otimização do outro. Neste estudo trabalhamos com Problema do Ladrão Viajante (do inglês Traveler Thief Problem), que combina o Problema do Caixeiro Viajante com o Problema da Mochila. O problema do ladrão viajante (PLV) e problema dos múltiplos ladrões viajantes (PMLV) tentam aproximar alguns problemas de mundo real ao mundo teórico. Para contextualizar, suponha um ladrão que está em uma cidade inicial e possui um mapa com a distância de uma cidade para todas as outras; ele também sabe o peso e o valor de cada item que ele pode roubar em cada cidade; além disso, alugou uma mochila de taxa R que tem capacidade de carga W, sendo que o aluguel a ser pago aumenta conforme o tempo que ele demora para devolvê-la. No caso, quanto mais pesada a mochila do ladrão, mais devagar ele anda e mais caro será o aluguel. É conhecida também a velocidade máxima e mínima que o ladrão consegue andar, então qual a sequência de cidades que o ladrão deve visitar (componente Problema do Caixeiro Viajante) e qual o plano de coleta de itens ele deve fazer (componente Problema da Mochila) para que obtenha o melhor lucro? Já o PMLV consiste em vários ladrões em vez de um único. Para estudo dos dois problemas foram desenvolvidos, na linguagem c++, heurísticas e algoritmos de buscas locais que tentassem os resolver de forma satisfatória. Primeiramente foi desenvolvido uma solução aproximada para o PLV e depois a mesma foi generalizada para que pudesse resolver o problema para múltiplos ladrões. Para gerar uma rota inicial, foi utilizada a heurística baseada na árvore geradora mínima, pois essa garante que seja produzida uma rota no máximo duas vezes pior que a rota ótima para começar a análise do problema. Em seguida é criado um plano de coleta baseado nessa primeira rota, usando uma heurística que consiste em ordenar os itens de acordo com seu impacto na rota dada. Como a rota e o plano de coleta estão intimamente conectados, essa primeira solução é quase sempre insatisfatória, pois não foram levadas em consideração outras alternativas, já que uma rota boa pode não produzir um plano de coleta bom, e então piorar a minha solução final. Assim, a primeira solução gerada passa por uma busca local, que alterna a ordem de cidades na rota e refaz o plano de coleta: se alguma dessas trocas melhorar a solução atual, ela passa a ser a solução atual, repetindo o processo da busca enquanto for encontrada uma solução melhor. Para o PMLV, há o problema de distribuição das cidades: neste trabalho, a rota final do PLV é dividida para os N ladrões de forma sequencial e a busca local é aplicada individualmente na rota de cada ladrão. A solução desenvolvida é capaz de retornar, na maioria das vezes, uma solução lucrativa, entretanto ainda consome uma quantidade razoável de tempo de processamento. |
| Palavras-chave | Heurísticas, Meta-heurísticas, Otimização |
| Forma de apresentação..... | Painel |