Das Montanhas de Minas ao Oceano: Os Caminhos da Ciência para um Futuro Sustentável
20 a 25 de outubro de 2025
Trabalho 20489
| 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 | Dimensões Econômicas: ODS9 |
| Setor | Departamento de Informática |
| Bolsa | CNPq |
| Conclusão de bolsa | Não |
| Apoio financeiro | CNPq |
| Primeiro autor | Nicolas Eliel dos Reis Silva |
| Orientador | JOSE ELIAS CLAUDIO ARROYO |
| Título | Aplicação de Métodos Heurísticos para Problemas de Otimização em Redes |
| Resumo | Neste estudo, aborda-se o problema do Caixeiro Viajante com Estações de Lançamento de Drones, em que um conjunto de n clientes deve ser atendido por um caminhão ou por um drone lançado de uma estação aberta. Existem m estações potenciais, cada uma com nd drones, porém apenas c estações devem ser escolhidas (abertas) para atender os clientes. O problema consiste em selecionar as estações que serão abertas, definir quantos e quais serão os clientes que cada estação irá atender, atribuir os clientes e estações que serão atendidos pelo caminhão e determinar qual a melhor rota deste, que parte de um depósito, passa pelos clientes e estações abertas e retorna para o depósito. O objetivo é minimizar a distância total do percurso do caminhão, a distância de operação dos drones e os custos de abertura das estações, garantindo que todos os clientes sejam atendidos. Para a solução do problema, foram propostos métodos computacionais exatos e heurísticos. O método exato é baseado no modelo de Programação Linear Inteira do problema que é resolvido pelo solver GUROBI. O método heurístico consiste, inicialmente, na construção de soluções iniciais através da heurística gulosa de Inserção Mais Barata (CI - Cheapest Insertion), que busca encontrar a melhor rota para o caminhão passando por clientes e estações abertas; em seguida as soluções sao melhoradas por algoritmos de busca local, tais como busca 2-OPT que visa reduzir a distância percorrida pelo caminhão fazendo troca de arcos; e outra Busca Local que tem como objetivo testar soluções retirando um cliente de uma estação e inserindo-o na rota do caminhão. As soluções determinadas pelas heurı́stica proposta são comparadas com soluções geradas pelo solver GUROBI. A comparação entre os resultados foi feita a partir de imagens obtidas com a biblioteca Matplotlib e de tabelas CSV com informações sobre as soluções geradas, podendo ser comparados diversos aspectos, como o tempo de execução e o custo das soluções. Os resultados mostram que o algoritmo heurístico determina soluções de excelente qualidade gastando tempos de CPU significativamente menores que o GUROBI. |
| Palavras-chave | algoritmos heurísticos, otimização em redes, programação linear inteira |
| Forma de apresentação..... | Painel |
| Link para apresentação | Painel |
|---|