“Bicentenário da Independência: 200 anos de ciência, tecnologia e inovação no Brasil e 96 anos de contribuição da UFV”.
8 a 10 de novembro de 2022
Trabalho 17580
| 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 | PIBIC/CNPq |
| Conclusão de bolsa | Não |
| Apoio financeiro | CNPq |
| Primeiro autor | Paulo Henrique Santana Dezingrini |
| Orientador | JOSE ELIAS CLAUDIO ARROYO |
| Título | Otimização Combinatória Aplicada em Problemas de Programação de Transporte |
| Resumo | O problema do caixeiro viajante (PCV) é um problema de transporte e distribuição amplamente conhecido e estudado na área de Ciência da Computação. Neste problema, um vendedor deseja passar por n cidades percorrendo a menor distância possível e retornando à cidade inicial, em outras palavras, deseja-se determinar a melhor rota do percurso. Neste projeto é estudado uma das variações do PCV, que é o PVC aberto e com sub-rotas. Esta variação difere-se do problema original em dois aspectos principais, sendo eles o fato de que não há a necessidade de retornar à cidade de origem e nem de passar em todas as n cidades, mas apenas em k cidades (k < n). Neste trabalho, inicialmente são desenvolvidas heurísticas para construir soluções aproximadas para o problema (trajetos iniciais). Foram testadas duas heurísticas baseadas nas técnicas do vizinho mais próximo e da inserção mais barata. Foram realizadas uma série de testes e a heurística que apresentou melhores resultados foi a do vizinho mais próximo. Visando então melhorar os resultados até então obtidos, foram aplicadas técnicas de busca local, que consistem em gerar soluções diferentes a partir de algumas modificações feitas na solução original. O conjunto de soluções obtidas é conhecido como vizinhança. O processo de busca em vizinhança é repetido enquanto o algoritmo estiver conseguindo soluções melhores, obtendo assim um ótimo local. Foram utilizados movimentos diferentes para gerar vizinhanças, por exemplo: inserção, troca, 2-Opt, adição-remoção. Para melhorar ainda mais as soluções obtidas, se iniciou a implementação de uma nova busca local, conhecida como RVND (Random Variable Neighborhood Descend) que consiste em explorar um conjunto de vizinhanças em ordem aleatória, e caso exista uma melhora na solução atual, o processo é repetido até não haver mais vizinhanças a serem exploradas. Também foi implementada uma meta-heurística chamada ILS (Iterated Local Search), que aplica a busca local RVND após a perturbação da melhor solução conhecida, assim, obtém-se novos ótimos locais. Foram realizados uma série de experimentos computacionais. Os resultados preliminares obtidos mostraram que o RVND e o ILS obtiveram, respectivamente, 39 e 41 resultados melhores que os já conhecidos na literatura, além de 13 e 12 soluções iguais. Apesar de ainda apresentarem uma grande quantidade de casos piores, ambos métodos apresentaram uma melhora considerável nas soluções conhecidas. |
| Palavras-chave | Heurísticas, Otimização, Problema do caixeiro viajante |
| Forma de apresentação..... | Vídeo |
| Link para apresentação | Vídeo |
|---|