"Ciências Básicas para o Desenvolvimento Sustentável"
24 a 26 de outubro de 2023
Trabalho 19578
| 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 | Não |
| Apoio financeiro | CNPq |
| Primeiro autor | Pedro Henrique de Moura |
| Orientador | JOSE ELIAS CLAUDIO ARROYO |
| Outros membros | Paulo Henrique Santana Dezingrini |
| Título | Desenvolvimento de algoritmos exatos e heurísticas para problemas de planejamento da produção e transporte |
| Resumo | Neste trabalho foi estudado um problema de roteamento de veículos, onde é utilizado um veículo terrestre (caminhão) e um veículo aéreo não tripulado (drone), para o serviço de entrega de encomendas de n clientes, de tal maneira que o tempo de atendimento seja minimizado. Na literatura, o problema é chamado de Flying Sidekick The Sallesman Problem with Drone (FTSPD) ou Problema do Caixeiro Viajante com Ajudante Voador. Neste problema o caminhão, parte de um centro de distribuição, transportando as encomendas dos clientes e um drone. Em alguns pontos do trajeto, o drone é lançado pelo caminhão para atender certos clientes elegíveis. Após o drone entregar a encomenda do cliente, ele retorna ao caminhão para a substituição da bateria e ser lançado novamente para atender outro cliente. Apenas clientes com cargas de até determinado peso podem ser atendidos pelo drone e há também a limitação de bateria, logo o trajeto percorrido deve ser tal que o tempo de bateria seja suficiente para que o drone seja lançado do caminhão em um ponto A, atenda um cliente i e retorne para o caminhão em outro ponto B. Este modo de operação reduz o tempo total para atender os n clientes, uma vez que o drone pode se transladar em linhas retas e livre de congestionamentos. Após atender todos os clientes, o caminhão deve retornar ao centro de distribuição, no menor tempo possível. O crescimento promissor de entregas com drone é objeto de estudo no exterior e já opera há alguns anos conhecido como “last-mile delivery with drone”, entrega de última milha com drone. No Brasil, algumas empresas vêm implementando o uso de drones para otimizar o processo logístico, atendendo as normas de uso do espaço aéreo brasileiro determinadas pela Agência Nacional de Aviação Civil (ANAC), que determina as características de produtos que podem ou não ser transportados por drones. O problema do Caixeiro Viajante, muito estudado na literatura, é caracterizado como um problema NP-difícil. Logo, as soluções para este problema são determinadas por meio de heurísticas, métodos de busca local e meta-heurísticas. Este trabalho foi desenvolvido utilizando algoritmos heurísticos, métodos de busca local e técnicas de programação dinâmica. A metodologia consiste em primeiro, encontrar uma rota para o caminhão e posteriormente determinar os clientes que serão atendidos pelo drone. Inicialmente é gerada uma rota do caixeiro viajante, por meio da heurística do vizinho mais próximo. Esta rota é melhorada por um método de busca local e após isso é utilizado um algoritmo de programação dinâmica para encontrar os melhores pontos de lançamento do drone e pontos de retorno, após o atendimento de um cliente. Até o presente momento foram realizados testes preliminares e foi possível observar que os resultados obtidos são promissores. |
| Palavras-chave | Heurísticas, otimização, drones |
| Forma de apresentação..... | Painel |
| Link para apresentação | Painel |
|---|